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

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.
