# 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
4 years, 2 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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

- 4 years ago

There is another way of tackling such a problem. a,b,c,d are non-negative integers. To ensure they are positive integers, adding 1 to each of them gives a+b+c+d=14. Now consider the 14 as a list of '1's. To get the number of ways of getting the ordered sets a,b,c,d we can partition the 14 by placing 3 lines in the gaps between the '1's. There are 13 gaps, so we have rephrased the problem - How many ways are there of choosing 3 gaps from 13 gaps. This yields 13 choose 3 = 286 (Apologies for the lack of LaTeX).

- 3 years, 6 months ago