How can you compute the asymptotics of

$$T=\sum_{k=1}^{n} k^{k-1} (n-k)^{2n-k} \binom{n}{k}\;?$$

This is related to Asymptotics of sum of binomials .

I attempted to simply use Stirling's approximation. This gives you

$$T \approx U =\frac{n^{n+1/2}}{\sqrt{2\pi}}\sum_{k=1}^n \frac{(n-k)^{n-1/2}}{k^{3/2}}$$

This approximation $U$ seems to be some constant times $n^{2n}$ asymptotically and also for $T$ itself.

By experimentation it looks like

$$T \sim \frac{n^{2n}}{2\pi}.$$

Is this correct?

Update. No it isn't.


The summand is decreasing with $k$:

$$ \sum_{k=1}^n k^{k-1} (n-k)^{2n-k} \binom{n}{k} = n^{2n} \sum_{k=1}^n \left(\frac{k}{n}\right)^{k-1} \left(1-\frac{k}{n}\right)^{2n-k} \frac{1}{n} \binom{n}{k} $$ We can now use the fact that $$ \lim_{n \to \infty} \left(\frac{k}{n}\right)^{k-1} \left(1-\frac{k}{n}\right)^{2n-k} \frac{1}{n} \binom{n}{k} = \frac{k^{k-1}}{k!} \left( \frac{1}{\mathrm{e}^2} \right)^k $$ Thus $$ \sum_{k=1}^n k^{k-1} (n-k)^{2n-k} \binom{n}{k} \rightarrow_{n \to \infty} n^{2n} \sum_{k=1}^\infty \frac{k^{k-1}}{k!} \left( \frac{1}{\mathrm{e}^2} \right)^k = n^{2n} \left( -W\left(-\frac{1}{\mathrm{e}^2}\right)\right) = n^{2n} \exp\left( W\left(-\mathrm{e}^{-2}\right) - 2 \right) $$ where $W(z)$ denotes the Lambert $W$-function. Note that $$ \left( -W\left(-\frac{1}{\mathrm{e}^2}\right)\right) \approx 0.158594 < 0.159155 \approx \frac{1}{2\pi} $$ Numerically it seems that estimate is from above:

enter image description here

  • $\begingroup$ Umm, I don't see how you can replace with $\frac{k^{k-1}}{k!} e^{-2k}$ like that. Can't you apply the same logic to $S_n = \sum_{k=1}^{n} \frac{1}{k \log n}$? On the other hand, if you are talking about an upper bound... $\endgroup$
    – Aryabhata
    Apr 17 '13 at 0:40
  • $\begingroup$ @Sasha Could you add some justification for that step? I am pretty sure your conclusion is correct however. It shows the dangers of guessing based on numerical results as my guess was really close numerically but wrong. $\endgroup$
    – user66151
    Apr 17 '13 at 11:56

Since the terms in the sum are decaying very fast, we can restrict the sum to small values of $k$ and use an asymptotic estimate that has a small error for large $n$ and small $k$. In more detail, if $$a_k = \binom n k k^{k-1} (n-k)^{2n-k},$$ then $$\frac {a_{k+1}} {a_k} = \left( 1 + \frac 1 k \right)^{k-1} \left( 1 - \frac 1 {n-k} \right)^{2n-2k} \left( 1 - \frac 1 {n-k} \right)^{k-1} < \frac 1 e, \\ \sum_{k = \ln^2 n + 1}^n a_k < a_1 \sum_{k = \ln^2 n}^{n - 1} e^{-k} = O \left( n^{2n} e^{-\ln^2 n} \right),$$ thus the tail will be negligible compared to all the terms in the expansion $n^{2n} \left( c_0 + \frac {c_1} n + \dots \right)$. On the other hand, for large $n$, $$a_k = \frac {k^{k-1} e^{-2 k}} {k!} n^{2 n} \left( 1 - \frac {k^2 - k} {2 n} + O \left(\frac {k^4} {n^2} \right) \right), \\ \sum_{k=1}^{\ln^2 n} a_k = n^{2 n} \left( \sum_{k=1}^{\ln^2 n} \frac {k^{k-1} e^{-2 k}} {k!} \left( 1 - \frac {k^2 - k} {2 n} \right) + O \left(\frac {\ln^{10} n} {n^2} \right) \right),$$ once we prove that the $O$ term is uniform in $k$.

Using the same reasoning, we can now extend the summation range on the right-hand side to infinity, as the contribution from the tail is $O(e^{-\ln^2 n})$. This yields the Lambert W-function. The second term contains the factors $k^p$, which correspond to applying the operators $\left( z \frac d {dz} \right)^p$ to the W-function. After simplifications, $$\sum_{k=1}^n \binom n k k^{k - 1} (n - k)^{2 n - k} \sim n^{2 n} \left( \alpha - \frac {\alpha^2 (2 - \alpha)} {2(1 - \alpha)^3 n} + \dots \right), \\ \alpha = -W \!\left(-e^{-2} \right).$$


Your Answer

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