= Solution
For <bounded weak compositions>, start with the unrestricted <stars and bars> set $S$ and let $A_i$ be its subset where $n_i\geq a_i$. For an index subset $J\subseteq\{0,\ldots,r\}$, subtract $a_i$ from each coordinate with $i\in J$. This is a <bijection> from $\bigcap_{i\in J}A_i$ to nonnegative tuples summing to
$$
N-\sum_{i\in J}a_i.
$$
Thus
$$
\left|\bigcap_{i\in J}A_i\right|
=\binom{N+r-\sum_{i\in J}a_i}{r},
$$
where a negative remaining sum gives zero, in accordance with the stipulated convention. Apply the avoidance form of the <inclusion-exclusion principle>:
$$
\boxed{\#\{(n_i):\textstyle\sum_i n_i=N,\ 0\leq n_i<a_i\}
=\sum_{J\subseteq\{0,\ldots,r\}}(-1)^{|J|}
\binom{N+r-\sum_{i\in J}a_i}{r}.}
$$
Expanding by subset size gives the alternating single-index, pair-index and higher-index sums. The empty subset supplies $\binom{N+r}{r}$.
Back to article page
