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$
3
  • 5
    $\begingroup$ this is just $n! S_n^n$, the Stirling number of the second kind. $\endgroup$ Oct 15, 2015 at 16:42
  • 1
    $\begingroup$ @CarloBeenakker $S_n^n=1$, yes? $\endgroup$ Oct 15, 2015 at 16:44
  • 2
    $\begingroup$ yep, it's that simple $\endgroup$ Oct 15, 2015 at 16:46

1 Answer 1

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$
2
  • $\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, 2015 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$ Oct 16, 2015 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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