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}$ I want to ask if there is a slick way to prove:
$$\sum_{j=0}^n{(-1)^j{{n}\choose{j}}\left(1-\frac{j}{n}\right)^n}=\frac{n!}{n^n}$$
Edit:
I know Yuval has given a proof, but that one is not direct. I am requesting for a direct algebraic proof of this identity.
Thanks.
 A: Start with 
$$\sum_{j=0}^{n} (-1)^j \binom{n}{j} (1+x)^{n-j} = x^n$$
which follows readily from the binomial theorem.
Now differentiate, and multiply by $\displaystyle (1+x)$. Repeat this $\displaystyle n$ times and set $\displaystyle x = 0$.
Notice that the constant term of the resulting polynomial on the right side is $\displaystyle n!$. 
You can prove by induction that the lowest degree of $\displaystyle x$ that appears on the right side after $\displaystyle k$ steps ($0 \lt \displaystyle k \le n$) is $\displaystyle x^{n-k}$ and has the coefficient $\displaystyle n(n-1)\dots(n-k+1)$.
This gives us the set of identities
$$\sum_{j=0}^{n} (-1)^j \binom{n}{j} (n-j)^{k} = 0, \ \ 0 \le k \lt n$$
$$\sum_{j=0}^{n} (-1)^j \binom{n}{j} (n-j)^{n} = n!$$
I also seem to recollect there was a proof involving $\displaystyle \log x$, I will update this answer later if I remember it.
A: This is inclusion-exclusion for counting the number of onto maps from $n$ to $n$.
A: Lemma: Let $f(j) = \sum_{k=0}^n f_k j^k$ be a degree $n$ polynomial. I claim that $\sum_{j=0}^{n} (-1)^j \binom{n}{j} f(j) = n! f_n$. 
Proof: For any polynomial $g$, define $\Delta(g)$ to be the polynomial $\Delta(g)(j) = g(j) - g(j+1)$. Observe that, if $g$ is a polynomial with leading term $a x^d + \cdots$, then $\Delta(g)$ is a polynomial with leading term $-d a x^{d-1} + \cdots$. In particular, if $f$ is as in the statement of the lemma, then $\Delta^n(f)$ is the constant $(-1)^n n! f_n$. The sum in question is $\Delta^n(f)$ evaluated at $0$. QED
Now, apply the lemma to $f(j) = (1-j/n)^n$.
A: This answer is similar to Moron's but I think is somewhat simpler.  Expand $(e^x-1)^n$ using the binomial theorem to obtain $$(e^x-1)^n = \sum_{j=0}^n (-1)^{n-j} \binom{n}{j} e^{jx}.$$  Differentiate both sides $n$ times.  Every term on the left-hand side will contain an $e^x-1$ factor except for an $n!e^{nx}$ term, and the right side will be $$\sum_{j=0}^n (-1)^{n-j} \binom{n}{j} j^n e^{jx}.$$  Then substitute $x = 0$ to obtain 
$$n! = \sum_{j=0}^n (-1)^{n-j} \binom{n}{j} j^n.$$  Reindex the sum and divide by $n^n$.  
A: The result follows immediately if you know the Stirling Numbers of the second kind, and it's combinatoric  meaning. Not an algebraic proof, though.
Update:
In table 4 of these Combinatorial Identities it is stated an identity that -I believe- is equivalent to yours:
$ \displaystyle \sum_{k=0}^n (-1)^k {n \choose k} k^j = (-1)^n n!$
if $j=n$, (zero otherwise). And it just say that this is a "Statement of Euler's finite difference theorem". I don't know what this means, and I would like to know.
Update 2:
Indeed, the identity follows from the formula of the n-th finite difference, taking the function $f(x)=x^j$
A: Let n be fixed , and 
f(x) = (x-n)^n

The standard result in finite difference state that if f is a polynomial of degree n , then 
Δ^n(f) = n!
Now , the lhs of the given identity is exactly (1/n^n)Δ^n(f)(0) , and the result follows.
Q.E.D.
