Stars and Bars

We discuss a combinatorial counting technique known as stars and bars. Consider the following problem.

Problem: How many ordered sets of non-negative integers $(a, b, c, d)$ are there such that $a + b + c + d = 10$?

It may be tempting to list every possible combination of non-negative integers in an ordered fashion. However, this method of listing does not work easily for much larger numbers.

Technique

Step 1: First, we will create a bijection between solutions to $a+b+c +d = 10$ with sequences of length 13 that consist of 10 $1$'s and 3 $0$'s. What this means is that we want to associate each solution with a unique sequence, and vice versa.

The construction is straightforward. Given a set of 4 integers $(a, b, c, d)$, we create the sequence that starts with $a$ $1$'s, then has a $0$, then has $b$ $1$'s, then has a $0$, then has $c$ $1$'s, then has a $0$, then has $d$ $1$'s. For example, if $(a, b, c, d) = (1, 4, 0, 2)$, then the associated sequence is $1 0 1 1 1 1 0 0 1 1$ . Now, if we add the restriction that $a + b + c + d = 10$, the associated sequence will consist of 10 $1$'s (from $a, b, c, d$) and 3 $0$'s (from our manual insert), hence have total length 13.

Conversely, given a sequence of length 13 that consists of 10 $1$'s and 3 $0$'s, set $a$ equal to the length of the initial string of $1$'s (before the first $0$), set $b$ equal to the length of the next string of 1's (between the first and second $0$), set $c$ equal to the length of the third string of $1$'s (between the second and third $0$), and set $d$ equal to the length of the last string of $1$'s (after the third $0$). Then, this yields a solution $a + b + c + d = 10$.

It is clear that the constructions associate a solution with a unique sequence, and vice versa. Hence we have a bijection.

Step 2: Now, it remains to count the number of solutions. Since we have a bijection with the sequences, it is equivalent to count the number of sequences of length 13 that consist of 10 $1$'s and 3 $0$'s.

First, let us assume that the $0$'s are distinct, say of the form $0_1, 0_2, 0_3$ . Then, in a sequence of length 13, there are 13 ways we could place $0_1$. After which, there are 13-1 ways we could place $0_2$. After which, there are 13-2 ways we could place $0_3$. Now, the rest of the sequence have to be $1$'s, and clearly there is only 1 way to do so. By the rule of product, this will yield $13 \times (13-1) \times (13-2) \times 1$ ways.

However, we have double counted many times, since the $0$'s are actually the same. There are 6 ways ( $0_1 0_2 0_3, 0_1 0_3 0_2, 0_2 0_1 0_3$, $0_2 0_3 0_1, 0_3 0_1 0_2, 0_3 0_2 0_1$ ) to arrange the 'distinct' $0$'s. Thus, each actual sequence would have been counted 6 times, so to get the actual number of ways, we will have to divide by 6.

Hence, there are $13 \times (13-1) \times (13 - 2 ) \times 1 \div 6 =286$ solutions.

Note: Students who are familiar with combinatorics should realize from the above argument that there are ${13 \choose 3} = 286$ solutions.