Combinatorics – Number of Surjective Functions from a Set with $m$ Elements onto a Set with $n$ Elements

combinationscombinatoricsfunctionspermutations

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.

Best Answer

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

Related Question