Expressing a factorial as difference of powers: $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$?

Solution 1:

Let $A:=\{ x_1,..,x_n \}$ and $B=\{y_1,..,y_m \}$.

Lets count the number of onto functions $f:A \to B$. There are $m^n$ functions from $A$ to $B$. Lets count now the ones which are not onto:

Define

$$P_i= \{ f : A \to B |y_i \notin f(A) \}$$

Then we need to figure out the cardinality of $\cup_i P_i$.

By the inclusion exclusion principle

$$|P_1 \cup P_2 ..\cup P_m |=\sum |P_i|-\sum |P_i \cap P_j|+\sum |P_i \cap P_j \cap P_k| -... \\=\binom{m}{1}(m-1)^n-\binom{m}{2}(m-2)^n+\binom{m}{3}(m-3)^n-... $$

Thus in total there are

$$m^n-\binom{m}{1}(m-1)^n+\binom{m}{2}(m-2)^n-\binom{m}{3}(m-3)^n-...=\sum_{k=0}^m (-1)^k\binom{m}{k}(m-k)^n$$

When $n=m$ the number of onto functions is

$$\sum_{k=0}^n (-1)^k\binom{n}{k}(n-k)^n$$

But any function $f: \{ x_1,..,x_n \} \to\{y_1,..,y_n \}$ is onto if and only if it is a bijection. Thus the number of onto functions is equal to the number of bijections, which is $n!$.

Hence

$$\sum_{k=0}^n (-1)^k\binom{n}{k}(n-k)^n=n!$$

Solution 2:

This identity also has an algebraic proof. Suppose the sum we are trying to evaluate is given by $$\sum_{k=0}^n {n\choose k} (-1)^k (n-k)^{n}.$$

Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that \begin{align} A(z) B(z) &= \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ &= \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!} \end{align} i.e. the product of the two generating functions is the generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

Now in the present case we clearly have $$A(z) = \sum_{q\ge 0} (-1)^q \frac{z^q}{q!} = \exp(-z).$$ Furthermore we have $$B_n(z) = \sum_{q\ge 1} q^{n} \frac{z^q}{q!} = \exp(z) \sum_{k=1}^{n} {n\brace k} z^k,$$ as can be seen by induction. For $n=1$ we have $$B_1(z) = \sum_{q\ge 1} q \frac{z^q}{q!} = z \sum_{q\ge 1} \frac{z^{q-1}}{(q-1)!} = \exp(z)\times z.$$ Now using the induction hypothesis we have $$B_{n+1}(z) = z \frac{d}{dz} B_n(z) = z \exp(z) \sum_{k=1}^{n} {n\brace k} k z^{k-1} + z \exp(z) \sum_{k=1}^{n} {n\brace k} z^k.$$ This is \begin{align} & z \exp(z) \sum_{k=0}^{n-1} {n\brace k+1} (k+1) z^k + z \exp(z) \sum_{k=1}^{n} {n\brace k} z^k \\ &= z \exp(z) \left({n\brace 1} + \sum_{k=1}^{n-1} \left({n\brace k+1} (k+1)+{n\brace k}\right)z^k+ {n\brace n} z^{n}\right) \\ &= z \exp(z) \left({n+1\brace 1} + \sum_{k=1}^{n-1} {n+1\brace k+1} z^k + {n+1\brace n+1} z^{n}\right) \\ &= \exp(z) \left({n+1\brace 1} z + \sum_{k=1}^{n-1} {n+1\brace k+1} z^{k+1} + {n+1\brace n+1} z^{n+1}\right) = \exp(z) \sum_{k=1}^{n+1} {n+1\brace k} z^k. \end{align}

Returning to the original problem we find that the sum has the value $$n! [z^n] A(z) B_n(z) = n! [z^n] \sum_{k=1}^{n} {n\brace k} z^k = n! {n\brace n} = n!$$ which was to be shown.

A useful exercise in the algebra of Stirling numbers and binomial coefficients. Here is a MSE link that points to another calculation of the same type.

Addendum. In response to the comment we can actually show that $$\sum_{k=0}^n {n\choose k} (-1)^k (l-k)^{n}$$ for $l$ an integer.

Observe that $$l-k = (n-k)+(l-n)$$ and put $p=l-n.$ Using the same setup as before we now have \begin{align} B(z) &= \sum_{q\ge 0} (q+p)^n \frac{z^q}{q!} = \sum_{q\ge 0} \sum_{m=0}^n {n\choose m} q^m p^{n-m} \frac{z^q}{q!} \\ &= \sum_{q\ge 0} p^n \frac{z^q}{q!} + \sum_{q\ge 0} \sum_{m=1}^n {n\choose m} q^m p^{n-m} \frac{z^q}{q!} = \exp(z) p^n +\sum_{m=1}^n {n\choose m} p^{n-m} \sum_{q\ge 0} q^m \frac{z^q}{q!} \\ &= \exp(z) p^n + \exp(z) \sum_{m=1}^n {n\choose m} p^{n-m} \sum_{k=1}^m {m\brace k} z^k. \end{align} This formula also holds for $p=0$ if we assume that $0^0=1$, in which case it produces the first formula we derived above. It follows that $$n! [z^n] A(z) B_n(z) = n! [z^n] \left(p^n+\sum_{m=1}^n {n\choose m} p^{n-m} \sum_{k=1}^m {m\brace k} z^k\right) = n! {n\choose n} {n\brace n} = n!$$ thereby showing the result for all $l.$

Addendum Oct 10 2016. There is really nothing to prove here as the formula $$\frac{1}{n!} \sum_{k=0}^n {n\choose k} (-1)^{n-k} k^m$$ by definition gives the Stirling number of the second kind $${m\brace n}.$$