Sum of all possible surjective functions. For my combinatorics homework I have the following problem:
Let $A = \{a_1, a_2, ..., a_m\}$ and $B = \{b_1, b_2, ... , b_n\}$ with $m \geq n$. Show that the amount of surjective functions $f$ from $A$ to $B$ is equal to:
\begin{equation} 
\sum_{i=0}^n (-1)^i {n \choose i} (n-i)^m
\end{equation}
My first thought was that, because these functions must be surjective, for every element $b \in B$ there must be a unique $a \in A$ such that $f(a) = b$. Therefore we must choose $n$ elements in $A$ that have a unique image on $B$ and the rest of the elements in $A$ can be sent to a random element in $B$. So i was thinking about:
\begin{equation}
{m \choose n} \cdot n! \cdot n^{m-n}
\end{equation}
as the amount of all possible surjective functions $f$ from $A$ to $B$.
My second thought was that the combination is unnecessary and therefore the formula must be:
\begin{equation}
n! \cdot n^{m-n}
\end{equation}
Is this correct? If so, how can i prove that this is the same as the summation given at the beginning?
I hope anybody can help me with this problem.
Thanks in advance!
 A: The first formula follows from the inclusion-exclusion principle in the following way: denote by $F_i,$ $1 \leq i \leq n$ the set of all functions from $A$ to $B$ such that the cardinal of their images is exactly $n - i.$ Let us count these. Let $1 \leq i \leq n.$ We must first choose $i$ of the $n$ elements of $B$ that are not in the range of $f \in F_i.$ This ammounts to $\binom{n}{i}$ choices. Moreover, once we have chosen the range of $f$, we have exactly $(n - i)^m$ choices for $f,$ so that the total number is equal to $\binom{n}{i} (n - i)^m.$ Note that the surjective functions are exactly the complement of the union of the $F_i'$s. This cardinal is easily computed with the inclusion-exclusion principle and it is equal to $\sum_{1 \leq i \leq n} \binom{n}{i} (-1)^{i - 1} (n - i)^m.$ Thus the number of surjective functions is $$n^m - \sum_{1 \leq i \leq n} \binom{n}{i} (-1)^{i - 1} (n - i)^m = \sum_{0 \leq i \leq n} (-1)^i \binom{n}{i} (n - i)^m.$$
The number of surjective functions from $A$ to $B$ can also be approximated directly in a similar manner to the one you were trying to use. The method you described is more or less precisely correct. Let $f: A \rightarrow B$ be surjective. We go through the elements of $B$ one by one, starting with $b_1.$ Since $f$ is surjective, there must be $a_j \in A$ such that $f(a_j) = b_1,$ so we have $m$ choices of $a$ for $b_1.$ Similarly, for $b_2$ we will have $m - 1$ choices and so on. We get $\binom{m}{n} n!$ so far. The other elements in $A$ can be mapped to anything in $B,$ so we have another $n^{m - n}$ choices, for a total of $\binom{m}{n} n! n^{n - m}$ so far. The thing is we may allow for repetitions if we use this method, so this will not be our final answer. I hope this helps. :)
