Formula for number of onto functions from m to m-1

Question

Recently I came up with general formula for number of onto functions from set $|\mathbb{A}|=m$ to set $|\mathbb{B}|=n$. Is there any way I can come up with explicit formula for $n=m-2$?

I started thinking about binomial coefficients property, that $$\binom{m}{m-2}=\binom{m}{2}$$ and this somehow could help reducing long summation that we use in general formula, but it didn't do anything helpful.

My second idea was to calculate the result with $m=n$, then consequently increment $m$ 2 times, calculating new result. First of all, we know that if $m=n$, then number of onto functions is $m!$. After we have added 1 element (let's denote it by $x$) to $\mathbb{A}$, $x$ can be mapped to any of $n$ elements. But after that adding, some pairs of previous elements in $\mathbb{A}$ can now map to the same element. That's the point when my calculations got stuck.

I also tried to brute force the solution for $S(m, m-1)$ and found out that $S(m, m-1)=\frac{m!\,(m-1)}{2}$ at least for $m < 25$. Is it true or it's just a coincidence for relatively small numbers?

Final question: is there any way to somehow reduce long summation in general formula for $n=m-2$ and find an explicit formula without summation?

Answer 1

If $m\geq4$, and $f:\>A:=[m]\to B:=[m-2]$ is a surjective map then all elements of $B$ have exactly one preimage, with the following exceptions: either (i) exactly one element $y\in B$ has three preimages, or (ii) two elements $y_1$, $y_2\in B$ have two preimages each.

In case (i) we can choose this $y\in B$ in $m-2$ ways, its preimages in ${m\choose 3}$ ways, and then map the remaining $m-3$ elements of $A$ bijectively onto the remaining elements of $B$ in $(m-3)!$ ways.

In case (ii) we can choose $y_1<y_2$ in ${m-2\choose2}$ ways, then $f^{-1}\bigl(\{y_1\}\bigr)$ in ${m\choose 2}$ ways and $f^{-1}\bigl(\{y_2\}\bigr)$ in ${m-2\choose 2}$ ways. Finally we can map the remaining $m-4$ elements of $A$ bijectively onto the remaining elements of $B$ in $(m-4)!$ ways.

It follows that the number $N$ you are after is given by $$N=(m-2){m\choose3}(m-3)!+{m-2\choose2}{m\choose2}{m-2\choose2}(m-4)!\ .$$ I may leave the simplification of this result to you.

Answer 2

Say we want to count the number of surjections $f$ from $[n]$ onto $[m]$. Then for each $i\in [m]$, $f^{-1}(i)$ is a nonempty subset of $[n]$. Furthermore, if $i\neq j$, then $f^{-1}(i)\cap f^{-1}(j)=\varnothing$, because a single element cannot be mapped to two different elements. In other words, we partition $[n]$ into $m$ nonempty blocks, which serve as the preimages of the elements of $[m]$ under $f$, and then we choose what element of $[m]$ each block maps to, making sure that each block maps to a different element. The number of partitions of $n$ into $m$ nonempty blocks is referred to as $S(n,m)$, or the second Stirling number, and then we have $m!$ ways of assigning each block to an element of $[m]$. Hence, the number of such surjections is $m!S(n,m)$.

EDIT: If you're looking for a closed form representation of the Stirling numbers, I don't know of one. Your observation comes from the fact that $S(n,n-1)=\binom{n}{2}$, so the number of surjections from $[n]$ onto $[n-1]$ is $(n-1)!\binom{n}{2}=(n!)(n-1)/2$.

EDIT 2: For the particular case of $S(n,n-2)$, the number of partitions of $[n]$ into $n-2$ blocks is $\binom{n}{3}+\binom{n}{2}\binom{n-2}{2}/2$. The first term counts partitions with a $3$-element block, and the rest are singletons, and the second term counts partitions with two $2$-element blocks, and the rest are singletons.