# Computing the sum $\sum_{k=0}^{n} \binom{n}{k}(-1)^k(n-k)^n$

I need to compute $S_{n} = \sum_{k=0}^{n} \binom{n}{k}(-1)^k(n-k)^n$. $S_{2} = 2, S_{3} = 6,S_{4}=24$ therefore i think answer is $S_{n} = n!$. And i have got $S_{n}=(\Delta^n(n-x)^n)(0)$. But it gives no benefit to me..

• Have you tried induction? – MarkG Feb 23 '15 at 13:46
• Yes, but with the same result(fail). – qwenty Feb 23 '15 at 13:47
• The following MSE link may prove useful reading. – Marko Riedel Feb 23 '15 at 20:51

If you apply $n$ times the forward (backward) difference operator to a monic polynomial in $x$ having degree $n$ you get a constant that just depends on the degree of the polynomial. For a combinatorial interpretation, $n!$ is the number of bijective functions from $A=\{1,\ldots,n\}$ to $B=\{1,\ldots, n\}$. How many functions $f:A\to B$ do we have such that $|f(A)|=n-k$? Obviously $\binom{n}{k}(n-k)^n$. Conclude by inclusion-exclusion.
It's precisely the cardinality of the set $$\left\{f:\{1,2,...,n\}\to \{1,2,...,n\}\mid f\ \text{ is onto (or surjective)}\right\}$$
Moreover, you know that a function $f:\{1,...,n\}\to\{1,...,n\}$ is onto if and only if is injective and thus bijective. I let you continue.