Stars and bars with upper bounds

2. (Stars and bars.) Write $m$ stars in a row and place $k-1$ bars among them; the bars cut the row into $k$ groups of stars whose sizes are $y_1,\dots,y_k\ge0$ with sum $m$, and every solution arises exactly once. A configuration is a sequence of $m+k-1$ symbols of which $k-1$ are bars: $\binom{m+k-1}{k-1}$ possibilities.

1. Put $y_i=x_i-1$, so $0\le y_i\le7$ and $y_1+\dots+y_4=16$.

• All non-negative solutions: $\binom{19}{3}=969$.
• Let $A_i$ be the set of solutions with $y_i\ge8$. Substituting $y_i=8+z_i$ gives $z$-sum $8$: $\binom{11}{3}=165$ solutions, for each $i$.
• Two variables $\ge8$: the sum would be $\ge16$ with equality: $y_i=y_j=8$ and the other two $0$, giving $\binom{3}{3}=1$ solution for each of the $\binom42=6$ pairs.
• Three variables $\ge8$ would need sum $\ge24>16$: impossible.

By inclusion-exclusion the answer is
$$969-4\cdot165+6\cdot1=315.$$

Check. Direct enumeration by computer gives $315$.

Remark. Equivalently, $315$ is the coefficient of $x^{16}$ in $\left(\frac{1-x^8}{1-x}\right)^4$.

Lesson. Stars and bars counts unconstrained solutions; upper bounds are handled by inclusion-exclusion on the violations.