Problem: the number $a(n,k)$ is defined by the following recurrence \begin{equation} a(n,k)=(k+1)(k+2)\, a(n-1, k)+\frac{(k+1)(k+2)(k+3)}{k} \,a(n-1, k-1), \end{equation} with $a(1,1)=1$ and $a(n,k)=0$ if $k<1$ or $k>n$.

For fixed $n$, the generating polynomial of $a(n,k)$ is defined as $A_n(x)=\sum_{k=1}^n a(n,k)x^k$. The recurence above is equivalent to the following differential equation $$ \frac{\mathrm{d}}{\mathrm{d}x} A_{n+1}(x) =24 A_n(x)+(36x+6)\frac{\mathrm{d}}{\mathrm{d}x} A_{n}(x)+(12x^2+6x)\frac{\mathrm{d}^2}{\mathrm{d}x^2} A_{n}(x)+(x^3+x^2)\frac{\mathrm{d}^3}{\mathrm{d}x^3} A_n(x). $$

Question 1: all roots of $A_n(x)$ are real?

Question 2: $A_n(x)$ interlaces $A_{n+1}(x)$? i.e. $$ b_1 \leq a_1 \leq b_2 \leq a_2 \leq \cdots \leq b_n \leq a_n \leq b_{n+1}, $$ where $\{a_i\}$ and $\{b_j\}$ are roots of $A_n(x)$ and $A_{n+1}(x)$, respectively.

Question 3: all roots of $A_n(x)$ are located in $(-1,0]$?

These three statements are verified to be true for $n\leq 50$.

Some examples of $A_n(x)$ are given \begin{eqnarray*} A_1(x) &=& x, \\ A_2(x) &=& 6x + 30 x^2,\\ A_3(x) &=& 36x + 540 x^2+ 1200 x^3,\\ A_4(x) &=& 216x + 7560 x^2+ 45600 x^3 +63000 x^4. \end{eqnarray*}

Background of this problem: this number arises from certain graph enumeration problem.

One can easily prove the log-concavity of $\{a(n,k)\}_k$ by induction. Many literatures on real-rootedness or interlacing deal with recurrences with polynomial coefficients or first and second order differential equations, not for this example. Any things about these numbers and polynomials would also be appreciated.

Progress: as pointed out by Per Alexandersson (see below reply), the linear differential operator $p\mapsto 24 p +(36x+6)p' + (12x^2+6x)p'' + (x^3+x^2)p'''$ preserves real-rootedness. This show that if $A_n(x)$ has only real zeros, so does the right hand side of the differential equation.

Notice that if a polynomial $f$ has only real zeros, the primitive integral $\int f dx$ of $f$ could have complex zeros in general. I am wondering, under what conditions of $f$, primitive integral $\int f dx$ has only real zeros. (Assume that the constant term of $\int f dx$ is zero.)


1 Answer 1


Well, if you can show that the linear differential operator $p\mapsto 24 p +(36x+6)p' + (12x^2+6x)p'' + (x^3+x^2)p'''$ preserves real-rootedness, then you are a bit closer.

Now, this can be attacked by proving that the symbol of this operator is stable, see


It will be some work; you end up with a 2-variable polynomial, and you want to show that this is non-zero whenever both variables have positive real part.

Now, it is quite easy to see that in "the limit", i.e, for large degrees of your polynomial $p$, this operator preserves real-rootedness, since then only the $(x^3+x^2)p'''$ term matters. And $(x^3+x^2)$ has roots 0 and -1, so it is not surprising that you get [-1,0] as the special interval.

  • $\begingroup$ To prove that the symbol of the operator is stable, is there a standard way to find out those positive semidefinite symmetric matrices? And I can see the the -1 and 0 coming from the leading coefficients, just like the dominant singularity. But any results in real stable polynomials or other areas could facilitate a proof of these bounds? $\endgroup$
    – Thomas Li
    Feb 21, 2014 at 21:10
  • $\begingroup$ Finding the psd-matrices is one way to do it; but you can prove stability in other ways as well. I am no expert in this field, but have a look at the papers by Brändén. $\endgroup$ Feb 21, 2014 at 21:58
  • $\begingroup$ Thank you! Now I understand the real-rootedness of RHS of the differential equation. $\endgroup$
    – Thomas Li
    Feb 26, 2014 at 13:00

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.