next up previous contents
Next: Combinations Up: Elementary combinatorics Previous: Permutations   Contents

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:

$\displaystyle 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$



root 2002-06-10