Finding Number of Positive & Non-Negative Integral Solutions For a + b + c + ... = N & Its Applications

[zabeer]

The concept which we will discuss in this note is a simple and useful tactic for solving seemingly complicated problems in combinations and counting. Very useful for CAT, GMAT and similar exams.

Concept -
How many ways are there are to put n indistinguishable balls into k distinguishable bins ?
case 1: n and k are positive integers = (n - 1) C (k - 1)
case 2: n and k are non negative integers = (n + k - 1) C (k - 1)

This is neatly explained in Wikipedia (Thanks Wikipedia!), so I will use the same to explain the logic and afterwards we will solve enough problems to get a good understanding of the concept and various application of it in our exams.

Case 1:

Suppose one has n objects (to be represented as stars; in the example below n = 7) to be placed into k bins (in the example k = 3), such that all bins contain at least one object; one distinguishes the bins (say they are numbered 1 to k) but one does not wish to distinguish the n stars (so configurations are only distinguished by the number of stars present in each bin). Instead of starting to place stars into bins, one starts by placing the stars on a line:

★ ★ ★ ★ ★ ★ ★

where the stars for the first bin will be taken from the left, followed by the stars for the second bin, and so forth. Thus the configuration will be determined once one knows what is the first star going to the second bin, and the first star going to the third bin, and so on. One can indicate this by placing k − 1 separating bars at some places between two stars; since no bin is allowed to be empty, there can be at most one bar between a given pair of stars:

★ ★ ★ ★ | ★ | ★ ★ ( two bars give rise to three bins containing 4, 1, and 2 objects)

Thus one views the n stars as fixed objects defining n − 1 gaps, in each of which there may or not be one bar (bin partition). One has to choose k − 1 of them to actually contain a bar; therefore there are (n - 1)C(k - 1) possible configurations

case 2:

In this case, the representation as a sequence of stars and bars, with the bars dividing the stars into bins, is unchanged. The weakened restriction of non-negativity (instead of positivity) means that one may place multiple bars between two stars, as well as placing bars before the first star or after the last star. So the below arrangement is allowed

★ ★ ★ ★ | | ★ | ★ ★ | (four bars give rise to five bins containing 4, 0, 1, 2, and 0 objects)

Total arrangements in this scenario is given as (n + k - 1)C(k - 1)

We will solve some problems using this concept

Number of solutions of a + b + c + d = 22, (a, b, c and d are Natural numbers)

This problem want us to put 22 items into 4 bins (a, b, c and d) where every bin has a positive number of items (Case 1)

This can be done in (22 - 1) C ( 4 - 1) = 21C3 ways.

Number of solutions of a + b + c + d = 12 (a, b, c and d ≥ 0 )

This problem want us to put 12 items into 3 bins where every bin can have either zero or all of the items (Case 2)

This can be done in (12 + 4 - 1)C(4 - 1) = 15C3 ways.

Number of solutions for the inequality x + y + z ≤ 10 where, x, y and z are non-negative integers.

The trick here is the ≤ symbol instead of =. How to solve such questions ?

x + y + z ≤ 10

can be written as x + y + z + d = 10, where d is a dummy variable.

Why we need a dummy variable here ? it is like we are dividing 10 items into 4 baskets and the fourth dummy basked (d) will ensure x, y and z would together have ≤ 10 always. If d = 0, x + y + z = 10 and if d = 10, x + y + z = 0 --> covering all the possible values for x + y + z which are ≤ 10.

so the answer here is (10 + 4 - 1) C (4 - 1) = 13C3 ways

Number of ways of getting a sum of 12 when rolling 3 dice simultaneously?

Let a, b and c be the numbers we obtained for each dice

So we have a + b + c = 12

Also, we know 0 < a, b and c < = 6

So If we go with case 1, where a, b and c > 0
Number of ways = 11 C 2 = 55 ways

But this includes invalid cases like a = 10, b = 1 and c = 1. How to remove them ?
now let a = A + 6 ( to find the occurrence of values above 6 for a)

