2
$\begingroup$

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!

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

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Acapello Oct 16 '15 at 14:53
  • $\begingroup$ 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)$. $\endgroup$ – David E Speyer Oct 16 '15 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.