# Prove that $n! = \sum_{i=0}^{n-1}{n \choose i}(n-i)^n (-1)^i$ [duplicate]

Prove that product of $n(n-1)(n-2)\dots(2)(1)$ i.e.

$$n! = \sum_{i=0}^{n-1}{n \choose i}(n-i)^n (-1)^i$$

-

## marked as duplicate by Aryabhata, Qiaochu YuanApr 11 '12 at 0:59

You can get your $\TeX$ input formatted by enclosing it in single dollar signs (inline) or double dollar signs (displayed). – joriki Apr 11 '12 at 0:18
Hint: the $n^{th}$ forward difference of a polynomial of degree $n$ is $n!$ times its leading coefficient. – Qiaochu Yuan Apr 11 '12 at 0:38

Let $[n]:=\{1,2,\cdots ,n\}$. Consider a map from [n] onto itself. $A_i :=$ all such maps for which $i$ doesn't belong to the image of the map. Then, use the Principle for Inclusion and Exclusion.

-
This isn’t quite right: you want $A_i$ to be the set of maps whose ranges miss $i$ elements of $[n]$, not those whose ranges simply miss the number $i$. – Brian M. Scott Apr 11 '12 at 0:57

There are $n^n$ maps from $[n]=\{1,\dots,n\}$ to $[n]$; $n!$ of them are bijections. Let $F_i$ be the set of maps from $[n]$ to $[n]$ whose ranges miss at least $i$ elements of $[n]$. Thus, $F_0$ is the collection of all $n^n$ maps from $[n]$ to $[n]$, and $F_{n-1}$ is the set of all constant maps from $[n]$ to $[n]$.

Suppose that $f:[n]\to[n]$ misses $i$ members of $[n]$; then $f$ is a map from $[n]$ to an $(n-i)$-element subset of $[n]$. There are $(n-i)^n$ such maps, and there are $\binom{n}i$ $i$-element subsets of $[n]$, so $|F_i|=\binom{n}i(n-i)^n$.

Now just use the inclusion-exclusion principle.

-
If $F_1$ is the set of all maps that miss at least 1 element, then what are you excluding from it? Why isn't it the complement to the set of bijections? I'm having trouble understanding. – Flowers Dec 30 '13 at 6:21