Discrete Math · Undergraduate

Stars and Bars: Combinations with Repetition

Quick answer

Sharing n identical objects among k people, or counting nonnegative integer solutions of x₁ + … + xₖ = n, is the same as arranging n stars and k − 1 bars in a row. The bars split the stars into k groups, so the count is C(n + k − 1, k − 1). If every group must get at least one, hand one to each first and count the rest, giving C(n − 1, k − 1). The same count gives the number of ways to choose n items from k types when repeats are allowed and order does not matter.

What you'll learn

  • Model a distribution problem with stars and bars
  • Count nonnegative integer solutions of x₁ + … + xₖ = n
  • Handle lower bounds by giving out the minimum first
  • Count selections with repetition

Stars for objects, bars for walls

To share 1010 identical candies among 33 kids, line up 1010 stars and 22 bars. The bars cut the row into 33 groups, read left to right:

⋆⋆⋆∣⋆⋆⋆⋆⋆∣⋆⋆means 3+5+2\star\star\star \mid \star\star\star\star\star \mid \star\star \qquad \text{means } 3 + 5 + 2

Every way of placing the bars is one sharing, and every sharing is one placement. With nn objects and kk groups, there are n+k−1n + k - 1 symbols and we choose where the k−1k - 1 bars go:

(n+k−1k−1)\binom{n + k - 1}{k - 1}

If each group must get at least one, the count is (n−1k−1)\binom{n - 1}{k - 1}.

Why the bars capture every case

A sharing is fully described by how many objects each group gets. In the row, the stars before the first bar are group 11‘s, the stars between the bars are group 22‘s, and so on. Two bars side by side mean an empty group. Reading the row gives the sharing, and writing the sharing as stars and bars gives the row, so the two are counted by the same number. Counting rows is a combination: choose k−1k - 1 of the n+k−1n + k - 1 spots for bars.

Worked examples

Common mistakes

Practice problems

  1. In how many ways can 55 identical balls go into 33 boxes?

    Answer

    2121

    Full solution

    (72)=21\binom{7}{2} = 21.

  2. In how many ways can 77 identical cookies go to 44 kids?

    Answer

    120120

    Full solution

    (103)=120\binom{10}{3} = 120.

  3. In how many ways can 77 identical cookies go to 44 kids if each gets at least one?

    Answer

    2020

    Full solution

    (63)=20\binom{6}{3} = 20.

  4. Count the nonnegative integer solutions of x+y+z=10x + y + z = 10.

    Answer

    6666

    Full solution

    (122)=66\binom{12}{2} = 66.

  5. Count the positive integer solutions of a+b+c=9a + b + c = 9.

    Answer

    2828

    Full solution

    (82)=28\binom{8}{2} = 28.

  6. A shop sells 44 flavors of donut. In how many ways can you pick 66 donuts, with repeats allowed?

    Answer

    8484

    Full solution

    n=6n = 6, k=4k = 4: (93)=84\binom{9}{3} = 84.

  7. Count the integer solutions of x+y+z=12x + y + z = 12 with each variable at least 33.

    Answer

    1010

    Full solution

    Set x=3+x′x = 3 + x' and so on: x′+y′+z′=3x' + y' + z' = 3, so (52)=10\binom{5}{2} = 10.

  8. A student counts the ways to put 44 identical balls into 22 boxes as 24=162^4 = 16. What is the correct count?

    Answer

    55

    Full solution

    The balls are identical, so only the split matters: (51)=5\binom{5}{1} = 5, the splits 0+40 + 4 through 4+04 + 0.

Frequently asked questions

What is the stars and bars formula?

The number of ways to put n identical objects into k groups is C(n + k − 1, k − 1).

What if every group must get at least one?

Give one to each group first, leaving n − k objects. The count becomes C(n − 1, k − 1).

How does it count combinations with repetition?

Choosing n items from k types with repeats allowed is the same as deciding how many of each type, so the count is C(n + k − 1, k − 1).

Does it work for different objects?

No. Stars and bars needs identical objects. With different objects, each one picks a group, giving kⁿ ways.

What to learn next