How many arrangements do we have? We have $N$ boxes and an inexhaustible supply of objects belonging to $k$ distinct classes such that $N\gt k$.
How many different arrangements of the objects in the boxes are there if
(a) each of the boxes may contain only one single object,
(b) every class is represented?
I have already tried to argue like this:
In order for the classes to be represented we have $k!$ choices in the case of the first $k$ boxes. Then I thought that for the rest ($N-k$) boxes we have $(N-k)^k$ possibilities. My first answer was: $k!(N-k)^k$. Then I enumerated the possibilities in the case of $N=4$ and $k=2$ and it turned out that my solution gave twice as many arrangements than I could enumerate. Then I got stuck.
 A: Without condition (b), the solution is straightforward - number of arrangements $A=k^N$
Condition b) implies we should remove the arrangements with only $k-1$ classes represented - there are ${k \choose k-1}$ way to choose which classes,  and for a given choice there are ${k-1}^N$ arrangements.
But wait! that has double counted cases where there are only $k-2$ classes. So we have to add them back in; and that affects the count for only $k-3$ classes, and so on.
Finally we run down through the possibilities on inclusions and exclusions and get:
$$\begin{align}A&=k^N-{k\choose k-1}(k-1)^N+{k\choose k-2}(k-2)^N-{k\choose k-3}(k-3)^N+...\\
&=\sum_0^{k-1}(-1)^i{k\choose k-i}(k-i)^N
\end{align}$$
Quick test: for $N=4, k=2$, $$A= {2\choose2}2^4 - {2\choose 1}1^4 = 1\times 16 - 2\times 2 = 14$$
A: The Stirling numbers of the second kind $S(N,k)$ count the number of ways to partition $N$ distinguishable objects into $k$ nonempty blocks. Multiply $S(n,k)$ by $k!$ to assign individual colors to these blocks, and you have the number you are after: It is the number of surjective maps $f: \>[N]\to[k]$.
