Permutations Combinations.: Distribution of Alike objects

QUESTION 1: In how many ways 8 identical one rupee coins can be distributed among 3 beggars?

SOLUTION: To solve this question we will take 1 simple analogy. So solving this question is equivalent to finding the number of ways of putting vertical lines among the given 8 identical one rupee coins.

Let us understand few such ways with help of following cases.

Case 1

Suppose we decide to give 1 coin to first beggar, 3 coins to second beggar and 4 coins to the third beggar respectively .This distribution is equivalent to putting 2 vertical lines among the given 8 identical coins as shown in diagram below (where each 1 rupee coin is denoted by O  and vertical lines denoted by  I )

O             I               O             O             O             I               O             O             O             O

Putting 2 vertical lines is equivalent distributing coins among 3 beggars as

Portion to the Left of 1^st line denotes the number of coins which 1^st beggar got i.e. only 1 in this case

Portion between 1^st and 2^nd line denotes the number coins which 2^nd beggar got i.e. 3 in this case

Portion after 2^nd line denotes the number coins which 2^nd beggar got i.e. 4 in this case

Case 2

Suppose we decide  not to give any coin to first beggar, 2 coins to second beggar and 6 coins to the third beggar respectively .This distribution is equivalent to putting 2 vertical lines among the given 8 identical coins as shown in diagram below (where each 1 rupee coin is denoted by O  and vertical lines denoted by  I )

I               O             O             I               O             O             O             O             O             O

Putting 2 vertical lines is equivalent distributing coins among 3 beggars as

Portion to the Left of 1^st line denotes the number coins which 1^st beggar got i.e. zero in this case

Portion between 1^st and 2^nd line denotes the number coins which 2^nd beggar got i.e. 2 in this case

Portion after 2^nd line denotes the number coins which 2^nd beggar got i.e. 6 in this case

Case 3

Suppose we decide  not to give any coin to first beggar and second beggar and 8 coins to the third beggar respectively .This distribution is equivalent to putting 2 vertical lines among the given 8 identical coins as shown in diagram below (where each 1 rupee coin is denoted by O  and vertical lines denoted by  I )

I               I               O             O             O             O             O             O             O             O

Putting 2 vertical lines is equivalent distributing coins among 3 beggars as

Portion to the Left of 1^st line denotes the number coins which 1^st beggar got i.e. zero in this case

Portion between 1^st and 2^nd line denotes the number coins which 2^nd beggar got i.e. zero in this case

Portion after 2^nd line denotes the number coins which 2^nd beggar got i.e. 8 in this case

So clearly many such cases are possible and each of the above diagram corresponds to one of the way of giving 8 identical coins  to 3 beggars .So now let us focus on the similarity between all the above diagrams ,In short all the above diagrams contain 2 vertical lines and 8 coins written in different orders

I I OOOOOOOO

And the number of ways of writing any alphabet with first 2 letters and last 8 letters same=

Thus number of ways of distributing 8 identical one rupee coins among 3 beggars =

Generalization

Number of ways in which n identical things can be distributed into r different groups or

Number of ways in which n identical one rupee coins can be distributed among r beggars

is equivalent to finding the number of ways of putting  (r – 1 ) vertical lines among  n identical

one rupee coins.

QUESTION 2: Find the number of non negative integer solutions of the equation X + Y + Z = 8 ?

Solution: This question is same as the question we solved above

Note that all X , Y,  Z ≥ 0 and all are integers.

Here 8 on the right hand side represents the number of coins and X , Y and Z represents  3 beggars . Lets us take the same cases which we took in previous example all these can be solutions of the above equations

1+ 3+ 4= 8

0 +2 +6 = 8

0+ 0+ 8 = 8

And many more such cases are possible. So clearly the number of non negative integer solutions of the equation X + Y + Z = 8 is same as the number of  ways 8 identical one rupee coins can be distributed among 3 beggars =

The same question can be asked in following format also

3. In how many ways 8 identical balls can be distributed into 3 different boxes so that no box remains empty?

4. Three boys picked up 8 oranges. In how many ways can they divide them if all oranges be identical?

QUESTION 5:Find the number of positive integer solutions of the equation X + Y + Z = 8?

Solution:

This question is almost same but constraints are different i.e. X , Y,  Z > 0

Or we can write X≥ 1, Y≥ 1, Z ≥ 1

Again the question is analogous to distributing 8 identical coins to three beggars

But here the condition is every beggar should have atleast 1 coin so we will distribute 1 coin to each beggar in advance.

So giving 1 coin to each beggar means we donated 3 coins. Thus we are left with 5 coins which we have to distribute among 3 beggars which can be done in

QUESTION 6: Find the number of integral solutions of the equation X + Y + Z +W = 20 where X≥ 1 ,

Y≥ 2, Z >0 , W ≥ 3?

Solution: This question is almost same but constraints are different i.e. X≥ 1 , Y≥ 2, Z >0 ,W ≥ 0

