Permutations and Combinations
9. Beggar's Method
Beggar's Method (non-negative integer solutions)
The problem statement of the type
"In how many ways can \(n\) identical coins be distributed among \(r\) beggars" is called the beggar's problem. We have the choice of not giving any coin to a particular beggar, meaning each beggar may or may not
receive any coins. Thus, this problem is analogous to finding non-negative integer solutions for \[x_1 + x_2 + x_3 + ... + x_r = n\]Let's consider a small example, consider a simple equation \(x + y + z = 3\), then the total number of non-negative integer solutions can be obtained by simple counting.
But if the equation has more variables or the value of the constant is larger, it will be difficult to count all the solutions manually. By using Binomial expansion, we obtain a simplified result to find the non-negative number of solutions of
\({x_1} + {x_2} + {x_3} + ..... + {x_r} = n\)
Where \({x_1},\,{x_2},\,{x_3},\,.......,{x_r} \ge 0\)
Total number of solutions is \({}^{n + r - 1}{{\rm{C}}_{r - 1}}\). This formula can be applied for solving various types of questions directly or indirectly based on it.
Sometimes all the variables are not nonnegative, in such cases the variables can be transformed into new variables so the new variables are all nonnegative, consider the following example.
\({x_1} + {x_2} + {x_3} + ..... + {x_r} = n\)
Here all the variable \({x_1},\,{x_2},\,{x_3},\,.......,{x_r}\) are natural numbers. Let us make a transformation \({x_i} = {a_i} + 1\)
So the equation in the new variables becomes,
\(({a_1} + 1) + ({a_2} + 1) + ({a_3} + 1) + ..... + ({a_r} + 1) = n\)
\( \Rightarrow {a_1} + {a_1} + {a_3} + ...... + {a_r} = n - r\)
Now note that all \({a_1},\,{a_2},\,{a_3},\,\,.......,\,{a_r} \ge 0\), so we can apply the formula and thus the required number of solutions is
\({}^{(n - r) + r - 1}{{\rm{C}}_{r - 1}} = {}^{n - 1}{{\rm{C}}_{r - 1}}\)
Example 01:If \(a + b + c =100\), find the number of solutions when
(i) \(a, b, c\) are non negative integers.
(ii) \(a, b, c\) are positive integers.
(ii) If \(a, b, c\) are positive integers, let \(a = x + 1,b = y + 1, c = z + 1\) so that even if \(x, y, z\) are zero, \(a, b, c\) will be positive.
Now the equation becomes \(x + 1 + y + 1 + z + 1=100\) or \(x + y + z = 97\)
Total number of solutions = \({}^{99}{{\rm{C}}_2}\)
Find the number of integer solutions of \(|{x_1}| + |{x_2}| + |{x_3}| + ....|{x_r}| = n\)
As each can be positive or negative, hence number of solutions = \(\left( {{2^r}} \right){\,^{n - 1}}{C_{r - 1}}\)
Now assume, exactly one of them is 0, then number of solutions is \(\left( {{2^{r - 1}}} \right){\,^r}{C_1}\,{\,^{n - 1}}{C_{r - 2}}\)
Now assume, exactly two of them are 0, then number of solutions is \(\left( {{2^{r - 2}}} \right){\,^r}{C_2}\,{\,^{n - 1}}{C_{r - 3}}\)
And so on.
Final answer is \(\sum\limits_{k = 0}^r {^r{C_k}\left( {^{n - 1}{C_{r - k - 1}}} \right){2^{r - k}}} \)