Menu Close

Prove-that-there-are-n-r-1-n-1-ways-of-placing-r-identical-objects-in-n-compartments-where-n-gt-r-

Tinku Tara 0 Comments
Pin




Question Number 3884 by Yozzii last updated on 23/Dec/15
Prove that there are (((n+r−1)),((n−1)) ) ways of placing r identical objects in n compartments, where n>r.
$${Prove}\:{that}\:{there}\:{are}\:\begin{pmatrix}{{n}+{r}−\mathrm{1}}\\{{n}−\mathrm{1}}\end{pmatrix}\: \\ $$$${ways}\:{of}\:{placing}\:{r}\:{identical}\:{objects} \\ $$$${in}\:{n}\:{compartments},\:{where}\:{n}>{r}. \\ $$
Commented by RasheedSindhi last updated on 24/Dec/15
Let r objects are denoted as o_0 ,o_1 ,o_2 ,...o_(r−1) . For o_0 there are n ways. For o_1 there are n−1 ways. For o_2 there are n−2 ways. For o_3 there are n−3 ways. ⋮ For o_(r−1) there are n−r+1 ways. Total ways: n(n−1)(n−2)...(n−r+1) =^n p_r = ((n),(r) ) r!=((n!)/(r!(n−r)!))×r! =((n!)/((n−r)!)) Or (((n+r−1)),((n−1)) ) ways.??? Continue
$${Let}\:{r}\:{objects}\:{are}\:{denoted}\:{as}\: \\ $$$$\boldsymbol{\mathrm{o}}_{\mathrm{0}} ,\boldsymbol{\mathrm{o}}_{\mathrm{1}} ,\boldsymbol{\mathrm{o}}_{\mathrm{2}} ,…\boldsymbol{\mathrm{o}}_{\boldsymbol{\mathrm{r}}−\mathrm{1}} . \\ $$$${For}\:\boldsymbol{\mathrm{o}}_{\mathrm{0}} \:{there}\:{are}\:{n}\:{ways}. \\ $$$${For}\:\boldsymbol{\mathrm{o}}_{\mathrm{1}} \:{there}\:{are}\:{n}−\mathrm{1}\:{ways}. \\ $$$${For}\:\boldsymbol{\mathrm{o}}_{\mathrm{2}} \:{there}\:{are}\:{n}−\mathrm{2}\:{ways}. \\ $$$${For}\:\boldsymbol{\mathrm{o}}_{\mathrm{3}} \:{there}\:{are}\:{n}−\mathrm{3}\:{ways}. \\ $$$$\vdots \\ $$$${For}\:\boldsymbol{\mathrm{o}}_{\boldsymbol{\mathrm{r}}−\mathrm{1}} \:{there}\:{are}\:{n}−{r}+\mathrm{1}\:{ways}. \\ $$$${Total}\:{ways}: \\ $$$${n}\left({n}−\mathrm{1}\right)\left({n}−\mathrm{2}\right)…\left({n}−{r}+\mathrm{1}\right) \\ $$$$=^{{n}} \mathrm{p}_{\mathrm{r}} =\begin{pmatrix}{\mathrm{n}}\\{\mathrm{r}}\end{pmatrix}\:\mathrm{r}!=\frac{\mathrm{n}!}{\mathrm{r}!\left(\mathrm{n}−\mathrm{r}\right)!}×\mathrm{r}! \\ $$$$\:\:=\frac{{n}!}{\left({n}−{r}\right)!} \\ $$$${Or} \\ $$$$\begin{pmatrix}{{n}+{r}−\mathrm{1}}\\{{n}−\mathrm{1}}\end{pmatrix}\:\:{ways}.??? \\ $$$${Continue} \\ $$
Commented by Yozzii 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)) )}.
$${From}\:{my}\:{investigation}\:{on}\:{this},\:{you} \\ $$$${can}\:{look}\:{at}\:{how}\:{can}\:{obtain}\:{the}\:{value} \\ $$$${of}\:{r}\:{via}\:{adding}\:{integers}.\:{For}\:{example} \\ $$$${if}\:{r}=\mathrm{4}\:{and}\:{n}\:{is}\:{fixed},\:{we}\:{could}\: \\ $$$${distribute}\:{r}=\mathrm{4}\:{like}\:\mathrm{1}+\mathrm{1}+\mathrm{1}+\mathrm{1}\:\left(\mathrm{4}\:{compartments}\right) \\ $$$${or}\:\mathrm{1}+\mathrm{1}+\mathrm{2}\:{or}\:\mathrm{1}+\mathrm{2}+\mathrm{1}\:{or}\:\mathrm{2}+\mathrm{1}+\mathrm{1}\:\left(\mathrm{3}\:{compartments}\right) \\ $$$${or}\:\mathrm{1}+\mathrm{3}\:{or}\:\mathrm{3}+\mathrm{1}\:{or}\:\mathrm{2}+\mathrm{2}\:\left(\mathrm{2}\:{compartments}\right) \\ $$$${or}\:\mathrm{4}\:\left(\mathrm{1}\:{compartment}\right). \\ $$$${You}\:{have}\:{n}\:{compartments}\: \\ $$$$\Rightarrow\:\begin{pmatrix}{{n}}\\{\mathrm{4}}\end{pmatrix}\:{ways}\:{for}\:\mathrm{1}+\mathrm{1}+\mathrm{1}+\mathrm{1} \\ $$$$\Rightarrow\:\begin{pmatrix}{{n}}\\{\mathrm{3}}\end{pmatrix}+\begin{pmatrix}{{n}}\\{\mathrm{3}}\end{pmatrix}+\begin{pmatrix}{{n}}\\{\mathrm{3}}\end{pmatrix}=\mathrm{3}\begin{pmatrix}{{n}}\\{\mathrm{3}}\end{pmatrix}\:{ways}\: \\ $$$${for}\:\mathrm{1}+\mathrm{1}+\mathrm{2},\:\mathrm{1}+\mathrm{2}+\mathrm{1},\:\mathrm{2}+\mathrm{1}+\mathrm{1} \\ $$$$\Rightarrow\mathrm{3}\begin{pmatrix}{{n}}\\{\mathrm{2}}\end{pmatrix}\:{ways}\:{for}\:\mathrm{1}+\mathrm{3},\mathrm{3}+\mathrm{1},\mathrm{2}+\mathrm{2} \\ $$$$\Rightarrow\:\begin{pmatrix}{{n}}\\{\mathrm{1}}\end{pmatrix}\:{ways}\:{for}\:\mathrm{4}. \\ $$$$\Rightarrow{Total}\:{number}\:{of}\:{ways}\: \\ $$$$=\begin{pmatrix}{{n}}\\{\mathrm{1}}\end{pmatrix}+\mathrm{3}\begin{pmatrix}{{n}}\\{\mathrm{2}}\end{pmatrix}+\mathrm{3}\begin{pmatrix}{{n}}\\{\mathrm{3}}\end{pmatrix}+\begin{pmatrix}{{n}}\\{\mathrm{4}}\end{pmatrix}. \\ $$$$ \\ $$$${For}\:{r}=\mathrm{5}\:{I}\:{deduced} \\ $$$$\begin{pmatrix}{{n}}\\{\mathrm{1}}\end{pmatrix}+\mathrm{4}\begin{pmatrix}{{n}}\\{\mathrm{2}}\end{pmatrix}+\mathrm{6}\begin{pmatrix}{{n}}\\{\mathrm{3}}\end{pmatrix}+\mathrm{4}\begin{pmatrix}{{n}}\\{\mathrm{4}}\end{pmatrix}+\begin{pmatrix}{{n}}\\{\mathrm{5}}\end{pmatrix}\:{ways}. \\ $$$${I}\:{saw}\:{the}\:{binomial}\:{coefficients} \\ $$$${arising}\:{in}\:{these}\:{answers}\:{so}\:{I}\:{guessed} \\ $$$${that}\:{generally}, \\ $$$${number}\:{of}\:{ways}=\underset{{i}=\mathrm{0}} {\overset{{r}−\mathrm{1}} {\sum}}\left\{\begin{pmatrix}{{r}−\mathrm{1}}\\{{i}}\end{pmatrix}×\begin{pmatrix}{{n}}\\{{i}+\mathrm{1}}\end{pmatrix}\right\}. \\ $$$${It}\:{is}\:{required}\:{to}\:{prove}\:{that}\: \\ $$$$\begin{pmatrix}{{n}+{r}−\mathrm{1}}\\{{n}−\mathrm{1}}\end{pmatrix}=\underset{{i}=\mathrm{1}} {\overset{{r}−\mathrm{1}} {\sum}}\left\{\begin{pmatrix}{{r}−\mathrm{1}}\\{{i}}\end{pmatrix}\begin{pmatrix}{{n}}\\{{i}+\mathrm{1}}\end{pmatrix}\right\}. \\ $$$$ \\ $$$$ \\ $$
Commented by RasheedSindhi last updated on 24/Dec/15
Perhaps I misunderstood your question.I supposed to place one object per compartment.There are n compartments. So first of r objects can go in anyone of n compartments.So there are are n ways for first object. Actually I didn′t give due importance to the word ′ identical ′!
$${Perhaps}\:{I}\:{misunderstood}\:{your} \\ $$$${question}.{I}\:{supposed}\:{to}\:{place}\:{one} \\ $$$${object}\:{per}\:{compartment}.{There} \\ $$$${are}\:{n}\:{compartments}.\:{So}\:{first} \\ $$$${of}\:{r}\:{objects}\:{can}\:{go}\:{in}\:{anyone} \\ $$$${of}\:{n}\:{compartments}.{So}\:{there}\:{are} \\ $$$${are}\:{n}\:{ways}\:{for}\:{first}\:{object}.\:{Actually} \\ $$$${I}\:{didn}'{t}\:{give}\:{due}\:{importance}\:{to} \\ $$$${the}\:{word}\:'\:{identical}\:'! \\ $$
Commented by prakash jain last updated on 24/Dec/15
Stars and Bars
$$\mathrm{Stars}\:\mathrm{and}\:\mathrm{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) markers divide r objects in n−compartments. So 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 objects arr divided into n−compartments. This method is known as stars and bars.
$$\mathrm{Taks}\:\left({n}+{r}−\mathrm{1}\right)\:\mathrm{position}.\: \\ $$$$\mathrm{Place}\:{n}−\mathrm{1}\:\mathrm{markers}\:\mathrm{at}\:\mathrm{any}\:\mathrm{of}\:\mathrm{those}\:\mathrm{postions}. \\ $$$$\mathrm{Remaining}\:{r}\:\mathrm{positions}\:\mathrm{are}\:\mathrm{occupied}\:\mathrm{by} \\ $$$$\mathrm{objects}. \\ $$$$\left({n}−\mathrm{1}\right)\:{markers}\:{divide}\:{r}\:{objects}\:{in}\:{n}−{compartments}. \\ $$$${S}\mathrm{o}\:\mathrm{total}\:\mathrm{number}\:\mathrm{of}\:\mathrm{ways}:\:\:^{{n}+{r}−\mathrm{1}} {C}_{{n}−\mathrm{1}} . \\ $$$$\mathrm{Examples}\:\left(\mathrm{stars}\:\mathrm{are}\:\mathrm{objects}\:\mathrm{bars}\:\mathrm{divide}\:\mathrm{them}\right) \\ $$$$\mathrm{4}\:\mathrm{obects}\:\mathrm{6}\:\mathrm{compartments}\:\left(\mathrm{5}\:\mathrm{bars}\right) \\ $$$$\bigstar\mid\mid\bigstar\mid\mid\mid\bigstar\bigstar\: \\ $$$$\:\mathrm{divisions}\:\mathrm{1},\mathrm{0},\mathrm{1},\mathrm{0},\mathrm{0},\mathrm{2} \\ $$$$\mathrm{total}\:\mathrm{position}\:\mathrm{9} \\ $$$$−\:−\:−\:−\:−\:−\:−\:−\:− \\ $$$$\mathrm{place}\:\left({n}−\mathrm{1}\right)\:\mathrm{bars}\:\mathrm{or}\:\mathrm{dividers} \\ $$$$−\:\mid\:\:\mid\:−\mid\:\mid\:\mid\:−\:− \\ $$$${r}\:{objects}\:{arr}\:{divided}\:{into}\:{n}−{compartments}. \\ $$$$\mathrm{This}\:\mathrm{method}\:\mathrm{is}\:\mathrm{known}\:\mathrm{as}\:\mathrm{stars}\:\mathrm{and}\:\mathrm{bars}. \\ $$
Commented by Yozzii 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}\:{never}\:{heard}\:{of}\:{this}\:{method}\:{before}. \\ $$$${I}\:{went}\:{after}\:{considering}\:{the}\:{identity} \\ $$$$\:\left(\mathrm{1}+{x}\right)^{{n}+{r}−\mathrm{1}} =\left(\mathrm{1}+{x}\right)^{{n}} \left(\mathrm{1}+{x}\right)^{{r}−\mathrm{1}} \: \\ $$$${for}\:{the}\:{coefficient}\:{in}\:{x}^{{n}−\mathrm{1}} \\ $$$${to}\:{prove}\:{that}\:\underset{{i}=\mathrm{0}} {\overset{{r}−\mathrm{1}} {\sum}}\left\{\begin{pmatrix}{{r}−\mathrm{1}}\\{{i}}\end{pmatrix}\begin{pmatrix}{{n}}\\{{i}+\mathrm{1}}\end{pmatrix}\right\}=\begin{pmatrix}{{n}+{r}−\mathrm{1}}\\{{n}−\mathrm{1}}\end{pmatrix}. \\ $$$$ \\ $$
Commented by prakash 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.
$$\mathrm{I}\:\mathrm{think}\:\mathrm{it}\:\mathrm{is}\:\mathrm{truly}\:\mathrm{exceptional}\:\mathrm{on}\:\mathrm{your} \\ $$$$\mathrm{part}\:\mathrm{to}\:\mathrm{come}\:\mathrm{up}\:\mathrm{with}\:\mathrm{this}\:\mathrm{method}\:\mathrm{on}\:\mathrm{your} \\ $$$$\mathrm{own}.\: \\ $$
Commented by Yozzii last updated on 24/Dec/15
Thank you very much for your kind words! Encouragement is beneficial when it is you think you′re making slow progress in individual mathematical studies. You′re further driven to continue trying as such a person.
$${Thank}\:{you}\:{very}\:{much}\:{for}\:{your}\:{kind} \\ $$$${words}!\:{Encouragement}\:{is}\:{beneficial} \\ $$$${when}\:{it}\:{is}\:{you}\:{think}\:{you}'{re}\:{making} \\ $$$${slow}\:{progress}\:{in}\:{individual}\:{mathematical} \\ $$$${studies}.\:{You}'{re}\:{further}\:{driven}\:{to} \\ $$$${continue}\:{trying}\:{as}\:{such}\:{a}\:{person}. \\ $$

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *