10
$\begingroup$

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

$\endgroup$
5
  • 3
    $\begingroup$ Look up the method of finite differences and apply it to $x^n$. There is also an inclusion-exclusion argument involving counting permutations. $\endgroup$ Commented Aug 11, 2013 at 17:35
  • $\begingroup$ @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!$. $\endgroup$ Commented Aug 11, 2013 at 17:57
  • $\begingroup$ 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. $\endgroup$
    – Evan
    Commented Aug 11, 2013 at 18:37
  • $\begingroup$ 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$ $\endgroup$ Commented Aug 21, 2018 at 21:37

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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. $$

$\endgroup$
1
  • 1
    $\begingroup$ @ZaidAlyafeai: Thanks for the comment. $\endgroup$ Commented Aug 11, 2013 at 19:59
5
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .