Solving Combinatorics Problems Using Stars & Bars Concept
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 (very) useful for CAT, GMAT and similar exams.
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.
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
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
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