Permutations and Combinations

9. Beggar's Method

9.1. Distribution of similar objects

Suppose there are 3 identical apples which are to be distributed among three students. In this case since apples are similar hence it does not matter which apple is given to which student, what matters it that how many apples are given to any student. Suppose the three students are A, B and C, then the apples can be distributed in the following 10 ways:


So this distribution is similar to the non-negative integer solutions of the equation \(A + B + C = 3\)

Total number of solutions = \({}^{3 + 3 - 1}{{\rm{C}}_{3 - 1}}\,\,\)= 10 ways.

From the above example we see that distribution of similar objects into distinct groups is similar to number of non-negative integer solution of a linear equation. Sometimes equation needs to be modified or transformed when the variables are nonnegative (for example, odd integers or even integers etc.).

The number of ways in which \(n\) identical things can be distributed into \(r\) different groups if the groups have any number of things from \(0\) to \(n\), is same as number of nonnegative integer solutions of the equation  \({x_1} + {x_2} + {x_3} + ...... + {x_r} = n\)

Required number of ways \( = {}^{n + r - 1}{{\rm{C}}_{r - 1}}\,\,\)

Example 1:

20 identical coins are distributed among 4 beggars. Find the total number of ways of distribution if each beggar gets at least 2 coins. 

Suppose four beggars are \(a, b, c\) and \(d\).The question is similar to find solution of the equation \(a + b + c+ d = 20\), where each \(a, b, c, d\) is more than or equal to 2.
Giving 2 coins to each beggars remaining 12 coins can be distributed according to the formula  \({}^{n + r - 1}{{\rm{C}}_{r - 1}}\)So required number of ways = \({}^{15}{{\rm{C}}_3}\)
Example 2:

There are four different dice, in how many ways sum of their outcomes will be 20.

Let the outcomes are \(x,\;y,\;z\) and \(w\), then
\(x + y + z + w = 20\)
As \(x,y,z,w \le 6\), let us assume \(x = 6 - a,\;y = 6 - b,\;z = 6 - c,\;w = 6 - d\), where \(a,b,c,d \ge 0\)
The equation becomes, \(6 - a + 6 - b + 6 - c + 6 - d = 20\)
\( \Rightarrow a + b + c + d = 4\)
Number of solutions = \(^{{\rm{4 + 4 - 1}}}{{\rm{C}}_{{\rm{4 - 1}}}} = 35\)