Permutations and Combinations
9. Beggar's Method
9.2. Selection with repetition
Suppose there are unlimited supply of identical Apples, Mangoes, Bananas and Oranges, from this group we want to select only 10 fruits irrespective of their types.
In this question we can take more than one fruit of one kind. We can take all the 10 mangoes, or the 10 apples. Also note that all the apples are identical among them and same is the case with mangoes, bananas, oranges. In all we have to take 10 fruits so
Apples + Oranges + Mangoes + Bananas should be equal to 10.
\( \Rightarrow a + o + m + b = 10\), where \(a,o,m,b \ge 0\)
This is similar to the nonnegative integer solutions of the equation \({x_1} + {x_2} + {x_3} + ...... + {x_r} = n\)
Hence the total number of ways = \(^{n + r - 1}{{\rm{C}}_{r - 1}}\)
Example 01. There is unlimited number of identical red, green, yellow and blue balls. In how many ways 10 balls can be selected so that there is at least one ball of each colour.
In this case since ball are identical, hence it does not matter which ball is selected, what matters is that how many balls are selected. Hence the problem is similar to:
Red + Green + yellow + Blue = 10
Or \(a + b + c + d =10\), where \(a,b,c,d \ge 1\)
We can assume \(a = x + 1,\;b = y + 1,\;c = z + 1,\;d = w + 1\)
\( \Rightarrow x + y + z + w = 6\)
so the number of solutions is \({}^9{{\rm{C}}_3}\)
Red + Green + yellow + Blue = 10
Or \(a + b + c + d =10\), where \(a,b,c,d \ge 1\)
We can assume \(a = x + 1,\;b = y + 1,\;c = z + 1,\;d = w + 1\)
\( \Rightarrow x + y + z + w = 6\)
so the number of solutions is \({}^9{{\rm{C}}_3}\)
Example 02. Find the number of solutions of the equation \(xyz = 1024\), where \(x,y,z\) are natural numbers.
The equation can be written as \(xyz = {2^{10}}\)
Suppose \(x = {2^a},\,\,y = {2^b},\,\,\,z = {2^c}\), where \(a,\;b,\;c \ge 0\)
\( \Rightarrow {2^{a + b + c}} = {2^{10}}\)
Now we have to find the number of nonnegative integer solutions of \(a + b + c = 10\)
Number of solutions = \(^{10 + 3 - 1}{{\rm{C}}_{3 - 1}} = {\,^{12}}{{\rm{C}}_2} = 66\)
Suppose \(x = {2^a},\,\,y = {2^b},\,\,\,z = {2^c}\), where \(a,\;b,\;c \ge 0\)
\( \Rightarrow {2^{a + b + c}} = {2^{10}}\)
Now we have to find the number of nonnegative integer solutions of \(a + b + c = 10\)
Number of solutions = \(^{10 + 3 - 1}{{\rm{C}}_{3 - 1}} = {\,^{12}}{{\rm{C}}_2} = 66\)