Again the question is analogous to distributing 20 identical coins to four beggars But here the condition is 1^st beggar should have atleast 1 coin, 2^nd beggar should have atleast 2 coin , 3^rdbeggar should have more than zero coin which is same as saying that he should have atleast 1 coin, and 4^th beggar should have atleast 3 coinsSo we will give 1 coin to 1^st beggar ,2 coins to 2^nd beggar ,1 coin to 3^rd beggar and 3 coins to 4^th beggar first. So giving 1 coin to each beggar means we donated 3 coins. Thus we are left with 5 coins which we have to distribute among 3 beggars which can be done in

QUESTION 7:How many non negative integral solutions are there to the system of equations

X + Y + Z +W + K = 20 and W+ K = 7 ?

Solution: Putting the value of  W+ K = 7 in

X + Y + Z +W + K = 20 when each of X≥ 0 , Y≥ 0  ,Z ≥ 0  ,W≥ 0 ,K≥ 0

We get  X + Y + Z  = 13

Solving this equation is same as distributing 13 Identical coins among 3 beggars which can be done in

Similarly solving equation W+ K = 7  where  W≥ 0 ,K≥ 0 equivalent to distributing 7 Identical coins among 2 beggars which can be done in

Thus the total number of solutions to the system of equations is = 8 x 105=840

QUESTION 8:Find the number of non negative integral solutions of 2X + Y + Z = 18

Solution

The questions which we did till now had coefficient one but this has coefficient two. For the time being we put x =k so equation becomes

2K + Y +Z = 18

Y + Z = 18 – 2k                                                                    (1)

As per the given constraint we are given Y ≥ 0 and Z ≥ 0 .

Thus Y + Z ≥ 0

=>           18 – 2k≥ 0

=>                     k≤ 9

Now as far as solving equation (1) is concerned we very well know it is equivalent to distributing 18 – 2k coins among 2 beggars

= 18- 2k + 1 = 19 – 2k ways

But k varies from 0 to 9.Thus total number of ways

Q 9:Find the number of  distinct terms in the expansion of (x+ y+ z)⁸ ?

Solution: After expansion of this expression it is clear that collective degree of each term is 8

In general terms will be of the form

x^a y^b z^c where a+ b + c = 8 and each of a , b and c is greater than or equal to zero

Thus again this question reduces to distributing 8 coins to 3 beggars which can be done

 = 45 ways

Q10:Find the number of non negative integral solutions of the equation X + Y + Z ≤18 ?

Solution

Given equation can be written as

X + Y + Z + W = 18 where each of X, Y, Z and W is greater than or equal to zero

Thus reduces to distributing 18 coins to 4 beggars which can be done

Hence the number of non-negative integral solutions of the equation X + Y + Z ≤ 18 are 1330.

Q 11:Find the number of non negative integral solutions of the equation as X + Y + Z < 20 ?

Solution

Given equation can be written as

X + Y + Z + W = 20 where X≥ 0 , Y≥ 0  ,Z ≥ 0  and W> 0

Or we can write it as X≥ 0 , Y≥ 0  ,Z ≥ 0  ,W≥ 1

Thus reduces to distributing 20 coins to 4 beggars such that each of the 1^st three beggars get zero or more than zero coin but 4rth beggar should get atleast 1 coin.

This can be done in

Hence the number of non negative integral solutions of the equation

X + Y + Z < 20 are 1540 .

Questions for practise

Q1 Find the number of non – negative integral solutions of 2x + y + z = 21?

Ans 132

Q2 Four boys picked up 30 oranges. In how many ways can they divide them if all oranges be identical?

Ans 5456

Q3 In how many ways 20 identical balls can be distributed into 4 different boxes so that no box remains empty?

Ans 969

Q4.How many non negative integral solutions are there to the system of equations

X + Y + Z +W + K = 20 and Z+W+ K = 5 ?

Ans 336

Q5 In how many ways 16 identical mangoes can be distributed among 4 personsif none gets less than 3 mangoes?

Ans 35

P&C : Distribution of alike objects

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)ⁿ = 1+ nx + n(n–1)/2! x² + . . . + n(n–1)…(n–r+1)/r! x^r + … terms upto ∞

(B). General term of the series (1+x)^-n = T_r+1 = (-1)^r x^r n(n+1)(n+2)…(n+r–1)/r! x^r

(C). General term of the series (1-x)^-n = T_r+1 = n(n+1)(n+2)…(n+r–1) / r! x^r

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 x³ in the expansion of (x⁰+ x¹+ x²+ x³) (x⁰+ x¹+ x²+ x³)

Now clearly terms containing x³ will be obtained by multiplying

x⁰. x³, x¹. x², x². x¹, x³. x⁰,

which clearly corresponds to solutions obtained in equation  (1)

i.e .We can clearly see now calculating coefficient of x³ in the expansion of