A + b + c = 6
number of ways = 5C2 = 10 ways

Same needs to be performed for b and c also. So we have to remove 3 x 10 = 30 ways from the total.

Finally, our answer is 55 - 30 = 25

Find the number of ways in which we can get a sum less than or equal to 17 by throwing six distinct dice.

a + b + c + d + e + f ≤ 17
a , b, c ... f can take values from 1 to 6

Because of ≤, add a dummy variable. (say, g)
so we have a + b + c + d + e + f + g = 17

Now we will discuss a very important point. a, b, c .. f are all natural numbers and for g - 0 is possible. Means this is neither in case 1 or case 2. To resolve this let subtract 1 from a, b, c .. f so that they can be given a value of 0 also. so this will fall under case 2. Our equation becomes
a + b + c + d + e + f +g = 17 - 6 = 11
Number of ways = (11 + 7 - 1) C (7 - 1) = 17C6

[Note - Here, idea is when we do a + b + c + ... it should be either all positive or all non negative (which includes zero). You cannot have both in the same equation. What we did before was to make all as whole numbers and we can also make all as natural numbers too. Both should give the same result. For a better understanding will do in the other way too (all natural numbers)
So we need to make g as positive. how ?
we define g = G - 1 where G is always positive
if you see here, g can still be zero when G is 1 but G is always > 0 just like a, b, ... f and now our equation is good for Case 1.
so a + b + c + d + e + f + G - 1 = 17
a + b + c + d + e + f + G = 18
Number of solutions (case 1 here) = (18 - 1)C(7 - 1) = 17C6]

now we have to remove cases where a > 6.
say a = A + 6
So, A + b + c + d + e + f + g = 11 - 6 = 5
Number of ways which a can be higher than 6 (invalid cases for a) = 11C6 ways.
6 x 11C6 invalid cases if we include for b, c, d, e and f also.

Our answer = total ways - invalid cases
17C6 - 6 x 11C6

How many 3 digits numbers have sum of its digit as 15.

This is just like throwing 3 dice to get a sum 15, where the values can range from 0 to 9 (not 6)

a + b + c = 15
Number of solutions = ( 15 + 3 - 1) C (3 - 1) = 17C2 = 136

as a, b and c cannot be more than 10, we need to take it into consideration.
a = A + 10
A + b + c = 5
number of solutions = (5 + 3 - 1) C (3 - 1) = 7C2 = 21
Considering for b and c, we have to reduce 21 x 3 = 63 from total.

136 - 63 = 73

a cannot be 0 (else it won't be a 3 digit number)
so we need to remove (0, 7, 8); (0, 8, 7); (0, 9, 6) and (0, 6, 9) from the list.
So final solution = 73 - 4 = 69

Find out the natural number solutions for 5x + 12y = 600

600 is divisible by both 5 and 12. So x should be of the form 12a and y should be of the form 5b.
We can write the above equation as 60a + 60b = 600
a + b = 10
9C1 = 9 solutions.

How many ways can we write the number 45 as the product of 3 natural numbers ?

45 = a * b * c
45 = 3^2 * 5
Let say, a = 3^p * 5^q
b = 3^m * 5^n
c = 3^x * 5^y

a * b * c = 3^(p + m + x) * 5^(q + n + y) = 3^2 * 5
p + m + x = 2 --> 4C2 = 6 ways
q + n + y = 1 --> 3C2 = 3 ways

So total 6 * 3 = 18 ways.

Remember, we need to find the whole number solutions as p, m, x, q, n and y can be 0.

How many ways can we write the number 45 as the product of 3 integers ?
(credits : @sibanand_pattnaik)

Case 1 : 45 = a * b * c (all positive)
We already solved it as 18 ways

Case 2 : 45 = a * b * c (two numbers negative)
We can have 3 cases for each of the 18 triplets we got from case 1. Which are (-a, -b, c), (a, -b, -c) and (-a, b, -c)
So total 18 * 3 = 54 ways.

So Total ways to represent 45 as the product of 3 integers = 18 + 54 = 72 ways