= Solution
Use a <stars and bars> <bijection>. For a tuple, place $N$ stars in $r+1$ consecutive blocks of lengths $n_0,\ldots,n_r$, separated by $r$ bars. The bar positions form an $r$-element subset of $\{1,\ldots,N+r\}$. Explicitly,
$$
b_j=n_0+\cdots+n_{j-1}+j,\qquad 1\leq j\leq r.
$$
They satisfy $1\leq b_1<\cdots<b_r\leq N+r$. Conversely, such a subset determines
$$
n_0=b_1-1,\quad
n_j=b_{j+1}-b_j-1\ (1\leq j<r),\quad
n_r=N+r-b_r.
$$
These numbers are nonnegative and sum to $N$, proving that the two constructions are inverse. Hence
$$
\boxed{|S|=\binom{N+r}{r}.}
$$
Zero-length blocks are permitted, so the <bijection> also covers $N=0$.
Back to article page
