Past exam of the mathematics course of the University of Cambridge / 2010 / ia / Paper 4 / 7E / c / Solution

Let $\Omega$ be the set of all functions from the $n$-element domain to the $k$-element codomain, and let $C_j$ consist of the functions which omit codomain element $j$. A function is surjective precisely when it lies outside ${\bigcup }_j{C}_j$.

For $J\subseteq [k]$ of size $i$, the intersection ${\bigcap }_{j\in J}{C}_j$ consists of maps taking all their values in the remaining $k-i$ elements, so it has $(k-i{)}^n$ members. There are $\left(\genfrac{}{}{0ex}{}{k}{i}\right)$ choices of $J$. Applying the complement form of the inclusion-exclusion principle givesWhen $k=n$, every fibre of a surjective function has at least one member, and the $n$ fibres partition an $n$-element domain. Thus every fibre has exactly one member and the function is a bijection. The count of these bijections is $n!$ by the successive distinct-image choices from part (a). Hence