Paper 4, Section II, 7E7 \mathrm{E}

Numbers and Sets | Part IA, 2010

(a) Let A,BA, B be finite non-empty sets, with A=a,B=b|A|=a,|B|=b. Show that there are bab^{a} mappings from AA to BB. How many of these are injective ?

(b) State the Inclusion-Exclusion principle.

(c) Prove that the number of surjective mappings from a set of size nn onto a set of size kk is

i=0k(1)i(ki)(ki)n for nk1\sum_{i=0}^{k}(-1)^{i}\left(\begin{array}{c} k \\ i \end{array}\right)(k-i)^{n} \quad \text { for } n \geqslant k \geqslant 1

Deduce that

n!=i=0n(1)i(ni)(ni)nn !=\sum_{i=0}^{n}(-1)^{i}\left(\begin{array}{c} n \\ i \end{array}\right)(n-i)^{n}

Typos? Please submit corrections to this page on GitHub.