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 195538 by SLVR last updated on 04/Aug/23

Number of distributions of  n different articles to r different  boxes  so as 1)empty box allowed  2)empty box not allowed  with proof...kindly help me

$${Number}\:{of}\:{distributions}\:{of} \\ $$$${n}\:{different}\:{articles}\:{to}\:{r}\:{different}\:\:{boxes} \\ $$$$\left.{so}\:{as}\:\mathrm{1}\right){empty}\:{box}\:{allowed} \\ $$$$\left.\mathrm{2}\right){empty}\:{box}\:{not}\:{allowed} \\ $$$${with}\:{proof}...{kindly}\:{help}\:{me} \\ $$

Commented by SLVR last updated on 04/Aug/23

sir...kindly give proof

$${sir}...{kindly}\:{give}\:{proof} \\ $$

Commented by SLVR last updated on 05/Aug/23

sir Mr.W..or...any one can  help me...i need bit urgently

$${sir}\:{Mr}.{W}..{or}...{any}\:{one}\:{can} \\ $$$${help}\:{me}...{i}\:{need}\:{bit}\:{urgently} \\ $$

Commented by mr W last updated on 05/Aug/23

using generating function method  we can see that the result is the  coefficient of term x^n  in expansion  1) n!(1+(x/1)+(x^2 /(2!))+(x^3 /(3!))+...)^r , i.e.  n!e^(rx)   2) n!((x/1)+(x^2 /(2!))+(x^3 /(3!))+...)^r , i.e.  n!(e^x −1)^r

$${using}\:{generating}\:{function}\:{method} \\ $$$${we}\:{can}\:{see}\:{that}\:{the}\:{result}\:{is}\:{the} \\ $$$${coefficient}\:{of}\:{term}\:{x}^{{n}} \:{in}\:{expansion} \\ $$$$\left.\mathrm{1}\right)\:{n}!\left(\mathrm{1}+\frac{{x}}{\mathrm{1}}+\frac{{x}^{\mathrm{2}} }{\mathrm{2}!}+\frac{{x}^{\mathrm{3}} }{\mathrm{3}!}+...\right)^{{r}} ,\:{i}.{e}.\:\:{n}!{e}^{{rx}} \\ $$$$\left.\mathrm{2}\right)\:{n}!\left(\frac{{x}}{\mathrm{1}}+\frac{{x}^{\mathrm{2}} }{\mathrm{2}!}+\frac{{x}^{\mathrm{3}} }{\mathrm{3}!}+...\right)^{{r}} ,\:{i}.{e}.\:\:{n}!\left({e}^{{x}} −\mathrm{1}\right)^{{r}} \\ $$

Commented by SLVR last updated on 05/Aug/23

Thanks Prof.W...so kind of you

$${Thanks}\:{Prof}.{W}...{so}\:{kind}\:{of}\:{you} \\ $$

Commented by mr W last updated on 05/Aug/23

a little explanation:  say box 1 has k_1  objects, box 2 has k_2   objects, etc. with k_1 +k_2 +...k_r =n and  k_1 ,k_2 ,...,k_r  are fixed values.  to distribute n objects in r boxes in  this way there are ((n!)/((k_1 )!×(k_2 )!×...(k_r )!))  possibilities.  since k_1 ,k_2 ,...,k_r  can be variable values,  we can construct a generating  function like  n!((x/(1!))+(x^2 /(2!))+...+...)^r  if each box must  get at least an object, or  n!(1+(x/(1!))+(x^2 /(2!))+...+...)^r  if each box may  also be empty.    for 1) the formula is r^n .  for 2) the formula is      r^n −C_1 ^r (r−1)^n +C_2 ^r (r−2)^n −...+(−1)^(n−1) C_(r−1) ^r

$${a}\:{little}\:{explanation}: \\ $$$${say}\:{box}\:\mathrm{1}\:{has}\:{k}_{\mathrm{1}} \:{objects},\:{box}\:\mathrm{2}\:{has}\:{k}_{\mathrm{2}} \\ $$$${objects},\:{etc}.\:{with}\:{k}_{\mathrm{1}} +{k}_{\mathrm{2}} +...{k}_{{r}} ={n}\:{and} \\ $$$${k}_{\mathrm{1}} ,{k}_{\mathrm{2}} ,...,{k}_{{r}} \:{are}\:{fixed}\:{values}. \\ $$$${to}\:{distribute}\:{n}\:{objects}\:{in}\:{r}\:{boxes}\:{in} \\ $$$${this}\:{way}\:{there}\:{are}\:\frac{{n}!}{\left({k}_{\mathrm{1}} \right)!×\left({k}_{\mathrm{2}} \right)!×...\left({k}_{{r}} \right)!} \\ $$$${possibilities}. \\ $$$${since}\:{k}_{\mathrm{1}} ,{k}_{\mathrm{2}} ,...,{k}_{{r}} \:{can}\:{be}\:{variable}\:{values}, \\ $$$${we}\:{can}\:{construct}\:{a}\:{generating} \\ $$$${function}\:{like} \\ $$$${n}!\left(\frac{{x}}{\mathrm{1}!}+\frac{{x}^{\mathrm{2}} }{\mathrm{2}!}+...+...\right)^{{r}} \:{if}\:{each}\:{box}\:{must} \\ $$$${get}\:{at}\:{least}\:{an}\:{object},\:{or} \\ $$$${n}!\left(\mathrm{1}+\frac{{x}}{\mathrm{1}!}+\frac{{x}^{\mathrm{2}} }{\mathrm{2}!}+...+...\right)^{{r}} \:{if}\:{each}\:{box}\:{may} \\ $$$${also}\:{be}\:{empty}. \\ $$$$ \\ $$$$\left.{for}\:\mathrm{1}\right)\:{the}\:{formula}\:{is}\:{r}^{{n}} . \\ $$$$\left.{for}\:\mathrm{2}\right)\:{the}\:{formula}\:{is}\: \\ $$$$\:\:\:{r}^{{n}} −{C}_{\mathrm{1}} ^{{r}} \left({r}−\mathrm{1}\right)^{{n}} +{C}_{\mathrm{2}} ^{{r}} \left({r}−\mathrm{2}\right)^{{n}} −...+\left(−\mathrm{1}\right)^{{n}−\mathrm{1}} {C}_{{r}−\mathrm{1}} ^{{r}} \\ $$