(x⁰+ x¹+ x²+ x³) (x⁰+ x¹+ x²+ x³) is equivalent to distributing 3 identical coins to 2 beggars

NOTE

As per coin beggar story  we looked at coefficient of x³ in expansion of

(x⁰+ x¹+ x²+ x³) (x⁰+ x¹+ x²+ x³)

(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 xⁿ in the expansion of

(x⁰+ x¹+ x²+ x³+……………….+ xⁿ) (x⁰+ x¹+ x²+ x³+……………….+ xⁿ) …………………………………………(x⁰+ x¹+ x²+ x³+……………….+ xⁿ)  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 x¹⁴ in the expansion of (x¹+ x²+ x³+ ………..+ x⁶)

(x¹+ x²+ x³+ ………..+ x⁶) (x¹+ x²+ x³+ ………..+ x⁶)

= Coefficient of x¹⁴ in the expansion of (x¹+ x²+ x³+ ………..+ x⁶)³

= Coefficient of x¹⁴ in the expansion of   x³(1+x¹+ x²+ ………..+ x⁵)³

= Coefficient of x^14-3 in the expansion of (1+x¹+ x²+ ………..+ x⁵)³

= Coefficient of x¹¹ in the expansion of

(As 1, x, x²….x⁵ are in G.P.)

= Coefficient of x¹¹ in the expansion of (1 -3 )(1+ 3x + 6x²+ ………..+21 x⁵+……78x¹¹+…..)

=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 x¹⁵ in the expansion of product of (x¹+ x²+ x³+ ………..+ x¹⁰)

(x²+ x³+ ………..+ x¹⁰)(x³+ x⁴+ ………..+ x¹⁰)(x⁴+ x⁵+ ………..+ x¹⁰)

= Coefficient of x^{15 –(1+2+3+4)} in the expansion of (1+ x+ x²+ ………..+ x⁹)

(1+ x+ x²+ ………..+ x⁸)( 1+ x+ x²+ ………..+ x⁷)(1+ x+ x²+ ………..+ x⁶)

= Coefficient of x⁵ in the expansion of (1+ x+ x²+ ………..+ x⁹)

(1+ x+ x²+ ………..+ x⁸)( 1+ x+ x²+ ………..+ x⁷)(1+ x+ x²+ ………..+ x⁶)

Neglecting the higher powers i.e. powers which are greater than x⁵

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 x_i denotes the number of chocolates received by  i th kid then as per the given condition

X₁ + x₂ + x₃ + x₄ + x₅ +  x₆ + x₇ =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 x_i 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

x₁ + x₂ + x₃ =15 where x₁ ≥ 1, x₂≥ 1, x₃≥ 1 s.t. x₁ ,x₂ and x₃ are unequal.

Since we have to find unequal integral solutions of above equation so

without loss of generality we can assume x₁ < x₂ < x₃

Let x₁= x  , x₂= x +y ,  x₃=  x₂+ z= x +y+ z

Putting the values of x₁ ,x_{2 ,} x₃ 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 x¹⁵ in the expansion of product of

(x³+ x⁶+ x⁹ +………..)(x²+ x⁴+ x⁶ +………..)(x¹+ x²+ x³+ ………..)

(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 x^{15 –(3 + 2+1)} in the expansion of product of

( 1+x³+ x⁶+ ………..)( 1+x²+ x⁴+ ………..)(1+x¹+ x²+ ………..)

=Coefficient of x⁹ in the expansion of product of

( 1+x³+ x⁶+ x⁹ )( 1+x²+ x⁴+ x⁶ +x⁸ )(1+x¹+ x²+ x³+ x⁴+ x⁵+ x⁶+ x⁷+ x⁸+ x⁹)

(After neglecting powers higher than x⁹)

= Coefficient of x⁹ in the expansion of product of

(1+x³+ x⁶+ x⁹ +x²+ x⁵ +x⁸+x¹¹+ x⁴+ x⁷+ x¹⁰+ x¹³+ x⁶+ x⁹+ x¹²+ x¹⁵+x⁸+ x¹¹+ x¹⁴

+ x¹⁷)(1+x¹+ x²+ x³+ x⁴+ x⁵+ x⁶+ x⁷+ x⁸+ x⁹)

=(1+x²+x³+ x⁴+x⁵ + 2x⁶+ x⁷+2x⁸+2 x⁹ + x¹⁰+2x¹¹+ x¹²+  x¹³+ x¹⁴+  x¹⁵+ x¹⁷)(1+x¹+ x²+ x³+ x⁴+ x⁵+ x⁶+ x⁷+ x⁸+ x⁹)

=2+2+1+2+1+1+1+1+1+1

=12

But x₁ ,x_2, x₃ 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 x₁ A`s ,  x<sub>2</sub> B`s and  x₃ C`s be selected

We have

x₁ + x₂ + x₃ =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

x₁ + x₂ + x₃ + x₄ =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