Stars & Bars / Integer Partitions

Medium3–4 hrsStars and BarsCompositionsDistributionsCounting

Overview

Stars and bars is the fundamental tool for counting integer solutions to linear equations. The idea: arranging n stars (objects) and k−1 bars (dividers) in a line — every arrangement corresponds uniquely to a way of distributing the n objects into k groups. The formula C(n+k−1, k−1) counts these arrangements. For labeled objects, use multinomials instead. For objects with upper bounds per bin, use inclusion-exclusion.

How to Recognize

→'How many ways to distribute n identical objects into k distinct bins?'
→Number of non-negative integer solutions to x₁+x₂+…+xₖ=n
→Distributing coins, balls, resources with no uniqueness
→'Ordered partitions of n into k parts'
→Any problem of dividing unlabeled items into labeled groups

Step-by-Step Approach

1.Non-negative integers (x₁+…+xₖ=n): C(n+k-1, k-1) ways
2.Positive integers (each xᵢ ≥ 1): substitute yᵢ = xᵢ-1, get C(n-1, k-1)
3.At most m in each bin: use inclusion-exclusion to subtract excess
4.Draw n stars and k-1 bars in a line — count arrangements
5.With distinct objects (balls labeled): use multinomials instead

Key Formulas

x_1+\cdots+x_k=n,\; x_i \ge 0: \binom{n+k-1}{k-1}

ways

x_1+\cdots+x_k=n,\; x_i \ge 1: \binom{n-1}{k-1}

ways

\text{Compositions of }n\text{ into }k\text{ parts: }\binom{n-1}{k-1}

\text{All compositions of }n: 2^{n-1}

(each of n-1 gaps: put a divider or not)

Worked Examples

0Quick Example

Distribute 10 identical candies to 3 kids (each may get 0): C(10+3-1, 3-1) = C(12,2) = 66 ways. With each kid getting at least 1: C(10-1, 3-1) = C(9,2) = 36 ways.

Problem

A casino has 20 identical $100 chips to distribute among 4 players. How many ways are there if (a) each player can get 0 chips, (b) each player must get at least 2 chips?

Solution

(a) Non-negative integers: x₁+x₂+x₃+x₄=20. C(20+4-1, 4-1) = C(23,3) = 1771 ways.

(b) Each player gets at least 2: let yᵢ = xᵢ-2 (yᵢ ≥ 0). Then y₁+y₂+y₃+y₄ = 20-8 = 12.

C(12+4-1, 4-1) = C(15,3) = 455 ways.

Answer

(a) C(23,3) = 1771. (b) C(15,3) = 455.

Common Mistakes

!
Confusing identical vs distinct objects. Stars and bars is for IDENTICAL objects. If objects are distinct, use multinomials or direct assignment.
!
Off-by-one in the formula. n+k-1 choose k-1 (not n choose k, not n+k choose k). Remember: n stars, k-1 bars, total n+k-1 symbols, choose positions for the bars.
!
Forgetting to substitute for minimum constraints. If xᵢ ≥ m, substitute yᵢ = xᵢ - m first.

Practice Problems

Click "Show Answer" to reveal

How many ways can you make change for $1 using quarters, dimes, nickels, and pennies (order doesn't matter)?

Hint: This is equivalent to non-negative integer solutions to 25q + 10d + 5n + p = 100. Stars and bars doesn't directly apply (unequal coefficients), but you can enumerate: loop over q=0,1,2,3,4, then for each q, loop over d=0,...

n people sit at a round table. How many distinct circular arrangements are there? (Rotations are the same.)

Hint: Fix one person's seat (breaks rotational symmetry). Arrange the remaining n-1 people.

Back to Study Plan

Multi-Asset Kelly & Applications Inclusion-Exclusion Principle