Stars & Bars

Stars and bars counts the solutions of $x_1+\cdots +x_k=n$ in non-negative integers by arranging $n$ stars and $k-1$ bars in a row.

Distribution and integer-solution questions are common counting warm-ups, and the lower-bound trick turns many variants into the same formula.

Each distribution is a string of $n$ stars and $k-1$ bars; choose the bar positions. Lower bounds are handled by pre-filling each box.

1. 1Confirm the items are identical and the boxes are distinct.
2. 2Subtract any lower bounds: if $x_i\ge m$, set $y_i=x_i-m$.
3. 3Apply $\left(\genfrac{}{}{0ex}{}{n^{\prime }+k-1}{k-1}\right)$ to the reduced total $n^{\prime }$.
4. 4For upper bounds, combine with inclusion-exclusion.