Math Question and Answers


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 158955 by mr W last updated on 11/Nov/21

	Answered by mr W last updated on 15/Nov/21
	$let′s look at the general case with n students into r schools. both students (objects) and schools (boxes) are distinct. let′s say the school S_1 obtains n_1 students, the schools S_2 obtains n_2 students, etc. n_1 +n_2 +n_3 +...+n_r =n 1) no restriction: n_1 ≥0, n_2 ≥0, etc. 2) each schools obtains at least one student: n_1 ≥1, n_2 ≥1, etc. to distribute n students into r schools such that S_1 obtains n_1 students, S_2 obtains n_2 students, etc. and S_r obtains n_r students, there are C_n_1 ^n C_n_2 ^(n−n_1 ) ...C_n_r ^(n−n_1 −n_2 −...−n_(r−1) ) ways, which is ((n!)/(n!(n−n_1 )!))×(((n−n_1 )!)/(n_2 !(n−n_1 −n_2 )!))×...×(((n−n_1 −n_2 −...−n_(r−1) )!)/(n_r !0!)), i.e. ((n!)/(n_1 !n_2 !n_3 !...n_r !)) ways. using generating function method we can see that for case 1) number of ways is the coef. of x^n in n!(1+(x/(1!))+(x^2 /(2!))+(x^3 /(3!))+...)^r =n!(e^x )^r =n!e^(rx) =n!(1+((rx)/(1!))+((r^2 x^2 )/(2!))+((r^3 x^3 )/(3!))+...) coef. of x^n is n!×(r^n /(n!))=r^n . that means there are r^n ways to distribute n students into r schools without restriction. for case 2) number of ways is the coef. of x^n in n!((x/(1!))+(x^2 /(2!))+(x^3 /(3!))+...)^r =n!(e^x −1)^r =n!Σ_(k=0) ^r (−1)^k C_k ^r (e^x )^(r−k) =n!Σ_(k=0) ^r {(−1)^k C_k ^r [1+(((r−k)x)/(1!))+(((r−k)^2 x^2 )/(2!))+...]} the coef. of x^n is n!Σ_(k=0) ^r [(−1)^k C_k ^r (((r−k)^n )/(n!))] =Σ_(k=0) ^r (−1)^k C_k ^r (r−k)^n = r^n −C_1 ^r (r−1)^n +C_2 ^r (r−2)^n −...+(−1)^(r−1) C_(r−1) ^r$
	${l e t}^{'} s l o o k a t t h e g e n e r a l c a s e w i t h n$ $s t u d e n t s i n t o r s c h o o l s . b o t h s t u d e n t s$ $(o b j e c t s) a n d s c h o o l s (b o x e s) a r e$ $d i s t i n c t .$ ${l e t}^{'} s s a y t h e s c h o o l S_{1} o b t a i n s n_{1}$ $s t u d e n t s, t h e s c h o o l s S_{2} o b t a i n s n_{2}$ $s t u d e n t s, e t c .$ $n_{1} + n_{2} + n_{3} + . . . + n_{r} = n$ $1) n o r e s t r i c t i o n : n_{1} ⩾ 0, n_{2} ⩾ 0, e t c .$ $2) e a c h s c h o o l s o b t a i n s a t l e a s t o n e$ $s t u d e n t : n_{1} ⩾ 1, n_{2} ⩾ 1, e t c .$ $t o d i s t r i b u t e n s t u d e n t s i n t o r s c h o o l s$ $s u c h t h a t S_{1} o b t a i n s n_{1} s t u d e n t s,$ $S_{2} o b t a i n s n_{2} s t u d e n t s, e t c . a n d$ $S_{r} o b t a i n s n_{r} s t u d e n t s, t h e r e a r e$ $C_{n_{1}}^{n} C_{n_{2}}^{n - n_{1}} . . . C_{n_{r}}^{n - n_{1} - n_{2} - . . . - n_{r - 1}} w a y s,$ $w h i c h i s$ $\frac{n!}{n! (n - n_{1})!} \times \frac{(n - n_{1})!}{n_{2}! (n - n_{1} - n_{2})!} \times . . . \times \frac{(n - n_{1} - n_{2} - . . . - n_{r - 1})!}{n_{r}! 0!},$ $i . e . \frac{n!}{n_{1}! n_{2}! n_{3}! . . . n_{r}!} w a y s .$ $u s i n g g e n e r a t i n g f u n c t i o n m e t h o d$ $w e c a n s e e t h a t$ $Missing \left or extra \right$ $n u m b e r o f w a y s i s t h e c o e f . o f x^{n} i n$ $n! {(1 + \frac{x}{1!} + \frac{x^{2}}{2!} + \frac{x^{3}}{3!} + . . .)}^{r}$ $= n! {(e^{x})}^{r}$ $= n! e^{r x}$ $= n! (1 + \frac{r x}{1!} + \frac{r^{2} x^{2}}{2!} + \frac{r^{3} x^{3}}{3!} + . . .)$ $c o e f . o f x^{n} i s n! \times \frac{r^{n}}{n!} = r^{n} .$ $t h a t m e a n s t h e r e a r e r^{n} w a y s t o$ $d i s t r i b u t e n s t u d e n t s i n t o r s c h o o l s$ $w i t h o u t r e s t r i c t i o n .$ $Missing \left or extra \right$ $n u m b e r o f w a y s i s t h e c o e f . o f x^{n} i n$ $n! {(\frac{x}{1!} + \frac{x^{2}}{2!} + \frac{x^{3}}{3!} + . . .)}^{r}$ $= n! {(e^{x} - 1)}^{r}$ $= n! \underset{k = 0}{\sum^{r}} {(- 1)}^{k} C_{k}^{r} {(e^{x})}^{r - k}$ $= n! \underset{k = 0}{\sum^{r}} {{(- 1)}^{k} C_{k}^{r} [1 + \frac{(r - k) x}{1!} + \frac{{(r - k)}^{2} x^{2}}{2!} + . . .]}$ $t h e c o e f . o f x^{n} i s$ $n! \underset{k = 0}{\sum^{r}} [{(- 1)}^{k} C_{k}^{r} \frac{{(r - k)}^{n}}{n!}]$ $= \underset{k = 0}{\sum^{r}} {(- 1)}^{k} C_{k}^{r} {(r - k)}^{n}$ $= r^{n} - C_{1}^{r} {(r - 1)}^{n} + C_{2}^{r} {(r - 2)}^{n} - . . . + {(- 1)}^{r - 1} C_{r - 1}^{r}$
	Commented by Tawa11 last updated on 11/Nov/21

	$Great sir .$
	Commented by mr W last updated on 11/Nov/21

	$e x a m p l e : 10 s t u d e n t s i n t o 5 s c h o o l s$ $n = 10, r = 5$ $1) n o r e s t r i c t i o n$ $n u m b e r o f w a y s = 5^{10} = 9 765 625$ $2) a t l e a s t o n e s t u d e n t i n e a c h s c h o o l$ $n u m b e r o f w a y s i s$ $5^{10} - 4^{10} C_{1}^{5} + 3^{10} C_{2}^{5} - 2^{10} C_{3}^{5} + C_{4}^{5}$ $= 5^{10} - 5 \times 4^{10} + 10 \times 3^{10} - 10 \times 2^{10} + 5$ $= 5 103 000$
	Commented by otchereabdullai@gmail.com last updated on 12/Nov/21

	$more blessing prof!$
Terms of Service
Privacy Policy
Contact: info@tinkutara.com

Question and Answers Forum