# Maximum of $\sum_{k=0}^{P} (-1)^{k+P}\binom{P}{k} k^N$ with $P\leq N$

For a combinatorics problem, I would need to identify the value of $$P$$ that maximizes the function

$$\Omega(P) = \sum_{k=0}^{P} (-1)^{k+P}\binom{P}{k} k^N$$

with $$P\leq N$$. Numerically, I see that the maximum is roughly located at $$P=3N/4$$, but I don't know how to prove it.

I am wondering whether an extrapolation of $$\Omega$$ to real values of $$P$$ could be found, which would simplify the search for a maximum. Any idea?

Thanks a lot!

I'm going to use lower case letters instead of upper. The sum can be expressed as $$p! \, S(n,p),$$ where $$S(n,p)$$ is the Stirling number of the second kind. We can use asymptotic expansions of Stirling numbers to solve your problem for $$n \to \infty.$$ I want to reproduce analytically your observed zeroth order approximation, $$p^*=\frac{3}{4}n.$$ To find a maximum, take a derivative and set to zero, and an approximation to a derivative in $$p$$ is the difference

$$\Delta_p \; p!S(n,p) = (p-1)!\big( p S(n,p) - S(n,p-1) \big) = 0$$ That is, to find $$p^*$$ we want $$p$$ such that

$$p=\frac{S(n,p-1)}{S(n,p)} = \frac{S(n+1,p)}{S(n,p)} - p$$ where the recursion relation has been used. Now most approximations to the Stirling numbers of second kind depend on solving a transcendental equation (perhaps the Lambert W is involved.) However, Guy Louchard in 'Asymptotics of the Stirling numbers of the second kind revisited' records a formula (among many) that is good enough in the region of interest, and is due to Moser and Wyman. It can be written as $$S(n,p) \sim \binom{n}{p}\Big(\frac{2}{p}\Big)^{p-n} .$$

Insert, simplify, and we have the simple equation

$$p=\frac{1}{2} \frac{(n+1)p}{2(1+n-p)}$$ which has two solutions, one of which is $$p^*=\frac{3}{4}(n+1).$$

I've made plots of the approximation using the binomial and simple factor vs. the ratio of Stirling numbers, and the approximate curve results in a root that is a bit too large, but not terribly so. To go beyond the zeroth order would seem to be a tedious analytic task, and it depends on whether the Lambert W is in your toolbox.

Added 11/29/2021 With an expansion found in arXiv 1506.00699v1 that implies a more accurate $$S(n,p)$$ in the vicinity where the line $$p$$ intersects it, a more complicated equation for p can be derived:

$$p=\frac{\sqrt{(n+1)n}}{2\log{2}}\exp\Big(\frac{n(n+1)-4p^2\log^2{2}}{n(n+1)+2(\log{2} -1)} \Big)$$

An exact solution can be found in terms of the Lambda W. Instead, take the solution and expand it asymptotically as $$n\to\infty.$$ Using some facts about the Lambert W and some simplification, then it can be shown

$$p^* \sim \frac{1}{2\log{2}}\big(n+\frac{1}{2}-\frac{1}{8n} +...\big)$$

This solution shows the true zeroth order factor is $$1/(2\log{2}) \approx 0.72135$$, which is about 4% less than the empirically derived factor of 0.75 by the OP.

• Thank you very much for this !! This zeroth order approximation is more than enough for what I need. Nov 29 '21 at 8:56
• @hugues_myr Thanks. Consider clicking the accept button. Nov 29 '21 at 16:19

Hint: Consider the differences $$\Omega(P+1)-\Omega(P)$$, and use Pascal's identity.