# Show this equality (The factorial as an alternate sum with binomial coefficients).

Why does the following equality hold? $$n!=\sum_{k=1}^n (-1)^{n-k} \binom{n}{k} k^n$$

• Look up the method of finite differences and apply it to $x^n$. There is also an inclusion-exclusion argument involving counting permutations. Aug 11 '13 at 17:35
• @QiaochuYuan can you post the proof based on counting permutations? That seems like the most "informative" combinatorics type of proof, but I don't see how it would go because it seems like for $k$ around $n/2$ you start adding and subtracting terms that are actually larger than $n!$. Aug 11 '13 at 17:57
• It seems like from the form of the sum, you would start with number of ways to arrange books $\{1,\ldots,n\}$ on a bookshelf with $n$ slots, allowing for repeats. And then start shaving off groups of configurations that aren't permutations. For instance, $\binom{n}{n-1} (n-1)^n$ seems like the ways to to arrange while only using $n-1$ of the books (so not a permutation), etc.
– Evan
Aug 11 '13 at 18:37
• You may remove the bound for $k$ as terms vanish for $k$ negative or above $n$. Moreover the formula will work for $n=0$ as $0!=1$ Aug 21 '18 at 21:37
• Dec 1 '18 at 10:36

Recalling the identity

$$\left\{\begin{matrix} n \\ k \end{matrix}\right\} =\frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}{k \choose j} j^n ,$$

where $\left\{\begin{matrix} n \\ k \end{matrix}\right\}$ is the Stirling numbers of the second kind. Now, substituting $k=n$ in the above identity gives the desired result

$$\left\{\begin{matrix} n \\ n \end{matrix}\right\}=1 =\frac{1}{n!}\sum_{j=0}^{n}(-1)^{n-j}{n \choose j} j^n \implies n!= \sum_{j=0}^{n}(-1)^{n-j}{n \choose j} j^n.$$

• @ZaidAlyafeai: Thanks for the comment. Aug 11 '13 at 19:59

Apply $\left(x \frac{d}{dx}\right)^n$ to both sides of the identity $(1-x)^n = \sum_{0 \leq k \leq n} \binom{n}{k} (-1)^k x^k$, then evaluate at $x=1$.

Consider if we were to permute numbers $1$ to $n$. Obviously left hand side $n!$ denotes the number of such permutations.

Using the complement version of inclusion-exclusion principle: (Link to Wikipedia, formula copied from Wikipedia)

\begin{align*} \biggl|\bigcap_{i=1}^n \overline{A_i}\biggr| &= \biggl|S - \bigcup_{i=1}^n A_i\biggr|\\ &= \left| S \right| - \sum_{i=1}^n\left|A_i\right| +\sum_{1 \le i < j \le n}\left|A_i\cap A_j\right| - \ldots + \left(-1\right)^{n} \left|A_1\cap\cdots\cap A_n\right| \end{align*}

If we let $A_i$ be the set of $n$-length sequences that have no $i$s (for $i = 1 \ldots\ n$), and $\overline{A_i}$ be the set of $n$-length sequences that have some $i$s, then the intersection $\bigcap_{i=1}^n \overline{A_i}$ gives all those sequences that have some $1$s, some $2$s, ..., and some $n$s. In other words, the intersection gives all $n$-length permutations.

And when we simplify the right hand side of the above formula, we get the right hand side of your question, where first term is for $k = n$ and the second-last term for $k = 1$. The last term of the above formula is zero in this case.