Number of surjections from $\{1,...,m\}$ to $\{1,...,n\}$

Question

Let $m,n$ be two integers such that, $m\ge n$. Compute the number of surjections from $\{1,...,m\}$ to $\{1,...,n\}$

There are $n^m$ functions (total).

we subtract from $n^m$ the number of non-surjective functions.

There are $\binom{n}{1}(n-1)^m$ functions missing one element.

There are $\binom{n}{2}(n-2)^m$ functions missing two elements, but how many times did we count this in the previous count ?

Then we have to add this again by inclusion-exclusion but why is the difference always 1?

Answer 1

For all $1 \le i \le n$ define $$A_i = \{\rho \colon M \to N \text{ a mapping such that } i \notin \rho(M)\}.$$ Then $$S = \{\rho \colon M \to N\} \setminus \bigcup_{i=1}^n A_i$$ is the set of surjections.

By the principle of inclusion and exclusion, we may calculate $$|S| = |\{\rho \colon M \to N\}| - \sum_{1 \le i_1 \le n} |A_i| + \sum_{1 \le i_1 < i_2 \le n} |A_{i_1} \cap A_{i_2}| - \dots \pm |A_1 \cap \dots \cap A_n|.$$ Now $|\{\rho \colon M \to N\}| = n^m$. We also have $$A_{i_1} \cap \dots \cap A_{i_k} = \{\rho \colon M \to N \text{ a mapping such that } \{i_1,\dots,i_k\} \cap \rho(M) = \emptyset\},$$ so that $|A_{i_1} \cap \dots \cap A_{i_k}| = (n-k)^m$. Each sum contains ${n \choose k}$ terms, so we have $$|S| = n^m - {n \choose 1}(n-1)^m + {n \choose 2}(n-2)^m - \dots \pm {n \choose n}(n-n)^m.$$

Answer 2

I have another "answer" and I am hoping that someone may enlighten me whether this answer is the same as above and if not, which one is correct.

It goes as follow: Order the set $\{1,\ldots,m\}$ in a linear fashion, there are $m!$ ways of doing this. There are $m-1$ spaces in between the elements and choosing $n-1$ spaces out of these spaces partitions the set into $n$ nonempty subsets, there are ${m-1 \choose n-1}$ ways of doing so. The first subset gets assigned to $1$, the second subset to $2$, and so on. This way, we were able to enumerate which elements of $\{1,\ldots,m\}$ get mapped to elements of $\{1,\ldots,n\}$. Thus, we have

$$ {m-1 \choose n-1}m! $$

such surjective maps.

Answer 3

For every pair of natural numbers $m\geq n$ let $\phi(m,n)$ be the number of surjections from a set with $m$ elements onto a set with $n$ elements.

We have $\phi(m,1)=1$ and $\phi(m,2)=2^m-2$. To compute $\phi(m,3)$ take $3^m$ and substract $\binom 32 \phi(m,2)+\binom 31 \phi(m,1)$.

Generalizing, $$\begin{align} \phi(m,n)&=n^m-\sum_{j=1}^{n-1}\binom nj\phi(m,j)=\\ &=n^m-\binom n{n-1}(n-1)^m+\sum_{j=1}^{n-2}\binom nj\phi(m,j)=\\ &=\sum_{j=0}^{n-1}(-1)^j\binom n{n-j}(n-j)^m \end{align}$$