Course contentsShow
← Computer Science
Lesson 102 of 2,8722. Discrete Mathematics for CSFree lesson

Combinations with Repetition (Stars and Bars)

Apply the stars and bars method to count ways to distribute indistinguishable objects into bins.

Combinations with Repetition (Stars and Bars)

You'll learn how to count ways to distribute identical items into distinct categories using the stars and bars formula.

The Core Problem

Imagine you have 5 identical coins to distribute among 3 friends. Since the coins are indistinguishable (no difference between them), you only care about how many each friend gets, not which specific coins. Friend A might get 2, Friend B gets 3, Friend C gets 0—one of many possibilities.

This is combinations with repetition: selecting from categories where picking the same category multiple times is allowed, and order doesn't matter.

The Stars and Bars Method

Visualize the 5 coins as stars: ★★★★★

To separate them into 3 groups, we need 2 dividers (called bars): |

One arrangement: ★★|★★★| means Friend A gets 2, Friend B gets 3, Friend C gets 0.

Another: |★★★|★★ means Friend A gets 0, Friend B gets 3, Friend C gets 2.

We're arranging 5 stars and 2 bars in a line. The total positions = 5 + 2 = 7. We choose 2 positions for the bars (or equivalently, 5 for the stars).

The Formula

To distribute n indistinguishable objects into k bins:

C(n + k - 1, k - 1) or equivalently C(n + k - 1, n)

For our example: C(5 + 3 - 1, 3 - 1) = C(7, 2) = 21 ways.

This uses the combinations formula you learned earlier: selecting positions from total arrangements.

When to Use This

  • Distributing identical resources
  • Counting solutions to equations like x₁ + x₂ + x₃ = n where variables are non-negative integers
  • Multiset selections (picking with replacement)

Key Takeaway: Stars and bars transforms distribution problems into combination calculations by representing objects as stars and separators as bars: C(n + k - 1, k - 1).