Waste less time on Facebook — follow Brilliant.
×

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

No vote yet
1 vote

Comments

Sort by:

Top Newest

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.... Tanya Gupta · 2 years, 11 months ago

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). Mukul Rathi · 2 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...