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