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) (a, b, c, d) are there such that a+b+c+d=10 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 a+b+c +d = 10 with sequences of length 13 that consist of 10 1 1's and 3 0 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) (a, b, c, d) , we create the sequence that starts with a a 1 1's, then has a 0 0, then has b b 1 1's, then has a 0 0, then has c c 1 1's, then has a 0 0, then has d d 1 1's. For example, if (a,b,c,d)=(1,4,0,2) (a, b, c, d) = (1, 4, 0, 2) , then the associated sequence is 1011110011 1 0 1 1 1 1 0 0 1 1 . Now, if we add the restriction that a+b+c+d=10 a + b + c + d = 10 , the associated sequence will consist of 10 1 1's (from a,b,c,d a, b, c, d) and 3 0 0's (from our manual insert), hence have total length 13.

Conversely, given a sequence of length 13 that consists of 10 1 1's and 3 0 0's, set a a equal to the length of the initial string of 1 1's (before the first 0 0), set b b equal to the length of the next string of 1's (between the first and second 0 0), set c c equal to the length of the third string of 1 1's (between the second and third 0 0), and set d d equal to the length of the last string of 1 1's (after the third 0 0). Then, this yields a solution a+b+c+d=10 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 1's and 3 0 0's.

First, let us assume that the 0 0's are distinct, say of the form 01,02,03 0_1, 0_2, 0_3 . Then, in a sequence of length 13, there are 13 ways we could place 01 0_1. After which, there are 13-1 ways we could place 02 0_2. After which, there are 13-2 ways we could place 03 0_3. Now, the rest of the sequence have to be 1 1's, and clearly there is only 1 way to do so. By the rule of product, this will yield 13×(131)×(132)×1 13 \times (13-1) \times (13-2) \times 1 ways.

However, we have double counted many times, since the 0 0's are actually the same. There are 6 ways ( 010203,010302,020103 0_1 0_2 0_3, 0_1 0_3 0_2, 0_2 0_1 0_3, 020301,030102,030201 0_2 0_3 0_1, 0_3 0_1 0_2, 0_3 0_2 0_1 ) to arrange the 'distinct' 0 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×(131)×(132)×1÷6=286 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 (133)=286 {13 \choose 3} = 286 solutions.

Note by Arron Kau
5 years, 8 months ago

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:

  • 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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

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 - 5 years, 6 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 - 4 years, 12 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...