, 2010

Let $m = k + n$, and let $T$ be the set of all $n$-term sequences of nonnegative integers $(b_1, b_2, \dots, b_n)$ such that $b_1 + b_2 + \dots + b_n = k$. It suffices for us to show that
$$n! \sum_{T} 1^{b_1} 2^{b_2} \cdots n^{b_n} = \binom{n}{n} n^{k+n} - \binom{n}{n-1} (n-1)^{k+n} + \cdots + (-1)^{n-2} \binom{n}{2} 2^{k+n} + \cdots + (-1)^{n-1} \binom{n}{1}.$$
We claim that both sides of the desired equation count the number of ways to color $k+n$ objects with $n$ colors such that each color is used at least once. For $1 \le t \le n$, the number of ways to color $k+n$ objects with $t$ colors is $t^{k+n}$, so the principle of inclusion-exclusion shows exactly that the right hand side counts these colorings.
It suffices to show that the left hand side also counts these colorings. Label the objects $1$, $2$, $\dots$, $k+n$ in some order, and, for $1 \le i \le n$, let $c_i$ be the smallest object of color $i$. Take $b_i = c_{i+1} - c_i$, where we let $c_{n+1} = n+k+1$. Then, notice that any such coloring is specified uniquely by the following data: (a) the order in which the colors first appear, (b) the number of objects between $c_i$ and $c_{i+1}$ for each $i$, where we take $c_{n+1} = n+k+1$, and (c) the colors of the objects between $c_i$ and $c_{i+1}$. We now count how many ways these data can be chosen. There are $n!$ choices for datum (a), and it is independent of (b) and (c). Datum (b) is specified uniquely by a choice of $(b_1, b_2, \dots, b_n)$ such that $b_1 + b_2 + \dots + b_n = k$, that is, an element of $T$. Given such a choice of $(b_1, b_2, \dots, b_n)$, there are $1^{b_1} 2^{b_2} \dots n^{b_n}$ ways to color the intermediate objects, as each of the $b_i$ between $c_i$ and $c_{i+1}$ admits $i$ choices of color since only $i$ colors appear before $c_{i+1}$. Summing over all choices of (a), (b), and (c), we see that the number of colorings of this type is
$$n! \sum_{T} 1^{b_1} 2^{b_2} \dots n^{b_n},$$
which matches the left hand side of the desired equation, completing the proof.

Denote by $S_m$ the set of all $n$-term sequences of positive integers $(a_1, a_2, \dots, a_n)$ such that $a_1 + a_2 + \dots + a_n = m$. Let $x_m = \sum_{S_m} 1^{a_1} 2^{a_2} \dots n^{a_n}$, with $x_m = 0$ if $m < n$, and consider the corresponding generating function
$$F_n(t) = x_0 + x_1 t + x_2 t^2 + \dots$$
Computing, we find that
$$\begin{aligned} F_n(t) &= (t + t^2 + \dots)(2t + 4t^2 + \dots) \dots (nt + n^2 t^2 + \dots) \\ &= \frac{t}{1-t} \cdot \frac{2t}{1-2t} \dots \frac{nt}{1-nt} \\ &= \frac{n! \cdot t^n}{(1-t)(1-2t)\dots(1-nt)}. \end{aligned}$$
Consider now the two-variable generating function $G_n(t, y)$ defined recursively by
$$G_0(t, y) = \sum_{k=0}^{\infty} y^k t^k = \frac{1}{1 - yt}$$
and
$$G_n(t, y) = G_{n-1}(t, y+1) - G_{n-1}(t, y) \text{ for } n > 0.$$
We may identify the coefficient of $t^m$ in $G_n(t, 0)$ as the $n^{\text{th}}$ forward finite difference of the function $f(y) = y^m$. Therefore, it is given by
$$\binom{n}{n} n^m - \binom{n}{n-1} (n-1)^m + \dots + (-1)^{n-2} \binom{n}{2} 2^m + (-1)^{n-1} \binom{n}{1}.$$
(If the reader is not familiar with the theory of finite differences, the claim also follows from a straightforward induction.)
We have just shown that the two sides of the desired equality are the coefficients of $t^m$ in the generating functions $F_n(t)$ and $G_n(t, 0)$. Hence, it now suffices to show that $F_n(t) = G_n(t, 0)$. For this, we will show that
$$G_n(t, y) = \frac{n! \cdot t^n}{\prod_{i=0}^{n} (1 - (i + y)t)}$$
which would complete the proof, as this expression easily reduces to $F_n(t)$ upon taking $y = 0$.

We proceed by induction on $n$. The base case $n = 0$ is evident. Now, suppose the claim holds for some $n$; by the definition of $G_n(t, y)$, we may compute
$$\begin{align*} G_{n+1}(t, y) &= G_n(t, y+1) - G_n(t, y) \\ &= \frac{n! \cdot t^n}{\prod_{i=0}^{n} (1 - (i+y+1)t)} - \frac{n! \cdot t^n}{\prod_{i=0}^{n} (1 - (i+y)t)} \\ &= \frac{n! \cdot t^n}{\prod_{i=1}^{n} (1 - (i+y)t)} \left[ \frac{1}{1 - (y+n+1)t} - \frac{1}{1-yt} \right] \\ &= \frac{n! \cdot t^n (n+1)t}{\prod_{i=0}^{n+1} (1 - (i+y)t)} \\ &= \frac{(n+1)! \cdot t^{n+1}}{\prod_{i=0}^{n+1} (1 - (i+y)t)}, \end{align*}$$
which completes the induction.