13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nitpick. If you are assuming A and B are both finite you should specifically state that. $\endgroup$ – fleablood Jul 29 '18 at 15:49
  • $\begingroup$ 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. $\endgroup$ – hardmath Jul 29 '18 at 15:50
  • $\begingroup$ Related, though not obviously. If I recall correctly, the closed form I was seeking would have been precisely what you're looking for. $\endgroup$ – Cameron Buie Jul 29 '18 at 16:12
  • $\begingroup$ More obviously related. $\endgroup$ – Cameron Buie Jul 29 '18 at 16:15
  • 3
    $\begingroup$ Possible duplicate of Calculating the total number of surjective functions $\endgroup$ – Arnaud D. Sep 17 '18 at 13:38
11
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I like this answer! Can you provide some combinatorial intuition for future readers as to why this is the case? $\endgroup$ – ml0105 Jul 29 '18 at 21:08
  • 4
    $\begingroup$ @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). $\endgroup$ – awkward Jul 29 '18 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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