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

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.$$

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}$$