(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}<a_{i} \text { for all } 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<j \leqslant r}\left(\begin{array}{c} N+r-a_{i}-a_{j} \\ r \end{array}\right) \\ &-\sum_{0 \leqslant i<j<k \leqslant r}\left(\begin{array}{c} N+r-a_{i}-a_{j}-a_{k} \\ r \end{array}\right)+\cdots \end{aligned}$$

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