Section 1.2

Stars and Bars

Identical items into distinct boxes: integer solutions of x1+...+xk = n with lower or upper bounds, multisets, non-decreasing sequences, monomials, and counts of digit sums or dice totals.

Toolkit

Stars and bars converts “identical items into distinct boxes” into counting arrangements of stars and bars. The number of nonnegative integer solutions to $x_1+\cdots+x_k=n$ is $\binom{n+k-1}{k-1}$ , equivalently the number of multisets of size $n$ from $k$ types. Key tools:

\#\{x_i\ge 0: \textstyle\sum x_i=n\}=\binom{n+k-1}{k-1},\qquad \#\{x_i\ge a_i: \textstyle\sum x_i=n\}=\binom{n-\sum a_i+k-1}{k-1}.

A bound $\sum x_i\le m$ becomes an equation by adding a slack variable $x_{k+1}\ge0$ with $\sum_{i=1}^{k+1}x_i=m$ . Upper bounds $x_i\le b_i$ are handled by inclusion-exclusion: subtract solutions with some $x_i\ge b_i+1$ , using

\sum_{S}(-1)^{|S|}\binom{n-\sum_{i\in S}(b_i+1)+k-1}{k-1}.

Non-decreasing sequences, digit strings, and dice outcomes all reduce to choosing multiplicities, i.e. to this same equation-counting problem.

Problems