Calculating The Total Number Of Surjective Functions

Answer :

Consider $f^{-1}(y)$, $y \in Y$. This set must be non-empty, regardless of $y$. What you're asking for is the number of ways to distribute the elements of $X$ into these sets.

The number of ways to distribute m elements into n non-empty sets is given by the Stirling numbers of the second kind, $S(m,n)$. However, each element of $Y$ can be associated with any of these sets, so you pick up an extra factor of $n!$: the total number should be $S(m,n) n!$

The Stirling numbers have interesting properties. They're worth checking out for their own sake.

Here is a solution that does not involve the Stirling numbers of the second kind, $S(n,m)$. The number of surjective functions from a set $X$ with $m$ elements to a set $Y$ with $n$ elements is

$$\sum_{i=0}^{n-1} (-1)^i{n \choose i}(n-i)^m$$

or more explicitly $${n \choose 0}n^m - {n \choose 1}(n-1)^m + {n \choose 2}(n-2)^m - \cdots \pm {n \choose n-2}2^m \mp {n \choose n-1}1^m$$

We begin by counting the number of functions from $X$ to $Y$, which is already mentioned to be $n^m$. Next we subtract off the number $n(n-1)^m$ (roughly the number of functions that miss one or more elements). Of course this subtraction is too large so we add back in ${n \choose 2}(n-2)^m$ (roughly the number of functions that miss 2 or more elements). But again, this addition is too large, so we subtract off the next term and so on. This is a rough sketch of a proof, it could be made more formal by using induction on $n$.

This gives an overcount of the surjective functions, because your construction can produce the same onto function in more than one way.

Consider a simple case, $m=3$ and $n=2$. There are six nonempty proper subsets of the domain, and any of these can be the preimage of (say) the first element of the range, thereafter assigning the remaining elements of the domain to the second element of the range. In other words there are six surjective functions in this case.

But your formula gives $\frac{3!}{1!} 2^{3-2} = 12$.

Added: A correct count of surjective functions is tantamount to computing Stirling numbers of the second kind. The Wikipedia section under Twelvefold way has details. For small values of $m,n$ one can use counting by inclusion/exclusion as explained in the final portion of these lecture notes.