3
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

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

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