9
$\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$ Aug 11 '13 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$ Aug 11 '13 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
    Aug 11 '13 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$ Aug 21 '18 at 21:37
5
$\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$ Aug 11 '13 at 19:59
4
$\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$
4
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.