By user50229

2012-12-25 00:57:05 8 Comments

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?


@Adam 2013-12-21 21:28:01

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

@hardmath 2012-12-25 01:14:17

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.

@user50229 2012-12-25 13:04:19

Thanks for the useful links. I suppose the moral here is I should try simple cases to see if they fit the formula!

@AndrewG 2012-12-25 01:37:21

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.

@user50229 2012-12-25 13:02:59

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?

@AndrewG 2012-12-25 22:46:21

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.

@CodeKingPlusPlus 2013-01-23 05:26:14

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

@AndrewG 2013-01-23 07:12:42

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

Related Questions

Sponsored Content

2 Answered Questions

[SOLVED] Total number of injective functions

2 Answered Questions

0 Answered Questions

Number of injective functions involving use of inclusion-exclusion principle

  • 2018-07-20 13:16:05
  • user3767495
  • 33 View
  • 0 Score
  • 0 Answer
  • Tags:   functions

3 Answered Questions

[SOLVED] Number of One to One Functions

1 Answered Questions

[SOLVED] Find total number of surjective mappings

  • 2014-10-08 00:39:46
  • user181598
  • 349 View
  • 1 Score
  • 1 Answer
  • Tags:   functions

0 Answered Questions

Counting Surjective functions without using the formula

1 Answered Questions

[SOLVED] Can surjective functions map an element from the domain...

Sponsored Content