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