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!

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

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented 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$
    – David E Speyer
    Commented Oct 16, 2015 at 15:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .