0
$\begingroup$

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$

  • 2
    Hint: the $n^{th}$ forward difference of a polynomial of degree $n$ is $n!$ times its leading coefficient.2012-04-11

2 Answers 2

1

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.

  • 0
    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$.2012-04-11
1

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.

  • 0
    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.2013-12-30