(a) Let $A, B$ be finite non-empty sets, with $|A|=a,|B|=b$. Show that there are $b^{a}$ mappings from $A$ to $B$. 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 $n$ onto a set of size $k$ is

$$\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 !=\sum_{i=0}^{n}(-1)^{i}\left(\begin{array}{c} n \\ i \end{array}\right)(n-i)^{n}$$