Number of onto functions

Question

What are the number of onto functions from a set $\Bbb A $ containing m elements to a set $\Bbb B$ containing n elements.

I found that if $m = 4$ and $n = 2$ the number of onto functions is $14$.

But is there a way to generalise this using a formula? If yes, what is this formula and how is it derived?

reference

I referred to this question but my doubt was not cleared: How many one to one and onto functions are there between two finite sets?

If not, Then what is the standard way of doing it?

If you explain this to me with an example please explain with the example of $m = 5$ and $n = 3$.

Answer 1

Obviously if $m<n$, there are no function from $\Bbb A$ onto $\Bbb B$, so assume that $m\ge n$. We’ll use an inclusion-exclusion argument. There are $n^m$ functions of all kinds from $\Bbb A$ to $\Bbb B$. If $b\in\Bbb B$, there are $(n-1)^m$ functions from $\Bbb A$ to $\Bbb B\setminus\{b\}$, i.e., functions whose ranges do not include $b$. We need to subtract these from the original $n^m$, and we need to do it for each of the $n$ members of $\Bbb B$, so a better approximation is $n^m-n(n-1)^m$.

Unfortunately, a function whose range misses two members of $\Bbb B$ gets subtracted twice in that computation, and it should be subtracted only once. Thus, we have to add back in the functions whose ranges miss at least two points of $\Bbb B$. If $b_0,b_1\in\Bbb B$, there are $(n-2)^m$ functions from $\Bbb A$ to $\Bbb B\setminus\{b_0,b_1\}$, and there are $\binom{n}{2}$ pairs of points of $\Bbb B$, so we have to add back in $\binom{n}2(n-2)^m$ to get

$$n^m-n(n-1)^m+\binom{n}2(n-2)^m\;,$$

which can be expressed more systematically as

$$\binom{n}0n^m-\binom{n}1(n-1)^m+\binom{n}2(n-2)^m\;.$$

Unfortunately, this over-corrects in the other direction, by adding back in too much. The final result, when the entire inclusion-exclusion computation is made, is

$$\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^m\;,$$

which can also be written $$n!{m\brace n}\;,$$ where ${m\brace n}$ is a Stirling number of the second kind. The Stirling number gives the number of ways of dividing up $\Bbb A$ into $n$ non-empty pieces, and the $n!$ then gives the number of ways of assigning those pieces to the $n$ elements of $\Bbb B$.

Answer 2

The answer is a little complicated. It is $n!S(m,n)$, where $S(m,n)$ is the appropriate Stirling Number of the second kind.

There are nice recursions for the $S(m,n)$, but no simple closed-form formula.

Answer 3

By the inclusion-exclusion principle, a Set $B$ containing $N$ distinct objects, with set of properties $B_1, B_2, \ldots, B_n$ (that the objects of the set $B$ may possess), and $N(B_i)$ being the number of objects having property $B_i$,the number of objects in $B$ having none of the properties $B_1, B_2, \ldots, B_n$ is given by

$N\left(\bigcap\limits_{i=1}^{n}\bar{B_i}\right)=N-N\left(\bigcup\limits_{i=1}^{n}B_i\right)$

$=N-\left(\sum\limits_{i=1}^{n} N(B_i)-\underset{1\leq i\neq j \leq n}{\sum\sum}N(B_i\cap B_j)+\underset{1\leq i\neq j \neq k \leq n}{\sum\sum\sum}N(B_i\cap B_j \cap B_k) - \ldots + (-1)^n N\left(\bigcap\limits_{i=1}^n B_i\right)\right)$

Now, for the mapping $f: A \to B$, with $A=\{a_1,a_2,\ldots,a_m\}$ and $B=\{b_1,b_2,\ldots,b_n\}$, s.t., $|A|=m$ and $|B|=n$, with $m\leq n$, let's define the property $B_i$ as $b_i \not \in B$, $\forall{i\in\{1, 2, \ldots, n\}}$, with $N=n^m$ being total number of possible mappings.

Then we have the number of onto functions

$=N\left(\bigcap\limits_{i=1}^{n}\bar{B_i}\right)$

$=n^m-\left(n(n-1)^m-{n \choose 2}(n-2)^m+\ldots+ (-1)^{n-1}{n \choose n-1}1^m\right)$

$=\sum\limits_{k=0}^{n}(-1)^k{n \choose k}(n-k)^m$

(Notice the similarity of the above expression with that of The Matching Problem/Derangements - n letters to n people)