number of surjective mapping from a set to another Is there a simple formula for finding the number of surjective mappings from a set of cardinality m to a set of cardinality n with m > n ?
 A: Yes there is a formula, the number of surjective functions from a set $X$ of cardinality $k$ to a set $Y$ of cardinality $n$, is given by $|surj(k,n)|=n! S_{k,n}$ where $S_{k,n}$ are the Stirling numbers of the second kind.
A: A function $f:X \to Y$ is called surjective when each of its preimages isn't empty. They form a partition of $Y$ into $k=|X|$ "blocks". On the other hand each partition from $Y$ into $k$ "blocks" lead to $n!$ surjective functions from $X$ to $Y$. Let denote $S_{n,k}$ they number of these partitions. They are basically the Stirling numbers of the second kind.
You can calculate the Stirling numbers by the following recursion: $S_{n,k} = S_{n-1,k-1}+ k S_{n-1,k}$. This can be seen in the following way:
The set of all partitions of the Set $Y:=[n]$ with $[n]=\{1,2,3,...,n\}$ decay in two disjoint subsets. 


*

*all partitions with $n \in Y$ is an own "block" of the partition

*all partitions with $n \in Y$ isn't an own "block" of the partition


ad 1) you can remove the the "block" {n} and this leads to a partition of $[n-1]$ into $k-1$ blocks and that is given by $S_{n-1,k-1}$.
ad 2) you can remove $n$ from his corresponding "block" and this leads to a partition of $[n-1]$ into $k$ "blocks" but from each such partition you can make $k$ partitions of $[n]$ when u put the element $n$ back to one "block". Therefore we have $k S_{n-1,k}$.
When you solve this recursion this leads to
$S_{n,k} = \frac{1}{k!} \sum_{i=0}^{k} \binom{k}{i} (-1)^{k-i} i^n$
