Surjections

Proposition 7.2.9   Let $A$ and $B$ be two finite and non empty sets such that $\vert A\vert=m$, $\vert B\vert=n$. the number $S(m,n)$ of surjections from $A$ to $B$ is given by the following relation:

$$n!\, S(m,n) = \sum_{k=0}^n (-1)^k \binom{n}{k} (n-k)^m$$

Proof. This is another application of the Inclusion-Exclusion principle. Consider the set of functions from $A$ to $B$ with $\lvert A\rvert = m$ and $\lvert B\rvert = n$. For any $i \in B$, define $X_i$ to be the set of functions avoiding $i$. So the set of surjections is $\Bar{X_1} \cap \dots \cap \Bar{X_n}$. Thus the number of surjections from $A$ to $B$ is $\lvert\Bar{X_1} \cap \dots \cap \Bar{X_n}\rvert$. By the inclusion-exclusion principle this is $\sum_{J \subseteq B} (-1)^{\lvert J\rvert } \lvert X_J\rvert$. If $\lvert J\rvert = k$ then $\lvert X_J\rvert = (n-k)^m$. The result follows. $\qedsymbol$