Asymptotics of sum of binomials

Question

How can you compute the asymptotics of

$$S=n + m - \sum_{k=1}^{n} k^{k-1} \binom{n}{k} \frac{(n-k)^{n+m-k}}{n^{n+m-1}}\;?$$

We have that $n \geq m$ and $n,m \geq 1$.

A simple application of Stirling's approximation gives

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

A more accurate approximation is given by

$$n+m- \frac{\left(1+\frac{1}{12 n}\right) n }{\sqrt{2 \pi }} \sum _{k=1}^{n-1} \frac{ (1-\frac{k}{n})^{m-\frac{1}{2}}}{\left(1+\frac{1}{12 k}\right) k^{3/2} \left(1+\frac{1}{12 (n-k)}\right) }$$

Via an indirect and handy wavy argument, my guess is guess for constant $m$ is that the answer is

$$S \sim \sqrt{2n} \frac{\Gamma(m+\frac{1}{2})}{(m-1)!}$$

Update. When $m$ grows almost as quickly as $n$ I think my guess is an underestimate. For example when $n=m$ it seems numerically that $S \sim 1.841 n$ and in fact if $n=m$ then it is suggested that $S \sim n\left(2-\left( -W\left(-\frac{1}{\mathrm{e}^2}\right)\right)\right)$ (see Is $\sum_{k=1}^{n} k^{k-1} (n-k)^{2n-k} \binom{n}{k} \sim\frac{n^{2n}}{2\pi} $?).

Update 2. When $m=1$ then $S$ is precisely the average number of people required to find a pair with the same birthday. This is solved at the wikipedia entry for the Birthday Problem and so $S \sim \sqrt{\frac{\pi n}{2}}$ (which equals my guess above). I would however ideally like to find the asymptotics in terms of $m$ and $n$ without assuming that $m$ is fixed.

Update 3. For the $m=1$ case we can prove that the correct asymptotics is $\sqrt{\frac{\pi n}{2}}$ in two ways.

• We will first show the result using the following identity.

$$n + 1 - \sum_{k=1}^{n} k^{k-1} \binom{n}{k} \frac{(n-k)^{n+1-k}}{n^{n+1-1}}=1 + \sum_{k=1}^n \frac{n!}{(n-k)!n^k} = 1+Q(n)$$

