# Paper 4, Section II, E

(i) Let $N$ and $r$ be integers with $N \geqslant 0, r \geqslant 1$. Let $S$ be the set of $(r+1)$-tuples $\left(n_{0}, n_{1}, \ldots, n_{r}\right)$ of non-negative integers satisfying the equation $n_{0}+\cdots+n_{r}=N$. By mapping elements of $S$ to suitable subsets of $\{1, \ldots, N+r\}$ of size $r$, or otherwise, show that the number of elements of $S$ equals

$\left(\begin{array}{c} N+r \\ r \end{array}\right)$

(ii) State the Inclusion-Exclusion principle.

(iii) Let $a_{0}, \ldots, a_{r}$ be positive integers. Show that the number of $(r+1)$-tuples $\left(n_{i}\right)$ of integers satisfying

$n_{0}+\cdots+n_{r}=N, \quad 0 \leqslant n_{i}

\begin{aligned} \left(\begin{array}{c} N+r \\ r \end{array}\right) &-\sum_{0 \leqslant i \leqslant r}\left(\begin{array}{c} N+r-a_{i} \\ r \end{array}\right)+\sum_{0 \leqslant i

where the binomial coefficient $\left(\begin{array}{c}m \\ r\end{array}\right)$ is defined to be zero if $m.

Typos? Please submit corrections to this page on GitHub.