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

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 byRasheedSindhi 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 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)) )}.

$${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 byRasheedSindhi 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 byprakash 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 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}\:{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 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.

$$\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 byYozzii 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}. \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com