The numerator of the sum on the left is $n^{n+1}-Q(n)n^n$ (Q(n) is called Ramanujan's function by Knuth) according to A219706 and A063169. This immediately gives the identity.

We also know that $Q(n) \sim \sqrt{\frac{\pi n}{2}}$ from the wikipedia (is there a better reference?).

• The second proof follows from the amazing answer of GEdgar where he shows that

$$\sum_{k=1}^n \binom{n}{k} k^{k-1}(n-k)^{n-k+1} = n^n\Bigg( n -\frac{\sqrt{2\pi}}{2} n^{1/2} + \frac{1}{3} -\frac{\sqrt{2\pi}}{24} n^{-1/2} +\frac{4}{135}n^{-1} -\frac{\sqrt{2\pi}}{576}n^{-3/2} +O\left(n^{-2}\right)\Bigg) $$

Answer 1

My first answer showed that small $k$ play a major role in the sum. Since Stirling is an asymptotic approximation, the approximation for small $k$ was not be good enough. My second answer showed that Stirling should be used for $n!$ and $(n-k)!$ since they will be large. My third approach overvalued $\left(1-\frac{k}{n}\right)^{m-1/2}$. This approach uses the series for the Lambert W function given in $(9)$ and approximations given in $(10)$. $$ \begin{align} &\sum_{k=1}^nk^{k-1}\binom{n}{k}\frac{(n-k)^{n+m-k}}{n^{n+m-1}}\\ &=\sum_{k=1}^n\left(1+O\left(\frac{k}{n^2}\right)\right)\frac{n^{n+1/2}}{(n-k)^{n-k+1/2}}\frac{k^{k-1}}{k!\,e^k}\frac{(n-k)^{n+m-k}}{n^{n+m-1}}\\ &=n\sum_{k=1}^n\left(1+O\left(\frac{k}{n^2}\right)\right)\frac{k^{k-1}}{k!\,e^k}\left(1-\frac{k}{n}\right)^{m-1/2}\tag{11} \end{align} $$ If we let $\alpha=\dfrac{m-1/2}{n}$, then $\left(1-\dfrac{k}{n}\right)^{m-1/2}\le e^{-k\alpha}$. Therefore, using the approximation for $\mathrm{W}'(x)$ given in $(10)$, we get $$ \begin{align} n\sum_{k=1}^n\frac{k}{n^2}\frac{k^{k-1}}{k!\,e^k}\left(1-\frac{k}{n}\right)^{m-1/2} &\le\frac1n\sum_{k=1}^nk\frac{k^{k-1}}{k!\,e^{k(1+\alpha)}}\\ &=\frac1n\mathrm{W}'(-e^{-1-\alpha})\\ &\le\frac1n\frac{e^2}{\sqrt{2\alpha}}\\ &=\frac{e^2}{\sqrt{(2m-1)n}}\tag{12} \end{align} $$ Thus, the big-O term in $(11)$ is insignificant. Using the series for $\mathrm{W}(x)$ from $(9)$ and remembering that $\mathrm{W}(-1/e)=-1$ $$ \begin{align} n\sum_{k=1}^n\frac{k^{k-1}}{k!\,e^k}\left(1-\frac{k}{n}\right)^{m-1/2} &=n\sum_{k=1}^n\frac{k^{k-1}}{k!\,e^k}\\ &-n\sum_{k=1}^n\frac{k^{k-1}}{k!\,e^k}\left(1-\left(1-\frac{k}{n}\right)^{m-1/2}\right)\\ &=n-n\sum_{k=n+1}^\infty\frac{k^{k-1}}{k!\,e^k}\\ &-n\sum_{k=1}^n\frac{k^{k-1}}{k!\,e^k}\left(1-\left(1-\frac{k}{n}\right)^{m-1/2}\right)\tag{13} \end{align} $$ Now we can use Stirling to approximate $\dfrac{k^{k-1}}{k!\,e^k}=\dfrac{k^{-3/2}}{\sqrt{2\pi}} +O\left(k^{-5/2}\right)$.

First, we evaluate the tail from the first sum in $(13)$ $$ \begin{align} n\sum_{k=n+1}^\infty\frac{k^{k-1}}{k!\,e^k} &=n\sum_{k=n+1}^\infty\left(\frac{k^{-3/2}}{\sqrt{2\pi}}+O\left(k^{-5/2}\right)\right)\\[6pt] &=\frac{2\,n^{1/2}}{\sqrt{2\pi}}+O\left(n^{-1/2}\right)\tag{14} \end{align} $$ Next, the error term in the second sum in $(13)$ $$ \begin{align} &n\sum_{k=1}^nk^{-5/2}\left(1-\left(1-\frac{k}{n}\right)^{m-1/2}\right)\\ &\le\left(\sum_{n=1}^\infty k^{-3/2}\right) \,\sup_k\left\{\frac{n}{k}\left(1-\left(1-\frac{k}{n}\right)^{m-1/2}\right)\right\}\\[6pt] &\le\zeta(3/2)(m-1/2)\tag{15} \end{align} $$ Finally, the main term in the second sum in $(13)$ is a Riemann Sum in disguise $$ \begin{align} &n\sum_{k=1}^n\dfrac{k^{-3/2}}{\sqrt{2\pi}}\left(1-\left(1-\frac{k}{n}\right)^{m-1/2}\right)\\ &=\frac{n^{1/2}}{\sqrt{2\pi}}\sum_{k=1}^n\left(\frac{k}{n}\right)^{-3/2}\left(1-\left(1-\frac{k}{n}\right)^{m-1/2}\right)\frac1n\\ &\sim\frac{n^{1/2}}{\sqrt{2\pi}}\int_0^1x^{-3/2}\left(1-(1-x)^{m-1/2}\right)\,\mathrm{d}x\\ &=\frac{2\,n^{1/2}}{\sqrt{2\pi}}\int_0^{\pi/2}\frac{\cos(u)-\cos^{2m}(u)}{\sin^2(u)}\,\mathrm{d}u\\ &=\frac{2\,n^{1/2}}{\sqrt{2\pi}}\int_0^{\pi/2}\left(-1+\sum_{k=0}^{2m-1}\cos^k(u)\right)\frac{\mathrm{d}u}{1+\cos(u)}\\ &=\frac{2\,n^{1/2}}{\sqrt{2\pi}}\int_0^{\pi/2}\left(-\frac1{1+\cos(u)}+\sum_{k=0}^{m-1}\cos^{2k}(u)\right)\,\mathrm{d}u\\ &=-\frac{2n^{1/2}}{\sqrt{2\pi}}+\frac{2\,n^{1/2}}{\sqrt{2\pi}}\sum_{k=0}^{m-1}\int_0^{\pi/2}\cos^{2k}(u)\,\mathrm{d}u\\ &=-\frac{2n^{1/2}}{\sqrt{2\pi}}+\frac{2\,n^{1/2}}{\sqrt{2\pi}}\sum_{k=0}^{m-1}\frac\pi2\frac1{4^k}\binom{2k}{k}\\ &=-\frac{2n^{1/2}}{\sqrt{2\pi}}+\frac{\pi\,n^{1/2}}{\sqrt{2\pi}}\frac{2m}{4^m}\binom{2m}{m}\tag{16} \end{align} $$ The last step uses the identity $\displaystyle\sum_{k=0}^{m-1}\frac1{4^k}\binom{2k}{k}=\frac{2m}{4^m}\binom{2m}{m}$.

Putting together $(11)-(14)$ yields $$ n+m-\sum_{k=1}^nk^{k-1}\binom{n}{k}\frac{(n-k)^{n+m-k}}{n^{n+m-1}}=\sqrt{2\pi n}\frac{m}{4^m}\binom{2m}{m}+O(m-1/2)\tag{17} $$ Using Stirling to approximate $\dfrac1{4^m}\binom{2m}{m}\sim\dfrac1{\sqrt{\pi m}}$, $(17)$ gives, for large $m$, $$ n+m-\sum_{k=1}^nk^{k-1}\binom{n}{k}\frac{(n-k)^{n+m-k}}{n^{n+m-1}} \sim\sqrt{2mn}\tag{18} $$ as my earlier answers did.

---

Further Considerations

The case where $m=\alpha n$, for some constant $\alpha$, cannot be handled by $(17)$ since the error term is $O(m)=O(\alpha n)$ and that would be similar in size to $\sqrt{2mn}=\sqrt{2\alpha}n$. To handle this case, we start with the sum at the beginning of $(13)$ $$ \begin{align} n\sum_{k=1}^n\frac{k^{k-1}}{k!\,e^k}\left(1-\frac{k}{n}\right)^{m-1/2} &\sim n\sum_{k=1}^\infty\frac{k^{k-1}}{k!\,e^{k(1+\alpha)}}\\ &=-n\mathrm{W}(-e^{-1-\alpha}) \end{align} $$

Thus, $$ n+m-\sum_{k=1}^nk^{k-1}\binom{n}{k}\frac{(n-k)^{n+m-k}}{n^{n+m-1}} \sim n(1+\alpha+\mathrm{W}(-e^{-1-\alpha}))\tag{19} $$ For $m=n$, where $\alpha=1$, this is $n\left(2+\mathrm{W}(-e^{-2})\right)=n\,1.84140566043696063785$

---

Derivation of the series for $\mathrm{W}(x)$

Here is an identity we will use later $$ \begin{align} &\sum_{k=1}^{n-1}\binom{n-1}{k-1}k^{k-1}(n-k)^{n-k-1}\\ &=\sum_{k=1}^{n-1}\binom{n-1}{k-1}k^{k-1}\sum_{j=0}^{n-k-1}\binom{n-k-1}{j}n^{j}(-1)^{n-k-j-1}k^{n-k-j-1}\tag{1}\\ &=\sum_{j=0}^{n-2}n^{j}(-1)^{n-j-1}\sum_{k=1}^{n-j-1}\binom{n-1}{k-1}(-1)^k\binom{n-k-1}{j}k^{n-j-2}\tag{2}\\ &=\sum_{j=0}^{n-2}n^{j}(-1)^{n-j-1}\sum_{k=1}^{n-1}\binom{n-1}{k-1}(-1)^k\binom{n-k-1}{j}k^{n-j-2}\tag{3}\\ &=\sum_{j=0}^{n-2}n^{j}(-1)^{n-j-1}\binom{n-1}{n-1}(-1)^{n-1}\binom{-1}{j}n^{n-j-2}\tag{4}\\ &=(n-1)n^{n-2}\tag{5} \end{align} $$ $(1)$: binomial theorem

$(2)$: change order of summation

$(3)$: add terms where $\binom{n-k-1}{j}=0$

$(4)$: $\sum\limits_{k=1}^n\binom{n-1}{k-1}(-1)^k\binom{n-k-1}{j}k^{n-j-2}=0$ since $\binom{n-k-1}{j}k^{n-j-2}$ is a degree $n-2$ polynomial in $k$

$(5)$: each term in the sum was $n^{n-2}$

---

Taking the log-derivative of $we^w=x$ gives $\frac{w'}{w}+w'=\frac1x$ which yields the equation $$ w=w'(1+w)x\tag{6} $$ from which we will derive a recursion for the power series for $\mathrm{W}(x)$. Suppose that $$ \mathrm{W}(x)=\sum_{n=1}^\infty\frac{a_n}{n!}x^n\tag{7} $$ Using $we^w=x$ and equations $(6)$ and $(7)$, we get that $a_k$ satisfy $a_0=0$, $a_1=1$, and $$ \begin{align} \frac{a_n}{n!} &=n\frac{a_n}{n!} +\sum_{k=1}^{n-1}k\frac{a_k}{k!}\frac{a_{n-k}}{(n-k)!}\\ -(n-1)\,a_n &=\sum_{k=1}^{n-1}\binom{n}{k}k\,a_ka_{n-k}\\ &=\sum_{k=1}^{n-1}\binom{n-1}{k-1}n\,a_ka_{n-k}\\ a_n &=-\frac{n}{n-1}\sum_{k=1}^{n-1}\binom{n-1}{k-1}a_ka_{n-k}\tag{8} \end{align} $$ Putting together $(5)$ and $(8)$, we get that $$ \mathrm{W}(x)=\sum_{n=1}^\infty\frac{(-n)^{n-1}}{n!}x^n\tag{9} $$

---

Behavior of $\mathrm{W}(x)$ for $x\sim-1/e$

For $\alpha$ near $0$, $$ \begin{align} \mathrm{W}\left(-e^{-1-\alpha}\right) &\doteq-1+\sqrt{2\alpha}-\frac13\sqrt{2\alpha}^2+\frac7{36}\sqrt{2\alpha}^3\\ \mathrm{W}'\left(-e^{-1-\alpha}\right) &\doteq\frac{e^{1+\alpha}}{\sqrt{2\alpha}}\left(1-\frac23\sqrt{2\alpha}-\frac1{12}\sqrt{2\alpha}^2\right)\\ \mathrm{W}''\left(-e^{-1-\alpha}\right) &\doteq-\frac{e^{2+2\alpha}}{\sqrt{2\alpha}^3}\left(1-\frac{19}{12}\sqrt{2\alpha}^2\right) \end{align}\tag{10} $$

Answer 2

Computation for constant $m$ positive integer. This uses the same method as in Estimate $\sum_{k=1}^{n} k^{k-1} \binom{n}{k} (n-k)^{n+1-k}$ , further explanation is there.

Write \begin{equation*} u_{-1}(z) = \sum_{n=1}^\infty \frac{n^{n-1}}{n!} z^n \tag{1}\end{equation*} Then the unique singularity nearest to the origin is at $z=e^{-1}$, and we have an expansion there: \begin{equation*} u_{-1}(z) = 1 - \sqrt{2}(1-ez)^{1/2}+\frac{2}{3}(1-ez) +O\left((1-ez)^{3/2}\right) \tag{2}\end{equation*} as $z \to e^{-1}$ from the left. Define recursively $u_m(z) = z u_{m-1}'(z)$ for $m = 0,1,2,\dots$. Then we have \begin{equation*} u_m(z) = \sum_{n=0}^\infty \frac{n^{n+m}}{n!}z^n \tag{3}\end{equation*} by induction. To expand these at $e^{-1}$ we will also need the expansion of $z$: \begin{equation*} z = e^{-1} - e^{-1}(1-ez) = e^{-1} +O\left((1-ez)^1\right) \tag{4}\end{equation*} Now differentiate (2) and multiply by (4) to get \begin{align*} u_0(z) = \frac{1}{\sqrt{2}}(1-ez)^{-1/2}-\frac{2}{3} +O\left((1-ez)^{1/2}\right) \tag{5}\end{align*} Differentiate this and multiply by (4) to get \begin{align*} u_1(z) &= \frac{1}{2\sqrt{2}} (1-ez)^{-3/2} +O\left((1-ez)^{-1/2}\right) \\ &= \frac{\Gamma(3/2)}{\sqrt{2\pi}} (1-ez)^{-3/2} +O\left((1-ez)^{-1/2}\right) \end{align*} Continuing, by induction we get \begin{equation*} u_m(z) = \frac{\Gamma(m+1/2)}{\sqrt{2\pi}}(1-ez)^{-m-1/2} +O\left((1-ez)^{-m+1/2}\right) \tag{6}\end{equation*} for $m \ge 1$.

Now fix positive integer $m$. (The extra term $-2/3$ in (5) mean that the formula for $m=0$ is different, but can also be done by this method.) Multiply (1) and (3) to get \begin{equation*} h(z) := u_{-1}(z)u_m(z) = \sum_{n=1}^\infty\left(\frac{1}{n!} \sum_{k=1}^n \binom{n}{k}\frac{k^{k-1}}{k!}\, \frac{(n-k)^{n-k+m}}{(n-k)!}\right)z^n =:\sum_{n=1}^\infty c_n z^n \end{equation*} Multiply (2) and (6) to get $$ h(z) = \frac{\Gamma(m+1/2)}{\sqrt{2\pi}}(1-ez)^{-m-1/2} -\frac{\Gamma(m+1/2)}{\sqrt{\pi}}(1-ez)^{-m} +O\left((1-ez)^{-m+1/2}\right) $$ as $z \to e^{-1}$ from the left. So by the Szegö method, we get an asymptotic series \begin{align*} c_n &\approx e^n\left[ \frac{\Gamma(m+1/2)}{\sqrt{2\pi}}\binom{n+m-1/2}{n} -\frac{\Gamma(m+1/2)}{\sqrt{\pi}}\binom{n+m-1}{n}+\dots \right] \\ c_n &= e^n\Bigg[ \frac{\Gamma(m+1/2)}{\sqrt{2\pi}}\left( \frac{1}{\Gamma(m+1/2)}n^{m-1/2}+O(n^{m-3/2})\right) \\ &\qquad\qquad -\frac{\Gamma(m+1/2)}{\sqrt{\pi}}\left( \frac{1}{(m-1)!}n^{m-1} +O\left(n^{m-2}\right) \right) +O\left(n^{m-3/2}\right) \Bigg] \\ &= e^n\left[\frac{1}{\sqrt{2\pi}}n^{m-1/2} -\frac{\Gamma(m+1/2)}{(m-1)!\sqrt{\pi}}n^{m-1}+O\left(n^{m-3/2}\right)\right] \end{align*} as $n \to \infty$.

Multiply by Stirling's formula, $$ n! = e^{-n}n^n\sqrt{2\pi}\left( n^{1/2}+O\left(n^{-1/2}\right)\right) $$ to get \begin{align*} &\sum_{k=1}^n\binom{n}{k} \frac{k^{k-1} (n-k)^{n-k+m}}{n^{n+m-1}} = c_n\frac{n!}{n^{n+m-1}} % \\ &\qquad = n - \frac{\sqrt{2}\,\Gamma(m+1/2)}{(m-1)!}\,n^{1/2} + O\left(1\right) \end{align*} so \begin{align*} S &= n+m-\sum_{k=1}^n\binom{n}{k} \frac{k^{k-1} (n-k)^{n-k+m}}{n^{n+m-1}} \\ &= n+O\left(1\right) -n + \frac{\sqrt{2}\,\Gamma(m+1/2)}{(m-1)!}\,n^{1/2} + O\left(1\right) \\ &= \frac{\sqrt{2}\,\Gamma(m+1/2)}{(m-1)!}\,n^{1/2} + O\left(1\right) \end{align*} as $n \to \infty$, since $m$ is constant.