Number of onto functions

Obviously if $m<n$, there are no function from $\Bbb A$ onto $\Bbb B$, so assume that $m\ge n$. We’ll use an inclusion-exclusion argument. There are $n^m$ functions of all kinds from $\Bbb A$ to $\Bbb B$. If $b\in\Bbb B$, there are $(n-1)^m$ functions from $\Bbb A$ to $\Bbb B\setminus\{b\}$, i.e., functions whose ranges do not include $b$. We need to subtract these from the original $n^m$, and we need to do it for each of the $n$ members of $\Bbb B$, so a better approximation is $n^m-n(n-1)^m$.

Unfortunately, a function whose range misses two members of $\Bbb B$ gets subtracted twice in that computation, and it should be subtracted only once. Thus, we have to add back in the functions whose ranges miss at least two points of $\Bbb B$. If $b_0,b_1\in\Bbb B$, there are $(n-2)^m$ functions from $\Bbb A$ to $\Bbb B\setminus\{b_0,b_1\}$, and there are $\binom{n}{2}$ pairs of points of $\Bbb B$, so we have to add back in $\binom{n}2(n-2)^m$ to get

$$n^m-n(n-1)^m+\binom{n}2(n-2)^m\;,$$

which can be expressed more systematically as

$$\binom{n}0n^m-\binom{n}1(n-1)^m+\binom{n}2(n-2)^m\;.$$

Unfortunately, this over-corrects in the other direction, by adding back in too much. The final result, when the entire inclusion-exclusion computation is made, is

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

which can also be written $$n!{m\brace n}\;,$$ where ${m\brace n}$ is a Stirling number of the second kind. The Stirling number gives the number of ways of dividing up $\Bbb A$ into $n$ non-empty pieces, and the $n!$ then gives the number of ways of assigning those pieces to the $n$ elements of $\Bbb B$.

The answer is a little complicated. It is $n!S(m,n)$, where $S(m,n)$ is the appropriate Stirling Number of the second kind.

There are nice recursions for the $S(m,n)$, but no simple closed-form formula.