Distribution of alike objects
In last article, we found that number of ways in which n identical things can be distributed into r different groups is equivalent to distributing n identical one rupee coins among r beggars when each beggar can get zero or more coins .The number of ways of doing this is
We should know few basics regarding binomial theorem before solving difficult problems of combination with repetition
Binomial theorem for general index
(A). (1+x)n = 1+ nx + n(n–1)/2! x2 + . . . + n(n–1)…(n–r+1)/r! xr + … terms upto ∞
(B). General term of the series (1+x)-n = Tr+1 = (-1)r xr n(n+1)(n+2)…(n+r–1)/r! xr
(C). General term of the series (1-x)-n = Tr+1 = n(n+1)(n+2)…(n+r–1) / r! xr
Coin – beggar analogy worked well as the questions which we did had only one constraint that is number of coins are bounded below by some constant. But what if, we have questions involving 2 sided constraints.
Before going into that, let us understand distribution of identical objects once again mathematically also with help of example below
Example : Find the number of ways of distributing 3 identical coins to 2 beggars?
Solution:
By previous article we know the number of ways of doing this is same as finding non negative integral solutions of the equation
a+ b = 3 where each of a and b is greater than or equal to zero and the number of ways are
Or infact we could have directly calculated possible solutions are
0 + 3,1+2,2+1,3+0 are the 4 possible solutions (1)
Let us try to analyze it some other way
We try calculating coefficient of x3 in the expansion of (x0+ x1+ x2+ x3) (x0+ x1+ x2+ x3)
Now clearly terms containing x3 will be obtained by multiplying
x0. x3, x1. x2, x2. x1, x3. x0,
which clearly corresponds to solutions obtained in equation (1)
i.e .We can clearly see now calculating coefficient of x3 in the expansion of
(x0+ x1+ x2+ x3) (x0+ x1+ x2+ x3) is equivalent to distributing 3 identical coins to 2 beggars
NOTE
As per coin beggar story we looked at coefficient of x3 in expansion of
(x0+ x1+ x2+ x3) (x0+ x1+ x2+ x3)
(i.e. they were multiplied only twice as number of beggars were only two)
Powers of x varies from 0 to 3 which shows that every beggar can get minimum zero and can get atmost 3 coins.
GENERALISATION:
Now we say , distributing n identical one rupee coins among r beggars when each beggar can get zero or more coins equals
Coefficient of xn in the expansion of
(x0+ x1+ x2+ x3+……………….+ xn) (x0+ x1+ x2+ x3+……………….+ xn) …………………………………………(x0+ x1+ x2+ x3+……………….+ xn) upto r times
{i.e. they were multiplied r times as number of beggars equals r and
Powers of x varies from 0 to n which shows that every beggar can get minimum zero and can get atmost n coins }
Note
So as per coin beggar story powers of x varies from 0 to n shows that every beggar can get zero or more coins and can get at most n coins(which was obvious as total number coins were n only).But lets see some problems which we cannot solve directly by coin beggar story
Let us cover few more difficult problems involving two sided constraints i.e. number of coins which each beggar has is bounded below and bounded above also.
QUESTION 1:
In how many ways can 3 persons, each throwing a single dice to have a total score of 14?
SOLUTION:
Let us relate this question to the story of beggars we learnt in previous article.In this, we have to distribute 14 coins to 3 beggars under the condition that each beggar should have atleast 1 coin and atmost 6 coins.Solving this question directly would be difficult as no of coins which each beggar should have is bounded by lower and upper constraint i.e.
1≤no of coins with each beggar ≤ 6
So we solve mathematically by saying that this is equivalent to calculating
= Coefficient of x14 in the expansion of (x1+ x2+ x3+ ………..+ x6)
(x1+ x2+ x3+ ………..+ x6) (x1+ x2+ x3+ ………..+ x6)
= Coefficient of x14 in the expansion of (x1+ x2+ x3+ ………..+ x6)3
= Coefficient of x14 in the expansion of x3(1+x1+ x2+ ………..+ x5)3
= Coefficient of x14-3 in the expansion of (1+x1+ x2+ ………..+ x5)3
= Coefficient of x11 in the expansion of
(As 1, x, x2….x5 are in G.P.)
= Coefficient of x11 in the expansion of (1 -3 )(1+ 3x + 6x2+ ………..+21 x5+……78x11+…..)
=78-21(3)
=15
QUESTION 2:
An Examination has four papers A,B,C and D .Each paper has maximum of 10 marks .Find the number of ways in which student can score 15 marks in the examination if a student is required to score atleast 1 mark from paper A, atleast 2 marks from paper B, atleast 3 marks from paper C, atleast 4 marks from paper D ?
SOLUTION:
So as per our story we have to distribute 20 coins to four beggars in such a way that
1≤no of coins with beggar A≤15
2≤no of coins with beggar B≤15
3≤no of coins with beggar C≤15
4≤no of coins with beggar D≤15
So keeping above conditions in mind, mathematically it is equivalent to calculating
Coefficient of x15 in the expansion of product of (x1+ x2+ x3+ ………..+ x10)
(x2+ x3+ ………..+ x10)(x3+ x4+ ………..+ x10)(x4+ x5+ ………..+ x10)
= Coefficient of x15 –(1+2+3+4) in the expansion of (1+ x+ x2+ ………..+ x9)
(1+ x+ x2+ ………..+ x8)( 1+ x+ x2+ ………..+ x7)(1+ x+ x2+ ………..+ x6)
= Coefficient of x5 in the expansion of (1+ x+ x2+ ………..+ x9)
(1+ x+ x2+ ………..+ x8)( 1+ x+ x2+ ………..+ x7)(1+ x+ x2+ ………..+ x6)
Neglecting the higher powers i.e. powers which are greater than x5
QUESTION 3:
In how many ways Santa Claus can distribute 28 chocolates to 7 kids giving not less than 3 chocolates to any kid?
SOLUTION:
If Santa gives 3 chocolates each to six kids then the number of chocolates received by the seventh kid=28 – 3(6)= 10
If xi denotes the number of chocolates received by i th kid then as per the given condition
X1 + x2 + x3 + x4 + x5 + x6 + x7 =28 and each 3 ≤ 10 where i = 1,2,3……….7
So as per our story we have to distribute 28 coins to seven beggars in such a way that any beggar can have atleast 3 and atmost 10 chocolates. Mathematically it is equivalent to calculating
QUESTION 4:
Find the number of ways of distributing 15 balls in three boxes in such a way that each box contains at least 1 ball and also the number of balls in each box are unequal ?
Solution:
Let xi denote the number of balls in the i th box where i varies from 1 to 3.
We can put it in the form of equation as
x1 + x2 + x3 =15 where x1 ≥ 1, x2≥ 1, x3≥ 1 s.t. x1 ,x2 and x3 are unequal.
Since we have to find unequal integral solutions of above equation so
without loss of generality we can assume x1 < x2 < x3
Let x1= x , x2= x +y , x3= x2+ z= x +y+ z
Putting the values of x1 ,x2 , x3 in the given equation we get
x + x +y+ x +y+ z = 15
3x + 2y + z = 15
Number of positive integral solutions of equation
=Coefficient of x15 in the expansion of product of
(x3+ x6+ x9 +………..)(x2+ x4+ x6 +………..)(x1+ x2+ x3+ ………..)
(Because since x varies from 1 ,2,3,4………….. Therefore 3x varies from 3 ,6,9,12…………..Similarly since y varies from 1 ,2,3,4………….. Therefore 2y varies from 2 ,4,6,8…………..)
=Coefficient of x15 –(3 + 2+1) in the expansion of product of
( 1+x3+ x6+ ………..)( 1+x2+ x4+ ………..)(1+x1+ x2+ ………..)
=Coefficient of x9 in the expansion of product of
( 1+x3+ x6+ x9 )( 1+x2+ x4+ x6 +x8 )(1+x1+ x2+ x3+ x4+ x5+ x6+ x7+ x8+ x9)
(After neglecting powers higher than x9)
= Coefficient of x9 in the expansion of product of
(1+x3+ x6+ x9 +x2+ x5 +x8+x11+ x4+ x7+ x10+ x13+ x6+ x9+ x12+ x15+x8+ x11+ x14
+ x17)(1+x1+ x2+ x3+ x4+ x5+ x6+ x7+ x8+ x9)
=(1+x2+x3+ x4+x5 + 2x6+ x7+2x8+2 x9 + x10+2x11+ x12+ x13+ x14+ x15+ x17)(1+x1+ x2+ x3+ x4+ x5+ x6+ x7+ x8+ x9)
=2+2+1+2+1+1+1+1+1+1
=12
But x1 ,x2, x3 can be arranged in 3! ways.
Hence required number of solutions is (12)(3!)=72
QUESTION 5:
How many natural numbers between 1 and 10000 have sum of digits as 12?
Solution:
Any number between 1 and 10000 will be four digit number hence it must be of the form `abcd`
where each of a , b ,c and d varies from 0 to 9
i.e. 0≤ a,b,c ,d≤9
QUESTION 6:
Find the number of ways in which 30 letters can be selected from 20 A`s , 20 B`s and 20 C`s ?
Solution
Let x1 A`s , x2 B`s and x3 C`s be selected
We have
x1 + x2 + x3 =30 where 0 ≤ x_1,x_2,x_3≤20
Thus the number of ways
Questions for practice
Q1 Find the number of positive unequal integral solution of the equation
x1 + x2 + x3 + x4 =20 ?
Ans 552
Q2 How many natural numbers between 1 and 10000 have sum of digits as 12?
Ans 25927
Q3 In how many ways can 3 persons, each throwing a single dice to have a total score of 11?
Ans 27
Q4 . In how many different ways can 30 chocolates be distributed to 10 children if each child should have atleast two chocolates?
Ans
Q5 Find the number of ways in which 24 letters can be selected from 16 A`s , 16 B`s and 16 C`s ?
Ans 217
