Distribution of alike objects is probably one of the most daunting topics when it comes to permutations and combinations. There is a certain number of objects which are alike among a certain number of individuals/objects fulfilling certain conditions. You can read the second part here.
The question goes something like: there are 10 similar Buzz Lightyear toys to be distributed among 3 children. In how many ways can you do it?
The easy way to visualize this is to put two sticks among the Buzz Lightyear action figures and distribute the toys accordingly
So, in the above case, we can see that the first kid gets 1 action figure, second kid gets 3 action figures and the third kid gets 6 action figures. Essentially, we have to arrange 10 similar action figures and 2 similar sticks into as many combinations as are possible.
This can be done in:
Another way to look at it is to find out the number of integral solutions to the equation
a + b + c = 10
This is given by 12C2 = 66 ways.
The key term here is the non-negative part. It essentially means that this formula will test for all the possible integral solutions from 0 till n for each of the variables and come up with the total number of viable solutions.
There are a few type of questions from this topic that are important. We shall cover it in the course of these two articles:
1) Non negative solutions
2) Positive solutions
3) Non-unit coefficients
4) Less than n
5) Less than or equal to n
6) Special variables
Non negative solutions
Like we saw in the above question, the number of non-negative solutions to the equation will be given by
So, if there are say 20 watches to be given to 10 people without any condition whatsoever, the distribution can be done in 29C9 ways.
This is a simple extension of the above case. The only thing that has to be done is to give away one object even before the distribution starts. For example: if there are 10 Buzz Lightyear action figures to be distributed among 3 kids such that each kid gets at least one action figure in how many ways can this be done?
So, we give 1 action figure to each kid right before the actual distribution takes place. Now, all 3 kids have 1 action figure each and we are left with 7 action figures to be distributed among 3 kids without any conditions. So, effectively, we have to find the number of non-negative integral solutions to a + b + c = 7 which is nothing but 9C2 = 36 ways.
It is important to remember why the number of solutions is lesser than what it was without any restriction. We are essentially eliminating all the cases where in one or more of a, b and c is/are 0.
You can try out these questions
If there are 10 Buzz Lightyear action figures to be distributed among 3 kids Arun, Barun and Kiranmala such that Arun gets at least one action figure, in how many ways can this be done?
If there are 10 Buzz Lightyear action figures to be distributed among 3 kids Arun, Barun and Kiranmala such that Arun and Kiranmala gets at least one action figure, in how many ways can this be done?
In all the questions that we have seen above, we were trying to find out the solutions to equations in which, the variables did not have anything except 1 as the coefficient. In other words, if we have to find out the number of integral solutions to a + 2b + c = 15, we will have to proceed in the following manner.
b can vary from 0 to 7
when b = 0, a + c = 15, so 16 solutions
when b = 1, a + c = 13, so 14 solutions
when b = 2, a + c = 11, so 12 solutions
when b = 3, a + c = 9, so 10 solutions
when b = 4, a + c = 7, so 8 solutions
when b = 5, a + c = 5, so 6 solutions
when b = 6, a + c = 3, so 4 solutions
when b = 7, a + c = 1, so 2 solutions
Total number of solutions is 2 + 4 + 6 … + 16 = 72 ways
With practice, you can actually skip the number of solutions set and directly find the answer. Let’s see it with an example:
What is the number of non-negative integral solutions to 3a + b + c = 30?
a varies from 0 to 10. The corresponding solutions to b + c will be 31, 29, 27, … 1. Sum of the solutions will be equal to sum of first 16 odd numbers which is 162 = 256 solutions in total.
The only problem in this area is a lack of awareness when it comes to the various scenarios. Many get tricked into applying one method for the other and end up in a mess. Practice is the key to these type of questions and the more scenarios you are open to, the better you will become. Another important bit is to read the question very carefully and not miss out on the subtle clues.
Do let us know in case you want us to cover any topic in detail. All the best!