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 105551 by mr W last updated on 29/Jul/20

In how many different ways can 10 students be divided into 3 groups?

$${In}\:{how}\:{many}\:{different}\:{ways}\:{can}\:\mathrm{10} \\ $$$${students}\:{be}\:{divided}\:{into}\:\mathrm{3}\:{groups}? \\ $$

Answered by adhigenz last updated on 29/Jul/20

It is the same thing as finding how many possible integer solution for a+b+c = 10, which a,b,c ≥ 1, since a certain group must contain at least 1 student. Let x = a−1, y = b−1, z = c−1 We write the equation as: x+y+z = 7, for x,y,z ≥ 0 The solution of integer is (((n+r−1)),(( r−1)) ) = (((7+3−1)),(( 3−1)) ) = ((9),(2) ) = 36 ways

$$\mathrm{It}\:\mathrm{is}\:\mathrm{the}\:\mathrm{same}\:\mathrm{thing}\:\mathrm{as}\:\mathrm{finding}\:\mathrm{how} \\ $$$$\mathrm{many}\:\mathrm{possible}\:\mathrm{integer}\:\mathrm{solution}\:\mathrm{for} \\ $$$$\mathrm{a}+\mathrm{b}+\mathrm{c}\:=\:\mathrm{10},\:\mathrm{which}\:\mathrm{a},\mathrm{b},\mathrm{c}\:\geqslant\:\mathrm{1},\:\mathrm{since}\:\mathrm{a} \\ $$$$\mathrm{certain}\:\mathrm{group}\:\mathrm{must}\:\mathrm{contain}\:\mathrm{at}\:\mathrm{least}\:\mathrm{1} \\ $$$$\mathrm{student}. \\ $$$$\mathrm{Let}\:{x}\:=\:{a}−\mathrm{1},\:{y}\:=\:{b}−\mathrm{1},\:{z}\:=\:{c}−\mathrm{1} \\ $$$$\mathrm{We}\:\mathrm{write}\:\mathrm{the}\:\mathrm{equation}\:\mathrm{as}: \\ $$$${x}+{y}+{z}\:=\:\mathrm{7},\:\mathrm{for}\:{x},{y},{z}\:\geqslant\:\mathrm{0} \\ $$$$\mathrm{The}\:\mathrm{solution}\:\mathrm{of}\:\mathrm{integer}\:\mathrm{is}\:\begin{pmatrix}{{n}+{r}−\mathrm{1}}\\{\:\:\:\:{r}−\mathrm{1}}\end{pmatrix} \\ $$$$=\:\begin{pmatrix}{\mathrm{7}+\mathrm{3}−\mathrm{1}}\\{\:\:\:\:\mathrm{3}−\mathrm{1}}\end{pmatrix} \\ $$$$=\:\begin{pmatrix}{\mathrm{9}}\\{\mathrm{2}}\end{pmatrix} \\ $$$$=\:\mathrm{36}\:\mathrm{ways} \\ $$

Commented by mr W last updated on 30/Jul/20

i don′t think both are the same thing. 10 students are distinct, say they are A,B,C,D,E,F,G,H,I,J. so for example A,B,C,D/E,F,G/H,I,J and A,B,C,E/D,F,G/H,I,J are two different ways.

$${i}\:{don}'{t}\:{think}\:{both}\:{are}\:{the}\:{same}\:{thing}. \\ $$$$\mathrm{10}\:{students}\:{are}\:{distinct},\:{say}\:{they}\:{are} \\ $$$${A},{B},{C},{D},{E},{F},{G},{H},{I},{J}. \\ $$$${so}\:{for}\:{example} \\ $$$${A},{B},{C},{D}/{E},{F},{G}/{H},{I},{J} \\ $$$${and} \\ $$$${A},{B},{C},{E}/{D},{F},{G}/{H},{I},{J} \\ $$$${are}\:{two}\:{different}\:{ways}. \\ $$

Answered by 1549442205PVT last updated on 30/Jul/20

Consider a way of division into 3 groups such that:one group of two,one group of two ,one group of six.Since for first two persons we have C_(10) ^2 ways to choose, for next two persons have C_8 ^2 ways to choose but because two −person repeated .Hence all have (( C_(10) ^2 ×C_8 ^2 )/2)=45×14=530 ways.Similarly,for way of division (2,3,5) we have C_(10) ^2 ×C_8 ^3 =45×56=2520 ways iii)For (2,4,4)have ((C_(10) ^2 ×C_8 ^4 )/2)=45.35=1575 iv)For (3,3,4)have ((C_(10) ^3 ×C_7 ^3 )/2)=60.35=2100 Thus,total we have 530+2520+1575+2100 =6725 ways to divide 10 student into three groups.

