Counting surjective functions We have $r$ objects and $n$ boxes. I have to count all the combinations possible if the objects and boxes could be both different. If that happens I can count the number of variations from $n$ to $r$ (number of functions between objects and boxes). I mean, $n^r$.
But if I have to count all the combinations possible if anyone of the boxes is empty ($r\ge n$). Now I have to count the surjective functions.
For example if I have $r$ objects and 1 box. The number of surjective functions is 1. Then, if I have $r$ objects and 2 boxes, the number of surjective functions is $2^r-2$. And finally if I have $r$ objects and 3 boxes, I will count $3^r-2\cdot[3\cdot2^r-3]$. How do I get the formula for $r$ objects and $n$ boxes? 
 A: We want the number of surjections from $r$ to $n$. 
First, note that the Stirling number of the second kind
$$
\begin{Bmatrix}
x\\
y
\end{Bmatrix}
$$
is a quantity that solves most of the puzzle: this number equals the number of partitions of $x$ into $y$-many nonempty subsets.
Clearly, every surjection $f\colon [r]\to [n]$ determines such a partition: $\{f^{-1}(j)\mid 1\le j\le n\}$, and each such partition of $r$ corresponds to $n!$ different surjections (permutations of the range). (Here, $[m]$ denotes $\{1,\dotsc,m\}$.) So the total number of surjections $[r]\to [n]$ is:
$$
n! 
\begin{Bmatrix}
r\\
n
\end{Bmatrix}
$$
The Stirling number of the second kind can be computed from the explicit formula
$$
\begin{equation*}
\begin{Bmatrix}
r\\
n
\end{Bmatrix}
=\frac{1}{n!}\sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}j^r
\end{equation*}
$$
As you can see, a kind of "inclusion/exclusion" principle is at work. Various answers to the following question (the special case $n=3$ of yours) provide some intuition about why that is so: Counting the number of surjections.
Notice the factor of $\frac 1 {n!}$, which we multiplied the Stirling number of 2nd kind by when counting surjections. So finally can simplify further: the number of surjections $[r]\to [n]$ is
$$
\sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}j^r
$$
A: Lets say you have $k$ empty boxes where $1\leq k \leq n-1$. Choose your empty boxes $\binom{n}{k}$ and then fill the other boxes with your objects $(n-k)^r$. Sum this up and you get $\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^r$. The number of your surjective functions will be $n^r-\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^r$.
