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

Solution 1:

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.

Solution 2:

This is inclusion-exclusion for counting the number of onto maps from $n$ to $n$.