Paper 4, Section II, E

Numbers and Sets | Part IA, 2013

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

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

(ii) State the Inclusion-Exclusion principle.

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

n0++nr=N,0ni<ai for all in_{0}+\cdots+n_{r}=N, \quad 0 \leqslant n_{i}<a_{i} \text { for all } i

(N+rr)0ir(N+rair)+0i<jr(N+raiajr)0i<j<kr(N+raiajakr)+\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 (mr)\left(\begin{array}{c}m \\ r\end{array}\right) is defined to be zero if m<rm<r.

Typos? Please submit corrections to this page on GitHub.