$$ \\ $$$$\mathrm{Consider}\:\mathrm{a}\:\mathrm{way}\:\mathrm{of}\:\mathrm{division}\:\mathrm{into}\:\mathrm{3}\:\mathrm{groups} \\ $$$$\mathrm{such}\:\mathrm{that}:\mathrm{one}\:\mathrm{group}\:\mathrm{of}\:\mathrm{two},\mathrm{one}\:\mathrm{group} \\ $$$$\mathrm{of}\:\mathrm{two}\:,\mathrm{one}\:\mathrm{group}\:\mathrm{of}\:\mathrm{six}.\mathrm{Since}\:\mathrm{for}\:\mathrm{first} \\ $$$$\mathrm{two}\:\mathrm{persons}\:\mathrm{we}\:\mathrm{have}\:\mathrm{C}_{\mathrm{10}} ^{\mathrm{2}} \:\mathrm{ways}\:\mathrm{to}\:\mathrm{choose}, \\ $$$$\mathrm{for}\:\mathrm{next}\:\mathrm{two}\:\mathrm{persons}\:\mathrm{have}\:\mathrm{C}_{\mathrm{8}} ^{\mathrm{2}} \:\mathrm{ways}\:\mathrm{to}\: \\ $$$$\mathrm{choose}\:\mathrm{but}\:\mathrm{because}\:\mathrm{two}\:−\mathrm{person}\:\mathrm{repeated} \\ $$$$.\mathrm{Hence}\:\mathrm{all}\:\mathrm{have}\:\frac{\:\mathrm{C}_{\mathrm{10}} ^{\mathrm{2}} ×\mathrm{C}_{\mathrm{8}} ^{\mathrm{2}} }{\mathrm{2}}=\mathrm{45}×\mathrm{14}=\mathrm{530} \\ $$$$\:\mathrm{ways}.\mathrm{Similarly},\mathrm{for}\:\mathrm{way}\:\mathrm{of}\:\mathrm{division} \\ $$$$\left(\mathrm{2},\mathrm{3},\mathrm{5}\right)\:\mathrm{we}\:\mathrm{have}\:\mathrm{C}_{\mathrm{10}} ^{\mathrm{2}} ×\mathrm{C}_{\mathrm{8}} ^{\mathrm{3}} =\mathrm{45}×\mathrm{56}=\mathrm{2520}\:\mathrm{ways} \\ $$$$\left.\mathrm{iii}\right)\mathrm{For}\:\left(\mathrm{2},\mathrm{4},\mathrm{4}\right)\mathrm{have}\:\frac{\mathrm{C}_{\mathrm{10}} ^{\mathrm{2}} ×\mathrm{C}_{\mathrm{8}} ^{\mathrm{4}} }{\mathrm{2}}=\mathrm{45}.\mathrm{35}=\mathrm{1575} \\ $$$$\left.\mathrm{iv}\right)\mathrm{For}\:\left(\mathrm{3},\mathrm{3},\mathrm{4}\right)\mathrm{have}\:\frac{\mathrm{C}_{\mathrm{10}} ^{\mathrm{3}} ×\mathrm{C}_{\mathrm{7}} ^{\mathrm{3}} }{\mathrm{2}}=\mathrm{60}.\mathrm{35}=\mathrm{2100} \\ $$$$\mathrm{Thus},\mathrm{total}\:\mathrm{we}\:\mathrm{have}\:\mathrm{530}+\mathrm{2520}+\mathrm{1575}+\mathrm{2100} \\ $$$$=\mathrm{6725}\:\mathrm{ways}\:\mathrm{to}\:\mathrm{divide}\:\mathrm{10}\:\mathrm{student}\:\mathrm{into} \\ $$$$\mathrm{three}\:\mathrm{groups}. \\ $$

Commented by mr W last updated on 30/Jul/20

but a group may also have only one student.

$${but}\:{a}\:{group}\:{may}\:{also}\:{have}\:{only}\:{one} \\ $$$${student}. \\ $$

Commented by 1549442205PVT last updated on 30/Jul/20

If such as then adding i)(1,1,8)have ((C_(10) ^1 ×C_9 ^1 )/2)=45 ways ii)(1,2,7)have C_(10) ^1 ×C_9 ^2 =10.36=360 ways iii)(1,3,6)have C_(10) ^1 ×C_9 ^3 =10.84=840 ways iv)(1,4,5)have C_(10) ^1 ×C_9 ^4 =10.126=1260 ways S=45+360+840+1260+6725=9230 ways

