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?
Best Answer
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.