# Number of surjective functions from a set with $m$ elements onto a set with $n$ elements

I was trying to calculate the number of surjective (onto) functions from A to B.
Let a set $A$ contain $m$ elements and another set $B$ contain $n$ element i.e.
$$|A|=m, \quad |B|=n.$$ Now, if $n>m$, no. of onto functions is $0$.
When $m \ge n$,
since there should be no unrelated element in B, let us relate first n elements of a A to B,so that all elements of B gets related.
Hence total possibility for first n elements of A( which actually contain m elements ) is $$n!$$ Now the remaining $m-n$ elements in $A$ can be related to any of the $n$ elements of $B$. Hence the total possibility of the remaining $m-n$ elements of $B$ is $$n^{m-n}$$
Therefore total number of surjective function is$$n!*n^{m-n}$$
Is anything wrong in this calculation ?If its wrong ,can anyone suggest correct method with proof.

• Nitpick. If you are assuming A and B are both finite you should specifically state that. – fleablood Jul 29 '18 at 15:49
• It's tedious but still worth the effort to work out "by hand" some smallish cases. This allows you to check your proposed formulas without going too far down the wrong path. – hardmath Jul 29 '18 at 15:50
• Related, though not obviously. If I recall correctly, the closed form I was seeking would have been precisely what you're looking for. – Cameron Buie Jul 29 '18 at 16:12
• – Cameron Buie Jul 29 '18 at 16:15
• Possible duplicate of Calculating the total number of surjective functions – Arnaud D. Sep 17 '18 at 13:38

## 3 Answers

In general computing the number of surjections between finite sets is difficult.

Your procedure for obtaining the figure of $n! \cdot n^{m-n}$ is overcounting, and also erroneous for another reason.

• It is overcounting beacuse you are specifying an ordered pair of functions (one bijective, one arbitrary) which piece together to form a surjection $A \to B$, but in general there are many ways of breaking up a surjection into a bijection and an arbitrary function.
• It is additionally erroneous because part of your procedure involves 'the first $n$ elements' of $A$, which means you've picked a distinguished subset of $A$ of size $n$. There are $\binom{m}{n}$ ways of doing this, so your procedure should in fact yield $\binom{m}{n} \cdot n! \cdot n^{m-n}$. But it's still overcounting: it counts the number of ordered triples $(A',f,g)$, where $A' \subseteq A$ is a subset with $n$ elements, $f : A' \to B$ is a bijection and $g : A \setminus A' \to B$ is an arbitrary function.

Even computing the number of surjections $A \to B$ when $n(A)=m$ and $n(B)=3$ is pretty tricky. There are $3^m - 3 \cdot 2^m + 3$ of them (see here, for instance).

If I recall correctly, there is no known closed form expression for the number of surjections from a set of size $m$ to a set of size $n$.

You can write an expression using inclusion-exclusion. There are $n^m$ total functions from $A$ to $B$. Subtract off the ones that do not cover one element. There are $(n-1)^m$ that skip one particular element, so you would subtract $n(n-1)^m$ to remove the ones that skip some element. You have removed all the ones that skip two elements twice, so we need to add them back in. There are ${n \choose 2}(n-2)^m$ that skip two elements. Now we have removed the ones that skip three elements three times and added them back three times, so we need to subtract ${n \choose 3}(n-3)m$. The final expression is $$n^m+\sum_{i=1}^{n-1}(-1)^i{n \choose i}(n-i)^m$$

The number of surjections from a set of $m$ elements to a set of $n$ elements is $$n! \;S(m,n)$$ where $S(m,n)$ is a Stirling number of the second kind.

• I like this answer! Can you provide some combinatorial intuition for future readers as to why this is the case? – ml0105 Jul 29 '18 at 21:08
• @ml0105 By definition, there are $S(m,n)$ ways to partition $A$ into $n$ nonempty subsets, then the subsets can be mapped to the elements of $B$ in $n!$ ways. (Please note that I have corrected a typo in my first version--I got my ms and ns mixed up). – awkward Jul 29 '18 at 21:20