Prove that there are (((n+r−1)),((n−1)) ) ways of placing r identical objects in n compartments, where n>r.


Question and Answers Forum

All Questions Topic List
Permutation and Combination Questions
Previous in All Question Next in All Question
Previous in Permutation and Combination Next in Permutation and Combination
Question Number 3884 by Yozzii last updated on 23/Dec/15

$P r o v e t h a t t h e r e a r e (\begin{matrix} n + r - 1 \\ n - 1 \end{matrix})$ $w a y s o f p l a c i n g r i d e n t i c a l o b j e c t s$ $i n n c o m p a r t m e n t s, w h e r e n > r .$
Commented byRasheedSindhi last updated on 24/Dec/15

$L e t r o b j e c t s a r e d e n o t e d a s$ $o_{0}, o_{1}, o_{2}, . . . o_{r - 1} .$ $F o r o_{0} t h e r e a r e n w a y s .$ $F o r o_{1} t h e r e a r e n - 1 w a y s .$ $F o r o_{2} t h e r e a r e n - 2 w a y s .$ $F o r o_{3} t h e r e a r e n - 3 w a y s .$ $⋮$ $F o r o_{r - 1} t h e r e a r e n - r + 1 w a y s .$ $T o t a l w a y s :$ $n (n - 1) (n - 2) . . . (n - r + 1)$ $=^{n} p_{r} = (\begin{matrix} n \\ r \end{matrix}) r! = \frac{n!}{r! (n - r)!} \times r!$ $= \frac{n!}{(n - r)!}$ $O r$ $(\begin{matrix} n + r - 1 \\ n - 1 \end{matrix}) w a y s . ? ? ?$ $C o n t i n u e$
Commented byYozzii last updated on 24/Dec/15
$From my investigation on this, you can look at how can obtain the value of r via adding integers. For example if r=4 and n is fixed, we could distribute r=4 like 1+1+1+1 (4 compartments) or 1+1+2 or 1+2+1 or 2+1+1 (3 compartments) or 1+3 or 3+1 or 2+2 (2 compartments) or 4 (1 compartment). You have n compartments ⇒ ((n),(4) ) ways for 1+1+1+1 ⇒ ((n),(3) )+ ((n),(3) )+ ((n),(3) )=3 ((n),(3) ) ways for 1+1+2, 1+2+1, 2+1+1 ⇒3 ((n),(2) ) ways for 1+3,3+1,2+2 ⇒ ((n),(1) ) ways for 4. ⇒Total number of ways = ((n),(1) )+3 ((n),(2) )+3 ((n),(3) )+ ((n),(4) ). For r=5 I deduced ((n),(1) )+4 ((n),(2) )+6 ((n),(3) )+4 ((n),(4) )+ ((n),(5) ) ways. I saw the binomial coefficients arising in these answers so I guessed that generally, number of ways=Σ_(i=0) ^(r−1) { (((r−1)),(i) )× ((n),((i+1)) )}. It is required to prove that (((n+r−1)),((n−1)) )=Σ_(i=1) ^(r−1) { (((r−1)),(i) ) ((n),((i+1)) )}.$
$F r o m m y i n v e s t i g a t i o n o n t h i s, y o u$ $c a n l o o k a t h o w c a n o b t a i n t h e v a l u e$ $o f r v i a a d d i n g i n t e g e r s . F o r e x a m p l e$ $i f r = 4 a n d n i s f i x e d, w e c o u l d$ $d i s t r i b u t e r = 4 l i k e 1 + 1 + 1 + 1 (4 c o m p a r t m e n t s)$ $o r 1 + 1 + 2 o r 1 + 2 + 1 o r 2 + 1 + 1 (3 c o m p a r t m e n t s)$ $o r 1 + 3 o r 3 + 1 o r 2 + 2 (2 c o m p a r t m e n t s)$ $o r 4 (1 c o m p a r t m e n t) .$ $Y o u h a v e n c o m p a r t m e n t s$ $\Rightarrow (\begin{matrix} n \\ 4 \end{matrix}) w a y s f o r 1 + 1 + 1 + 1$ $\Rightarrow (\begin{matrix} n \\ 3 \end{matrix}) + (\begin{matrix} n \\ 3 \end{matrix}) + (\begin{matrix} n \\ 3 \end{matrix}) = 3 (\begin{matrix} n \\ 3 \end{matrix}) w a y s$ $f o r 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1$ $\Rightarrow 3 (\begin{matrix} n \\ 2 \end{matrix}) w a y s f o r 1 + 3, 3 + 1, 2 + 2$ $\Rightarrow (\begin{matrix} n \\ 1 \end{matrix}) w a y s f o r 4 .$ $\Rightarrow T o t a l n u m b e r o f w a y s$ $= (\begin{matrix} n \\ 1 \end{matrix}) + 3 (\begin{matrix} n \\ 2 \end{matrix}) + 3 (\begin{matrix} n \\ 3 \end{matrix}) + (\begin{matrix} n \\ 4 \end{matrix}) .$ $F o r r = 5 I d e d u c e d$ $(\begin{matrix} n \\ 1 \end{matrix}) + 4 (\begin{matrix} n \\ 2 \end{matrix}) + 6 (\begin{matrix} n \\ 3 \end{matrix}) + 4 (\begin{matrix} n \\ 4 \end{matrix}) + (\begin{matrix} n \\ 5 \end{matrix}) w a y s .$ $I s a w t h e b i n o m i a l c o e f f i c i e n t s$ $a r i s i n g i n t h e s e a n s w e r s s o I g u e s s e d$ $t h a t g e n e r a l l y,$ $n u m b e r o f w a y s = \underset{i = 0}{\sum^{r - 1}} {(\begin{matrix} r - 1 \\ i \end{matrix}) \times (\begin{matrix} n \\ i + 1 \end{matrix})} .$ $I t i s r e q u i r e d t o p r o v e t h a t$ $(\begin{matrix} n + r - 1 \\ n - 1 \end{matrix}) = \underset{i = 1}{\sum^{r - 1}} {(\begin{matrix} r - 1 \\ i \end{matrix}) (\begin{matrix} n \\ i + 1 \end{matrix})} .$
Commented byRasheedSindhi last updated on 24/Dec/15

