= 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_jC_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 $\binom ki$ choices of $J$. Applying the complement form of the <inclusion-exclusion principle> gives
$$
\boxed{\#\{\text{surjections}\}
=\sum_{i=0}^k(-1)^i\binom ki(k-i)^n\quad(n\ge k\ge1).}
$$
When $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
$$
\boxed{n!=\sum_{i=0}^n(-1)^i\binom ni(n-i)^n.}
$$
Back to article page
