5
$\begingroup$

Consider the polynomial:

$$p(x) = \sum_{k=0}^{r}(-1)^{r-k} {r \choose k} x^{k(k-1) / 2}$$

I want to show that

$$p(x) = (x - 1)^{\lceil r/2 \rceil} \, q(x)$$

That is, $(x - 1)^{\lceil r/2 \rceil}$ is a factor of $p(x)$. Even better, find a formula for the quotient polynomial $q(x)$.

This problem arises when trying to compute the central moments of the log-normal distribution. Raw moments of this distribution are given by $M_r = \left< x^r \right> = e^{r\mu + \frac{1}{2} r^2 \sigma^2}$. So central moments are

$$C_r = \left< (x - M_1)^r \right> = \sum_{k=0}^{r} {r \choose k} M_k \, (-M_1)^{r-k} \\ = e^{r(\mu + \frac{1}{2}\sigma^2)} \sum_{k=0}^{r} (-1)^{r-k} {r \choose k} e^{\frac{1}{2}k(k-1)\sigma^2}$$

You will recognize the sum in this expression as the polynomial in the problem above. Using Mathematica or a similar program, it's easy to test that the alleged property holds for any particular $r$ you care to test. For numerical work, it's valuable to be able to express $C_r$ in factored form because there are catastrophic cancellations in the original form.

Presumably this comes down to some binomial identity with which I am unfamiliar.

$\endgroup$
7
$\begingroup$

$s$-th derivative of $p$ at 1 equals $$\sum_{k=0}^{r}(-1)^{r-k} {r \choose k} g_s(k),$$ where $g_s$ is a polynomial of degree $2s$. This equals 0 if $2s<r$.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Brilliant! Took me 15 minutes to comprehend each bit, but this is a fine proof.I messed around a bit more to see if there s some way I could construct $q(x)$ from the derivatives of $p(x)$, but that doesn't seem to be working out for me. Polynomial division isn't really a good approach, numerically. I don't suppose you see a way to construct $q(x)$ from this result? Thanks, in any case. $\endgroup$ – David Wright Mar 28 '17 at 8:31
  • $\begingroup$ You may write $q(x)=p(x)\cdot (1-x)^{-m}$, $m=\lceil r/2\rceil$, and look at this as a power series. This gives some formulae for coefficients of $q$. I do not know whether this is ok for you. $\endgroup$ – Fedor Petrov Mar 28 '17 at 9:14
  • $\begingroup$ In fact, $\sum_{k=0}^r (-1)^{r-k}\binom{r}{k}k^n = r!\cdot S(n,r)$, where $S(,)$ are Stirling numbers of second kind, and they are zero if $n<r$. $\endgroup$ – Max Alekseyev Mar 28 '17 at 21:59
7
$\begingroup$

Here is a combinatorial proof. Let $$t(x)=p(x+1)=\sum_{k=0}^r (-1)^{r-k}\binom rk (1+x)^{\binom k2}.$$ We want to show that $t(x)$ is divisible by $x^{\left\lceil r/2\right\rceil}$.

The coefficient of $x^j$ in $t(x)$ is the number of graphs with vertex set $\{1,2,\dots, r\}$, $j$ edges, and no isolated vertices. This can be proved easily using inclusion-exclusion or properties of exponential generating functions. The coefficients of these polynomials, with this combinatorial interpretation, can be found in the OEIS as sequence A054548 or A276639.

Since a graph with $r$ vertices and no isolated vertices must have at least $\left\lceil r/2\right\rceil$ edges, $t(x)$ is divisible by $x^{\left\lceil r/2\right\rceil}$.

It's interesting to note that the cumulants of the log-normal distribution are related to the inversion enumerator for labeled trees.

Additional comment: Here's a more detailed explanation of the combinatorial interpretation. Let $$ u_n(x) = \sum_G x^{e(G)}, $$ where the sum is over all graphs $G$ with vertex set $[n]:=\{1,2,\dots,n\}$ and $e(G)$ is the number of edges of $G$, and let $$ t_n(x) = \sum_H x^{e(H)}, $$ where the sum is over all graphs $H$ with vertex set $[n]$ and no isolated vertices. Then $$u_n(x) = \sum_{k=0}^n \binom nk t_k(x)$$ since any graph with vertex set $[n]$, and with $n-k$ isolated vertices, can be specified by choosing a $k$-subset $S$ of $[n]$, constructing a graph without isolated vertices with vertex set $S$, and leaving the elements of $[n]\setminus S$ as isolated vertices. This may be inverted to give $$t_n(x) = \sum_{k=0}^n (-1)^{n-k}\binom nk u_k(x).$$

But $u_n(x) = (1+x)^{\binom n2}$, since a graph with vertex set $[n]$ may be specified by including or not including each of the $\binom n2$ possible edges. Therefore $$t_n(x) = \sum_{k=0}^n (-1)^{n-k}\binom nk (1+x)^{\binom n2}.$$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you so much for providing this answer! Not only this another nice proof (although, for me, not quite as accessible as Fedor's), but your linked paper actually provides a numerically useful recurrence for lognormal cumulants. I have been coming back to this little problem for years, and had never come across the paper you linked to. This is the second time an obscure Riordan paper has solved a moment problem for me; I'm going to have to get this guy's collected works. $\endgroup$ – David Wright Mar 30 '17 at 3:32
  • 1
    $\begingroup$ I've added a more detailed explanation of the combinatorial interpretation. $\endgroup$ – Ira Gessel Mar 30 '17 at 14:49

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.