How many onto functions are there from a set $|T|=n+1$ to a set $|S|=n$?
It is well known that the number of onto functions from $|T|=m$ to $|S|=n$ is given by $$ n!\left(m\brace n\right)$$ where $m\brace n$ denotes a Sterling number of the second kind.
However, when $m=n+1$, I suppose the the computation may be simpler and not require this formula.
Thus we want to prove the number of surjections from $T\to S$, with $|T|=n+1$ and $|S|=n$ is $$\frac{n(n+1)!}{2}=\frac{n(n+1)}{2}\cdot n!=(1+…+n)n~!$$
Consider the simpler case from here by momentarily letting $T^*=T\setminus\{n+1\}$. Thus, $|T^*|=n$.
We find the number of onto functions from $T^*\to S$. From here it is easy to see that there are $n!$ such functions since the first element of $T^*$ has a choice of $n$ elements to map to in $S$, then the second element in $T$ of has a choice of $n-1$ elements to map to in $S$, … , and so on. Thus there are $$n\cdot(n-1)\cdot(n-2)\cdot…\cdot1=n!$$
such surjections.
Consider $T^*\cup\{n+1\}=T\therefore|T^*\cup\{n+1\}|=n+1$.
Since there are $n!$ onto functions that map $\{1,…,n\}\to\{1,…,n\}$, an onto map from $\{1,…,n,n+1\}\to\{1,…,n\}$ must map two $n_T\in\{1,…,n,n+1\}$ into the same element in $\{1,…,n\}$, thus there are at least $$n\cdot n!$$ such onto functions now.
Here is where I am stuck. How do I count what that last added element adds to the number of surjections?
Best Answer
An onto function from a set with $n+1$ elements to a set with $n$ elements will necessarily have $2$ elements from the domain mapping to the same element in the codomain and then all remaining elements in the domain mapping to a unique element in the codomain.
Pick which two elements from the domain share an output
Pick what that output was
From smallest to largest, pick what the output is for each remaining element
The number of such functions is then:
$$\binom{n+1}{2}n(n-1)! = (n+1)!\cdot \frac{n}{2}$$