# Asymptotic of a sum involving binomial coefficients

Good evening, I'm trying to find an asymptotic of this sum:

$$\sum_{j=0}^n (-1)^j {n \choose j} (n - j)^n = n^n - {n \choose 1} (n - 1)^n + {n \choose 2} (n - 2)^n + ... + (-1)^n {n \choose n} (n - n)^n$$

I think there is no close form. But I don't know how to calculate an asymptotics than. Maybe I should try to approximate it by some integral?

Thank you for any help!

• this is just $n! S_n^n$, the Stirling number of the second kind. – Carlo Beenakker Oct 15 '15 at 16:42
• @CarloBeenakker $S_n^n=1$, yes? – David E Speyer Oct 15 '15 at 16:44
• yep, it's that simple – Carlo Beenakker Oct 15 '15 at 16:46

Separate the different roles that $n$ plays in this sum, and look at $$\sum_{j=0}^n (-1)^j \binom{n}{j} (x-j)^n.$$ If $f(x)=f_n x^n + (\mbox{lower order terms})$ is any polynomial of degree $n$, then $\sum_{j=0}^n (-1)^j \binom{n}{j} f(x-j)$ is $n! f_n$. So your sum is equal to $n!$, and asymptotics are given by Stirling's formula.
• Thank you very much. I'm not fluent in math and some thinks in your answers not clear to me(like that sum is $$n! f_n$$, but I know what to investigate(Stirling number of the second kind). – Acapello Oct 16 '15 at 14:53
• If you are not fluent in math, you probably want to be at math.stackexchange, not mathoverflow. I might suggest en.wikipedia.org/wiki/Finite_difference as a good starting point for sums like $\sum (-1)^j \binom{n}{j} f(x-j)$. – David E Speyer Oct 16 '15 at 15:34