Distribution of ‘n’ identical objects into ‘m’ numbers of distinct groups.
PODCAST ON DISTRIBUTION OF OBJECTS INTO GROUPS
Let us consider distribution of n identical objects to m numbers of distinct groups.
let $\,x_i \,$ is the number of identical object objects in $i^{th}\, $ group.
Therefore $x_1\,+\,x_2\,+\,x_3……….\,+\,x_m\,=\,n\,\,\, ;\,\,\, where\,\, 0\leq x_i\leq n \,,\,\,\, \forall i=1,2,3,……..m $
Hence number of non negative integral solution of equation will be the number ways in which n identical objects can be distributed into m numbers of groups .
The number of solutions is Coefficient of $x^n\,$ in the expansion of $ (1+x+x^2+………+x^n)^m $
=Coefficient of $ x^n $ in the expansion of $ (1-x)^{-m}\,\, =\, {n+m-1 \choose n} $
Hence number of distribution = $ {n+m-1 \choose n} $
Distribution of n identical objects into m numbers of groups such none of the group remain empty.
Total number of solutions will be positive integral solution of equation of equation
$ x_1+x_2+x_3…………..+x_m\,=\,n \,\,\, 1\leq x_i \leq n \,\, \forall i=1,2,3……n $
let $ x_i\,=\,y_i\,+1\,\,\,\, therefore\,\, y_i\geq 0 \,\,\, \forall x_i \geq 1. $
Therefore number of distribution will be number of non negative solution of equation
$ y_1+y_2+y_3…………..+y_m\,=\,n\,-\,m \,\,\, 0\leq y_i \leq n-1 \,\, \forall i=1,2,3……n $
Hence Number of solutions are $ {(n-m)+m-1 \choose (n-m)}\,=\,{n\,-\,1 \choose n-m} $
Applications of distribution of identical objects
Question 1. Find the number of ways in which 10 identical blankets can be distributed to 5 beggars.
Answer :::: Here n =10 , m = 5 Hence $ {14 \choose 10} $
To study the distribution of Distinct objects into groups click here
Question 2 . Find coefficient of $x^5$ in the expansion of $(\,x^2\,-\,x\,+\,1\,)^4$.
Answer :::: General term in the expansion of $(\,x^2\,-\,x\,+\,1\,)^4$ is
$T_{(r_1,\,r_2,\,r_3)}=\frac{4!}{{r_1}!{r_2}!{r_3}!}\,(x^2)^{r_1}\,(-x)^{r_2}\,(1)^{r_3} $
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,=(-1)^{r_2}\,\frac{4!}{{r_1}!{r_2}!{r_3}!}\,x^{(2{r_1}\,+\,{r_2})} $
For Coefficient of $x^5$
$2{r_1}\,+\,r_2\,=\,5$ and $\,\,r_1\,+\,r_2\,+\,r_3\,=\,4$
Hence $(\,r_1\,,r_2\,,r_3\,)$ = ( 1 , 3 , 0 ) and ( 2 ,1 ,1 )
Therefore Coefficient of $x^5$ is = $\,\frac{4!}{1!\,3!\,0!}\,(-1)^3\,+\,\frac{4!}{2!\,1!\,1!}\,(-1)^1 $ $\\$ $= -6$
Question 3. Find number of ways in which from n or more number of identical object of 1 type , n or more number of identical object of 2 nd type and …. n or more number of identical object of m th type , exactly n can be selected.
Answer :::: Here also number of ways will be number of non negative solution of equation
$$x_1+x_2+x_3……..x_m=n$$
Where $x_i$ denotes number of i th objects taken in a selection.
And number of selection will be $${n+m-1 \choose n }$$
Question 4: Find the number of ways 4 persons from 12 sitting around a circular table be selected such that no two of them are neghibour.
Answer :::: let persons selected are A,B,C,D and $X_1\,,\,X_2\,,\,X_3\,,\,X_4$ be number of persons between A,B ; B,C ; C,D ; D,A respectively.
Hence $1\le X_i\le 8\,\,\, \forall i=1,2,3,4$
Number of selection will be number of integral solution of equation $$X_1+X_2+X_3+X_4=8$$
$$Let\,\,\,X_i=Y_i+1\,\,\,\,where\,\,\, 0\le Y_i \le 7 $$
Hence Number of selection is number of non negative solution of equation $$Y_1+Y_2+Y_3+Y_4=4$$
$$\therefore Solutions ={7 \choose 4}=35 $$
Question 5. Find the number of ways in which 12 people can be arranged around the circular table so that particular 4 persons A, B, C and D are not together.
Answer :::: Number of ways in which 8 other than A , B , C and D can be arranged around the circular table is 7! And between these 8 . A , B , C and D be arranged in $^8P_4$.
Hence total number of ways$$ =( 7! )(^8P_4)$$.