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

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

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

- 7 years, 2 months 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).

- 6 years, 7 months ago