In this article we will be discussing one of the most important concepts of Permutation and Combination which is Non Negative and Positive Integral Solutions. In this article we will not only give you the formula but we will also give an insight into the concept so that you can answer different variation of this concept.
Non Negative and Positive Integral Solutions
Let us start the discussion with a question which appeared in CAT 2008.
The question was, Find the number of terms in the expansion of (a + b + c)20
Analyzing the problem
Let’s take smaller examples to understand this problem.
We know (a + b)2 = a2 + 2ab + b2 or a2b0 + 2a1 b1 + a0 b2
similarly we can write, (a + b)3 = a3 b0 + 3 a2 b1 + 3 a1 b2 + b3
Now here in the underlined part we can notice that the sum of the exponents of ‘a’ and that of ‘b’ is 2 in each term for the first equation.
Similarly for the second expression the sum of the powers is 3 in each term.
And we are getting all the possible ways in which the sum can be 2 or 3 respectively. We mean in first case the exponents of ‘a’ and ‘b’ are (2, 0), (1,1) or (0, 2) and for the second equation they are (3, 0); (2, 1); (1.2) and (0,3)
Let us consider the expression (a + b + c)20. If we take an arbitrary term as K x ap x bq x cr then definitely p + q + r = 20.
And the number of terms will depend on how many set of values that are possible (p, q & r) such that their sum is 20. Here p, q and r can be 0 individually so they are basically non-negative integers.
Hence now the question changes to – how many solutions are possible for p + q + r = 20 such that p, q & r are non-negative integers?
Now consider the question –
Amar, Akbar and Anthony are three children and we need to distribute 20 chocolates among them such that each of them can get 0 or more chocolates. In how many ways can we do that?
If I assume that Amar, Akbar and Anthony get p, q and r chocolates respectively then obviously here also p + q + r = 20.
So now we need to find out the number of solutions of this equation where p, q or r can be 0.
Let us put these 20 chocolates on a straight line as shown in the figure 1. Now to divide them among three people we can put two barriers between any two chocolates.
For the 2nd figure the barriers (in terms of vertical lines) are placed in between 1st and 2nd chocolate and 2nd one is in between 7th and 8th chocolates.
So we can say that Akbar gets 1 chocolate (C1), Akbar gets 6 chocolates (C2 to C7) and Anthony gets 13 chocolates (C8 to C20).
For another example we can see in the 3rd figure that the distribution is 0, 20 (C1 to C20) and 0.
To explain if we put the barriers in between C5 & C6 and in between C10 and C11 then the set of values we have (5, 5, 10). (Not given in the figure).
Now for each arrangement of the barriers we get one set of solutions.
So now we are just arranging 20 identical chocolates and 2 identical barriers which can be done in 22!/ 2! x 20! ways which is 22C2.
The number of barriers is always 1 less than the number of people so we can say if we divide n chocolates among r people then r – 1 barriers are needed so our answer becomes n + r – 1Cr – 1.
Hence for non-negative integral solution of a + b + c + … r terms = n the number of solutions is given by n + r – 1Cr – 1.
Now if the question asks – Amar, Akbar and Anthony and we need to distribute 20 chocolates among them such that each of them can get 1 or more chocolates. In how many ways can we do that?
Then we should look for positive integral solutions. So we can give 1 chocolate to each of them so we are left with n – r chocolates to be distributed among r people and hence the answer would be (n – r)+ r – 1Cr – 1 or n – 1Cr – 1.
So remembering only one formula would help you to find out answers for both cases.
The article has been written by Subhankar Dhar, your own Mentor for Quant, DI and LR at Career Anna.
You may also prepare with us at our CAT PREP FACEBOOK GROUP.