Stars and Bars

Count the ways to distribute identical items into distinct groups, with or without lower bounds.

1. The idea

Stars and bars counts the number of ways to write $n$ identical items as an ordered sum of $k$ non-negative integers: $x_{1} + x_{2} + \dots + x_{k} = n$ , $x_{i} \geq 0$ . Picture $n$ stars in a row and $k - 1$ bars inserted among them to divide the stars into $k$ groups; the count is $(k - 1 n + k - 1)$ .

When each group requires a minimum count $x_{i} \geq m_{i}$ , substitute $y_{i} = x_{i} - m_{i} \geq 0$ to reduce back to the non-negative case with a smaller total, $n - \sum m_{i}$ , then apply the same formula.

This method applies whenever items are indistinguishable and only the count per category matters — distributing identical candies to children, allocating indistinguishable orders across price levels, and similar problems.

2. Why it matters

Stars and bars converts a distribution-counting problem into a single binomial coefficient, and the lower-bound shift technique is one of the most frequently reused tricks in quant interviews.

3. Core mathematics

Non-negative integer solutions

(k - 1 n + k - 1)

Number of solutions to $x_{1} + \dots + x_{k} = n$ with $x_{i} \geq 0$ .

Positive integer solutions

(k - 1 n - 1)

Each $x_{i} \geq 1$ ; equivalent to substituting $y_{i} = x_{i} - 1 \geq 0$ .

General lower bound shift

x_{i} \geq m_{i} \Rightarrow y_{i} = x_{i} - m_{i} \geq 0, \sum y_{i} = n - \sum m_{i}

4. How to recognize it

Think of this when…

Distributing identical items among distinct boxes, people, or categories.
Counting integer solutions to an equation like $x_{1} + x_{2} + \dots + x_{k} = n$ .
Minimum quantities per category ('each person gets at least one') signal the lower-bound shift.
Order allocation, inventory splitting, or dice-sum counting problems.

5. Worked example

Worked example

How many ways can 10 identical candies be distributed among 4 children so that each child gets at least 1 candy?

1
Set up the equation: $x_{1} + x_{2} + x_{3} + x_{4} = 10$ with each $x_{i} \geq 1$ .
2
Substitute $y_{i} = x_{i} - 1 \geq 0$ , so $\sum y_{i} = 10 - 4 = 6$ .
3
Apply the non-negative stars and bars formula with $n = 6$ , $k = 4$ .
$(4 - 1 6 + 4 - 1) = (3 9) = 84$
Answer: 84 ways.

6. Common mistakes

Using $(k - 1 n + k - 1)$ directly when there's a positivity constraint, without first shifting variables.
Mixing up $(k - 1 n + k - 1)$ with $(n n + k - 1)$ — they're equal, but it's easy to plug in the wrong pair of numbers if not careful.
Applying stars and bars when items are actually distinguishable (it only counts distributions of identical items).
Forgetting to subtract the total lower bound from $n$ before applying the formula.

7. Quick check

How many non-negative integer solutions are there to $x_{1} + x_{2} + x_{3} = 7$ ?

How many ways to distribute 8 identical coins to 3 people so each gets at least 2?

8. Practice

12 QuantSolve questions use this concept.

Practice this concept

9. Related methods

Stars & Bars

Create a free account to save lesson progress.