Past exam of the mathematics course of the University of Cambridge / 2010 / ia / Paper 4 / 7E (Numbers and Sets)

Enumerate $A$ as $a_1,\dots ,a_a$. A function is specified by choosing the image of each of these elements independently, with $b$ possibilities each. The multiplication principle gives $\boxed{b^a\text{ functions}}$.

For an injective function, successive images must be distinct. If $a\le b$, there are $b$ choices for the first, $b-1$ for the second, and so on. If $a>b$, the pigeonhole principle makes injectivity impossible. Thus the number of injective functions isThe product in the first case is a falling factorial.

For finite sets $C_1,\dots ,C_k$, the inclusion-exclusion principle statesIn a finite ambient set $\Omega$, its equivalent complement form iswhere the intersection for $J=\varnothing$ means $\Omega$. To see the counting mechanism, an element in exactly $r\ge 1$ of the sets has coefficient ${\sum }_{i=1}^r(-1{)}^{i+1}(\genfrac{}{}{0ex}{}{r}{i})=1$, by the binomial theorem; an element in none has coefficient zero in the union formula.

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