Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Proof of a combination identity:$\sum \limits_{j=0}^n{(-1)^j{{n}\choose{j}}\left(1-\frac{j}{n}\right)^n}=\frac{n!}{n^n}$

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

share|cite|improve this question

marked as duplicate by Aryabhata, Qiaochu Yuan Apr 11 '12 at 0:59

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

2 Answers 2

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.

share|cite|improve this answer
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.

share|cite|improve this answer
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

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