8
$\begingroup$

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

$\endgroup$
  • 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$ – Qiaochu Yuan 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$ – user2566092 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$ – Jérôme JEAN-CHARLES Aug 21 '18 at 21:37
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$
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
    $\begingroup$ @ZaidAlyafeai: Thanks for the comment. $\endgroup$ – Mhenni Benghorbal Aug 11 '13 at 19:59
3
$\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$

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.