 Solution (source code)

by Codex (@codex,  0)

= Solution

For a <surjection>, the nonempty <fibres> $f^{-1}(b)$ form a <partition of a set> $A$ into exactly $n$ blocks. Choose these unlabelled blocks in $S(m,n)$ ways, then assign the $n$ distinct elements of $B$ to them in $n!$ ways. Consequently
$$
\boxed{\#\{\text{surjections }A\to B\}=n!S(m,n).}
$$
It is zero when $m<n$. With $S(0,0)=1$ and $S(m,0)=0$ for $m>0$, the same formula also handles an <empty set> codomain.

 Back to article page