3.2Repetition and distributions (stars and bars)
The idea
Stars and bars counts ways to share identical objects among distinct boxes: place k−1 bars among n stars. The number of non-negative solutions of x₁ + … + x_k = n is C(n + k − 1, k − 1).
Think of it like this: Handing out n identical sweets to k children: line the sweets up and slip k−1 dividers between them.
Why it exists
Distribution and "number of solutions of an equation" are among the most repeated GATE combinatorics questions.
How it works
- Non-negative solutions: C(n+k−1, k−1).
- Every variable ≥ 1: C(n−1, k−1). A lower bound b on a variable: substitute x = y + b first.
- Distinct balls into distinct boxes: kⁿ (each ball picks a box).
- Upper bounds are handled by inclusion–exclusion: subtract the solutions that break a bound.
Worked example: x + y + z = 10 with x, y, z ≥ 0
C(12, 2) = 66. With each ≥ 1: C(9, 2) = 36.
Now play with it
- →Set n = 10 and k = 3 in the lab and read both counts.
- →Compare with the distinct-ball count 3¹⁰.
| n identical balls, k distinct boxes: C(n+k−1, k−1) | 45 |
| … each box non-empty: C(n−1, k−1) | 21 |
| n distinct balls, k distinct boxes: kⁿ | 6561 |
| n distinct balls, k identical non-empty boxes: S(n, k) | 966 |
x₁ + x₂ + … + x_k = n with every xᵢ ≥ 0 has C(n+k−1, k−1) solutions: place k−1 bars among n stars.
| Balls | Boxes | Rule | Count |
|---|---|---|---|
| identical | distinct | stars and bars | C(n+k−1, k−1) |
| identical | distinct, none empty | stars and bars | C(n−1, k−1) |
| distinct | distinct | each ball chooses a box | kⁿ |
| distinct | distinct, none empty | onto functions | k!·S(n, k) |
| distinct | identical, none empty | Stirling second kind | S(n, k) |
| identical | identical | integer partitions | p(n, k) |
The twelvefold way in six lines. GATE mostly asks the first four rows.
Check yourself
How many non-negative integer solutions does x₁ + x₂ + x₃ + x₄ = 7 have?
Exam notes (the dense version)
Strings of length r over n symbols: nʳ. Solutions of x₁+…+x_k = n with xᵢ ≥ 0: C(n+k−1, k−1); with every xᵢ ≥ 1: C(n−1, k−1). Put a lower bound on a variable by substituting xᵢ = yᵢ + bound first. Distinct balls in distinct boxes: kⁿ. Distinct balls in identical non-empty boxes: Stirling S(n,k).
Previous year questions: Combinatorics & Recurrences (17)
PYQs are grouped by topic, so this is the full set for Combinatorics & Recurrences; try the ones that match this subtopic. Open all 17 on the topic page.