Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 10 down vote accepted

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.

share|improve this answer
    
I think this is why combinatorics is so interesting, you have to find just the right way of looking at the problem to solve it. I hadn't heard of the Stirling numbers, I wonder why they are not included more often in texts about functions? Is it not as useful to know how many surjective functions there are as opposed to how many functions in total or how many injective functions? –  user50229 Dec 25 '12 at 13:02
    
Certainly. Often (as in this case) there will not be an easy closed-form expression for the quantity you're looking for, but if you set up the problem in a specific way, you can develop recurrence relations, generating functions, asymptotics, and lots of other tools to help you calculate what you need, and this is basically just as good. For instance, once you look at this as distributing m things into n boxes, you can ask (inductively) what happens if you add one more thing, to derive the recurrence $S(m+1,n) = nS(m,n) + S(m,n-1)$, and from there you're off to the races. –  AndrewG Dec 25 '12 at 22:46
    
Can someone explain the statement "However, each element of $Y$ can be associated with any of these sets, so you pick up an extra factor of $n!$ –  CodeKingPlusPlus Jan 23 '13 at 5:26
    
@CodeKingPlusPlus everything is done up to permutation. You can think of each element of Y as a "label" on a corresponding "box" containing some elements of X. The labeling itself is arbitrary, and there are n! different ways to do it. –  AndrewG Jan 23 '13 at 7:12

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.

share|improve this answer
1  
Thanks for the useful links. I suppose the moral here is I should try simple cases to see if they fit the formula! –  user50229 Dec 25 '12 at 13:04

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

$$ \sum_{i=0}^k (-1)^n{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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.