×

# 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.

Note by Arron Kau
2 years, 7 months ago

Sort by:

That's a really good note!!! We were taught the same thing, except we call it the "Beggar's Method" ....question states that in how many ways can 10 gold coins be distributed among 4 beggars.... · 2 years, 4 months ago