Stars and Bars
Stars and bars counts ways to group identical objects into labeled boxes — equivalently, non-negative (or bounded) integer solutions to linear Diophantine equations.
This lesson follows CP-Algorithms — Stars and bars.
Related: Knapsack (distributing capacity), Polynomials & Series (generating functions).
Theorem
Number of ways to put n identical objects into k labeled boxes:
C(n + k − 1, n) = C(n + k − 1, k − 1)
Proof sketch: write n stars (★) and k−1 bars (|). Example for 5 objects / 4 boxes:
★ | ★★ | | ★★ → (1, 2, 0, 2)
Every partition ↔ every arrangement of n stars and k−1 bars → binomial coefficient.
Non-negative sums
Count solutions of
x₁ + x₂ + ⋯ + xₖ = n, xᵢ ≥ 0
Same bijection → C(n + k − 1, n).
Example: 1 + 3 + 0 = 4 ↔ ★ | ★★★ |.
Positive sums
Now require xᵢ ≥ 1. Place n stars in a row; bars may occupy the n−1 gaps between stars (at most one bar per gap, else an empty box). Choose k−1 of those gaps:
C(n − 1, k − 1)
(Equivalently yᵢ = xᵢ − 1 ≥ 0 ⇒ Σ y = n − k ⇒ C((n−k) + k − 1, n−k).)
Lower bounds
For xᵢ ≥ aᵢ, set xᵢ′ = xᵢ − aᵢ ≥ 0:
x₁′ + ⋯ + xₖ′ = n − Σ aᵢ
then apply the non-negative formula (if the right-hand side is negative, answer is 0).
Upper bounds
Caps xᵢ ≤ bᵢ need inclusion–exclusion (or generating functions). See Upper-bound integer sums / IE on CP-Algorithms.
🧪 Binomial counts for the three cases
Check: stars and bars
Stars and bars
1 / 4Ways to put n identical items into k labeled boxes…
Pick an answer to see if you are right.
Practice drills
Input: n k (0 ≤ k ≤ n ≤ 60). Print C(n,k) (exact integer; multiplicative formula is fine).
Practice problems
From CP-Algorithms:
- Codeforces 553A — Kyoya and Coloured Balls
- Codeforces 1288C — Two Arrays
- Codeforces — Array, Colorful Bricks, One-Dimensional Puzzle (see article titles / search)
Cheat sheet
| Case | Formula |
|---|---|
Identical → k boxes | C(n+k−1, n) |
Σ x = n, x≥0 | same |
Σ x = n, x≥1 | C(n−1, k−1) |
xᵢ ≥ aᵢ | C(n−Σa + k−1, n−Σa) |
| Upper bounds | Inclusion–exclusion |