Calculating the total number of surjective functions

Question

It is quite easy to calculate the total number of functions from a set $X$ with $m$ elements to a set $Y$ with $n$ elements ($n^{m}$), and also the total number of injective functions ($n^{\underline{m}}$, denoting the falling factorial). But I am thinking about how to calculate the total number of surjective functions $f\colon X \twoheadrightarrow Y $.

The way I thought of doing this is as follows: firstly, since all $n$ elements of the codomain $Y$ need to be mapped to, you choose any $n$ elements from the $m$ elements of the set $X$ to be mapped one-to-one with the $n$ elements of $Y$. This results in $n!$ possible pairings. But the number of ways of choosing $n$ elements from $m$ elements is $\frac{m!}{(m-n)!\,n!}$, so the total number of ways of matching $n$ elements in $X$ to be one-to-one with the $n$ elements of $Y$ is $\frac{m!}{(m-n)!\,n!} \times n! = \frac{m!}{(m-n)!}$.

Now we have 'covered' the codomain $Y$ with $n$ elements from $X$, the remaining unpaired $m-n$ elements from $X$ can be mapped to any of the elements of $Y$, so there are $n^{m-n}$ ways of doing this. Therefore I think that the total number of surjective functions should be $\frac{m!}{(m-n)!} \, n^{m-n}$.

Is this anything like correct or have I made a major mistake here?

Answer 1

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.

Answer 2

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$.

Answer 3

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.