$P e r h a p s I m i s u n d e r s t o o d y o u r$ $q u e s t i o n . I s u p p o s e d t o p l a c e o n e$ $o b j e c t p e r c o m p a r t m e n t . T h e r e$ $a r e n c o m p a r t m e n t s . S o f i r s t$ $o f r o b j e c t s c a n g o i n a n y o n e$ $o f n c o m p a r t m e n t s . S o t h e r e a r e$ $a r e n w a y s f o r f i r s t o b j e c t . A c t u a l l y$ $I {d i d n}^{'} t g i v e d u e i m p o r t a n c e t o$ $t h e w o r d^{'} i d e n t i c a l^{'}!$
Commented byprakash jain last updated on 24/Dec/15

$Stars and Bars$
	Answered by prakash jain last updated on 24/Dec/15

	$Taks (n + r - 1) position .$ $Place n - 1 markers at any of those postions .$ $Remaining r positions are occupied by$ $objects .$ $(n - 1) m a r k e r s d i v i d e r o b j e c t s i n n - c o m p a r t m e n t s .$ $S o total number of ways :^{n + r - 1} C_{n - 1} .$ $Examples (stars are objects bars divide them)$ $4 obects 6 compartments (5 bars)$ $★ ∣∣ ★ ∣∣∣ ★ ★$ $divisions 1, 0, 1, 0, 0, 2$ $total position 9$ $- - - - - - - - -$ $place (n - 1) bars or dividers$ $- ∣ ∣ - ∣ ∣ ∣ - -$ $r o b j e c t s a r r d i v i d e d i n t o n - c o m p a r t m e n t s .$ $This method is known as stars and bars .$
	Commented byYozzii last updated on 24/Dec/15
	$I never heard of this method before. I went after considering the identity (1+x)^(n+r−1) =(1+x)^n (1+x)^(r−1) for the coefficient in x^(n−1) to prove that Σ_(i=0) ^(r−1) { (((r−1)),(i) ) ((n),((i+1)) )}= (((n+r−1)),((n−1)) ).$
	$I n e v e r h e a r d o f t h i s m e t h o d b e f o r e .$ $I w e n t a f t e r c o n s i d e r i n g t h e i d e n t i t y$ ${(1 + x)}^{n + r - 1} = {(1 + x)}^{n} {(1 + x)}^{r - 1}$ $f o r t h e c o e f f i c i e n t i n x^{n - 1}$ $t o p r o v e t h a t \underset{i = 0}{\sum^{r - 1}} {(\begin{matrix} r - 1 \\ i \end{matrix}) (\begin{matrix} n \\ i + 1 \end{matrix})} = (\begin{matrix} n + r - 1 \\ n - 1 \end{matrix}) .$
	Commented byprakash jain last updated on 24/Dec/15

	$I think it is truly exceptional on your$ $part to come up with this method on your$ $own .$
	Commented byYozzii last updated on 24/Dec/15

	$T h a n k y o u v e r y m u c h f o r y o u r k i n d$ $w o r d s! E n c o u r a g e m e n t i s b e n e f i c i a l$ $w h e n i t i s y o u t h i n k {y o u}^{'} r e m a k i n g$ $s l o w p r o g r e s s i n i n d i v i d u a l m a t h e m a t i c a l$ $s t u d i e s . {Y o u}^{'} r e f u r t h e r d r i v e n t o$ $c o n t i n u e t r y i n g a s s u c h a p e r s o n .$
Terms of Service
Privacy Policy
Contact: info@tinkutara.com

Question and Answers Forum