$$\mathrm{If}\:\mathrm{such}\:\mathrm{as}\:\mathrm{then}\:\mathrm{adding} \\ $$$$\left.\mathrm{i}\right)\left(\mathrm{1},\mathrm{1},\mathrm{8}\right)\mathrm{have}\:\frac{\mathrm{C}_{\mathrm{10}} ^{\mathrm{1}} ×\mathrm{C}_{\mathrm{9}} ^{\mathrm{1}} }{\mathrm{2}}=\mathrm{45}\:\mathrm{ways} \\ $$$$\left.\mathrm{ii}\right)\left(\mathrm{1},\mathrm{2},\mathrm{7}\right)\mathrm{have}\:\mathrm{C}_{\mathrm{10}} ^{\mathrm{1}} ×\mathrm{C}_{\mathrm{9}} ^{\mathrm{2}} =\mathrm{10}.\mathrm{36}=\mathrm{360}\:\mathrm{ways} \\ $$$$\left.\mathrm{iii}\right)\left(\mathrm{1},\mathrm{3},\mathrm{6}\right)\mathrm{have}\:\:\mathrm{C}_{\mathrm{10}} ^{\mathrm{1}} ×\mathrm{C}_{\mathrm{9}} ^{\mathrm{3}} =\mathrm{10}.\mathrm{84}=\mathrm{840}\:\mathrm{ways} \\ $$$$\left.\mathrm{iv}\right)\left(\mathrm{1},\mathrm{4},\mathrm{5}\right)\mathrm{have}\:\:\mathrm{C}_{\mathrm{10}} ^{\mathrm{1}} ×\mathrm{C}_{\mathrm{9}} ^{\mathrm{4}} =\mathrm{10}.\mathrm{126}=\mathrm{1260}\:\mathrm{ways} \\ $$$$\boldsymbol{\mathrm{S}}=\mathrm{45}+\mathrm{360}+\mathrm{840}+\mathrm{1260}+\mathrm{6725}=\mathrm{9230} \\ $$$$\boldsymbol{\mathrm{ways}} \\ $$

Commented by mr W last updated on 30/Jul/20

typo in result for (2,2,6): 45×14=630 instead of 530! then you get S=9330 this is correct, nice work sir!

$${typo}\:{in}\:{result}\:{for}\:\left(\mathrm{2},\mathrm{2},\mathrm{6}\right):\:\mathrm{45}×\mathrm{14}=\mathrm{630} \\ $$$${instead}\:{of}\:\mathrm{530}!\: \\ $$$${then}\:{you}\:{get}\:{S}=\mathrm{9330} \\ $$$${this}\:{is}\:{correct},\:{nice}\:{work}\:{sir}! \\ $$

Commented by mr W last updated on 30/Jul/20

the coefficient of x^(10) term from generating function ((10!)/(3!))(e^x −1)^3 is 9330.

$${the}\:{coefficient}\:{of}\:{x}^{\mathrm{10}} \:{term}\:{from} \\ $$$${generating}\:{function} \\ $$$$\frac{\mathrm{10}!}{\mathrm{3}!}\left({e}^{{x}} −\mathrm{1}\right)^{\mathrm{3}} \:{is}\:\mathrm{9330}. \\ $$

Commented by mr W last updated on 30/Jul/20

Commented by 1549442205PVT last updated on 30/Jul/20

Thank you Sir!You are welcome.

$$\mathrm{Thank}\:\mathrm{you}\:\mathrm{Sir}!\mathrm{You}\:\mathrm{are}\:\mathrm{welcome}. \\ $$

Commented by mr W last updated on 31/Jul/20

number of ways to place n distinct objects in k identical boxes is {_k ^n } which is the stirling number of the second kind. {_k ^n }=S_2 (n,k) {_3 ^(10) }=9330.

$${number}\:{of}\:{ways}\:{to}\:{place}\:{n}\:{distinct} \\ $$$${objects}\:{in}\:{k}\:{identical}\:{boxes}\:{is}\:\left\{_{{k}} ^{{n}} \right\} \\ $$$${which}\:{is}\:{the}\:{stirling}\:{number}\:{of}\:{the} \\ $$$${second}\:{kind}.\: \\ $$$$\left\{_{{k}} ^{{n}} \right\}={S}_{\mathrm{2}} \left({n},{k}\right) \\ $$$$\left\{_{\mathrm{3}} ^{\mathrm{10}} \right\}=\mathrm{9330}. \\ $$

Commented by mr W last updated on 31/Jul/20

Terms of Service

Privacy Policy

Contact: info@tinkutara.com