Commented by mr W last updated on 05/Aug/23

example:  we have 10 foreign students who  should be distributed to 3 schools.  in how many ways can this be done?  1) 3^(10) =59049 ways  2) 3^(10) −3×2^(10) +3×1^(10) =55980 ways

$${example}: \\ $$$${we}\:{have}\:\mathrm{10}\:{foreign}\:{students}\:{who} \\ $$$${should}\:{be}\:{distributed}\:{to}\:\mathrm{3}\:{schools}. \\ $$$${in}\:{how}\:{many}\:{ways}\:{can}\:{this}\:{be}\:{done}? \\ $$$$\left.\mathrm{1}\right)\:\mathrm{3}^{\mathrm{10}} =\mathrm{59049}\:{ways} \\ $$$$\left.\mathrm{2}\right)\:\mathrm{3}^{\mathrm{10}} −\mathrm{3}×\mathrm{2}^{\mathrm{10}} +\mathrm{3}×\mathrm{1}^{\mathrm{10}} =\mathrm{55980}\:{ways} \\ $$

Commented by mr W last updated on 05/Aug/23

Answered by MM42 last updated on 05/Aug/23

if  n≥r  let  x_i  = number articles in the i^(th)  box  1)⇒ x_1 +x_2 +...+x_r =n  ;  x_i  ≥0  ans= (((n+r−1)),((         n)) )=(((n+r−1)!)/(n!(r−1)!))  2)⇒ x_1 +x_2 +...+x_r =n  ;  x_i  ≥1  ⇒ y_1 +y_2 +...+y_r =n−r  ;  y_i  ≥0  ans= (((n−1)),((n−r)) )=(((n−1)!)/((n−r)!(r−1)!))  if  n<r  then  no all box can be full.

$${if}\:\:{n}\geqslant{r} \\ $$$${let}\:\:{x}_{{i}} \:=\:{number}\:{articles}\:{in}\:{the}\:{i}^{{th}} \:{box} \\ $$$$\left.\mathrm{1}\right)\Rightarrow\:{x}_{\mathrm{1}} +{x}_{\mathrm{2}} +...+{x}_{{r}} ={n}\:\:;\:\:{x}_{{i}} \:\geqslant\mathrm{0} \\ $$$${ans}=\begin{pmatrix}{{n}+{r}−\mathrm{1}}\\{\:\:\:\:\:\:\:\:\:{n}}\end{pmatrix}=\frac{\left({n}+{r}−\mathrm{1}\right)!}{{n}!\left({r}−\mathrm{1}\right)!} \\ $$$$\left.\mathrm{2}\right)\Rightarrow\:{x}_{\mathrm{1}} +{x}_{\mathrm{2}} +...+{x}_{{r}} ={n}\:\:;\:\:{x}_{{i}} \:\geqslant\mathrm{1} \\ $$$$\Rightarrow\:{y}_{\mathrm{1}} +{y}_{\mathrm{2}} +...+{y}_{{r}} ={n}−{r}\:\:;\:\:{y}_{{i}} \:\geqslant\mathrm{0} \\ $$$${ans}=\begin{pmatrix}{{n}−\mathrm{1}}\\{{n}−{r}}\end{pmatrix}=\frac{\left({n}−\mathrm{1}\right)!}{\left({n}−{r}\right)!\left({r}−\mathrm{1}\right)!} \\ $$$${if}\:\:{n}<{r}\:\:{then}\:\:{no}\:{all}\:{box}\:{can}\:{be}\:{full}. \\ $$$$ \\ $$

Commented by mr W last updated on 05/Aug/23

what you solved is for the case that  the objects are identical. but the  question said that both the boxes  and the objects are different.

$${what}\:{you}\:{solved}\:{is}\:{for}\:{the}\:{case}\:{that} \\ $$$${the}\:{objects}\:{are}\:{identical}.\:{but}\:{the} \\ $$$${question}\:{said}\:{that}\:{both}\:{the}\:{boxes} \\ $$$${and}\:{the}\:{objects}\:{are}\:{different}. \\ $$

Commented by MM42 last updated on 08/Aug/23

yes.you are right.i did not notice  the diffrence between the subjects.  thanks for you

$${yes}.{you}\:{are}\:{right}.{i}\:{did}\:{not}\:{notice} \\ $$$${the}\:{diffrence}\:{between}\:{the}\:{subjects}. \\ $$$${thanks}\:{for}\:{you}\: \\ $$$$ \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com