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

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.

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.

No vote yet

1 vote

Easy Math Editor

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:

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in`\(`

...`\)`

or`\[`

...`\]`

to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

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

Log in to reply

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

Log in to reply