Multiset Eulerian–Narayana polynomials

The multiset Eulerian–Narayana polynomial of a composition of $N$, which counts weakly increasing trees on a multiset by leaves, has degree $N-1$, only simple negative zeros and palindromic coefficients. This proves a conjecture of Lin, Ma, Ma and Zhou.

Results

Call a real polynomial $f$ admissible of degree $m$ if it has degree $m$, positive leading coefficient, nonnegative coefficients, positive constant term and only simple real zeros; then all zeros are negative. For $d\in\mathbb N$ and $a>0$ let $$ E_{d,a} f = \frac1a\Bigl(t(1-t) f' + \bigl(a + (d+a)t\bigr) f\Bigr). $$ For a composition $\alpha=(p_1,\dots,p_m)$ of $N\ge1$ with partial sums $N_j=p_1+\dots+p_j$, put $a_d(\alpha)=N_j-d$ for the least $j$ with $N_j>d$. The multiset Eulerian–Narayana polynomial is $$ P_\alpha = E_{N-2,\,a_{N-2}(\alpha)} \circ \dotsb \circ E_{0,\,a_0(\alpha)}(1). $$ By [ZZ26, Prop. 2.9], $P_\alpha$ is the leaf enumerator of weakly increasing trees on a multiset with multiplicities $\alpha$.

Theorem (Zhang–Zhao). [ZZ26] For a composition $\alpha$ of $N\ge1$, $P_\alpha$ is admissible of degree $N-1$ and palindromic: its coefficients of $t^k$ and $t^{N-1-k}$ agree for $0\le k\le N-1$. Let $Q_0=1$ and $Q_{d+1}=E_{d,a_d(\alpha)}Q_d$. Then $Q_d\ll Q_{d+1}$ and $Q_d,Q_{d+1}$ have no common zero, for $0\le d\le N-2$.

Theorem (Zhang–Zhao). [ZZ26, Thm. 1.3] Let $p,r\ge1$. Let $K_{p,r}$ be the $(p+r)\times p$ matrix whose entry in row $k$ and column $\ell$ (from $0$) is $0$ unless $\ell\le k\le\ell+r$, and then $$ \binom{p-\ell+r}{k-\ell}\binom{\ell+1+r}{r-k+\ell} \frac{(\ell+1)(p+r-k)+(p-\ell)(k-\ell)}{(\ell+1+r)(p-\ell+r)}. $$ Then $K_{p,r}$ is totally nonnegative. It is the product of the coefficient matrices of the steps $E_{p+s-1,a_s}$, $0\le s<r$, with $a_0=1$ and $a_s=r-s+1$ for $s\ge1$, each a nonnegative lower bidiagonal matrix, restricted to the first $p$ columns.

For the $\gamma$-expansion, let $a>0$ and put $\Phi_{d,a}\Gamma=\Gamma+\bigl(t(1-4t)\Gamma'+2dt\Gamma\bigr)/a$. If $\Gamma$ is admissible of degree $m$, then $\Phi_{2m,a}\Gamma$ is admissible of degree $m$ and $\Phi_{2m+1,a}\Gamma$ is admissible of degree $m+1$ [ZZ26, Lemma 3.2]. If $p=\prod_{j=1}^n(t-r_j)$ has distinct negative zeros, $d\in\{2n,2n+1\}$ and $r_i$ is replaced by $r_i+s$, then each zero $\rho$ of $\Phi_{d,a}p$ moves along a differentiable branch $\rho(s)$ of zeros with $\rho'(0)>0$ [ZZ26, Prop. 3.4].

Proof

Each step is a Darboux operator $t(1-t)f'+(a+bt)f$ with $a>0$ and $b>\deg f$. It raises the degree by one; at a zero $r$ of $f$ its value is $r(1-r)f'(r)$, which alternates in sign, so the new zeros interlace the old ones. The parameters $a_d(\alpha)$ are positive for $d<N$.

References

  1. [ZZ26] Philip B. Zhang & Tongyuan Zhao. Zeros and interlacing for multiset Eulerian--Narayana polynomials. arXiv e-prints, 2026.
    BibTeX
    @article{ZhangZhao2026x,
      author = {Philip B. Zhang and Tongyuan Zhao},
      title = {Zeros and interlacing for multiset {E}ulerian--{N}arayana polynomials},
      year = {2026},
      eprint = {2610.00966v1},
      url = {https://arxiv.org/abs/2610.00966v1},
      journal = {arXiv e-prints}
    }
  2. [LMMZ21] Zhicong Lin, Jun Ma, Shi-Mei Ma, & Yanghongbo Zhou. Weakly increasing trees on a multiset. Advances in Applied Mathematics, 129, 102206, 2021.
    BibTeX
    @article{LinMaMaZhou2021,
      author = {Lin, Zhicong and Ma, Jun and Ma, Shi-Mei and Zhou, Yanghongbo},
      title = {Weakly increasing trees on a multiset},
      year = {2021},
      journal = {Advances in Applied Mathematics},
      volume = {129},
      pages = {102206},
      doi = {10.1016/j.aam.2021.102206},
      url = {https://doi.org/10.1016/j.aam.2021.102206}
    }

Definitions

  • The first-order factor E_{d,a}

    RealRooted.MultisetEulerianNarayana.stepsource
    def step (d : ℕ) (a : ℝ) (f : ℝ[X]) : ℝ[X] :=
      C a⁻¹ * darbouxOperator a (-((d : ℝ) + a)) f
  • The multiset Eulerian–Narayana polynomial P_α

    RealRooted.MultisetEulerianNarayana.multisetEulerianNarayanasource
    def multisetEulerianNarayana (α : List ℕ) : ℝ[X] :=
      partialPoly (fun d => (prefixGap α d : ℝ)) (α.sum - 1)

Theorems

  • P_α has only simple negative zerosMain result

    RealRooted.MultisetEulerianNarayana.simpleNegRooted_multisetEulerianNarayanasource
    theorem simpleNegRooted_multisetEulerianNarayana {α : List ℕ} (hα : α.sum ≠ 0) :
        SimpleNegRooted (multisetEulerianNarayana α) (α.sum - 1)
  • Consecutive partial products interlace without common zeros

    RealRooted.MultisetEulerianNarayana.strictInterl_partialPolysource
    theorem strictInterl_partialPoly {a : ℕ → ℝ} {n : ℕ} (ha : ∀ d ≤ n, 0 < a d) :
        StrictInterl (partialPoly a n) (partialPoly a (n + 1)) ∧
          ∀ r, (partialPoly a n).IsRoot r → ¬ (partialPoly a (n + 1)).IsRoot r
  • P_α is palindromic

    RealRooted.MultisetEulerianNarayana.coeff_multisetEulerianNarayana_symmsource
    theorem coeff_multisetEulerianNarayana_symm (α : List ℕ) {k : ℕ} (hk : k ≤ α.sum - 1) :
        (multisetEulerianNarayana α).coeff k = (multisetEulerianNarayana α).coeff (α.sum - 1 - k)
  • Darboux steps preserve simple negative zeros and interlace

    RealRooted.SimpleNegRooted.darbouxOperatorsource
    theorem darbouxOperator (hf : SimpleNegRooted f d) {a b : ℝ} (ha : 0 < a) (hb : (d : ℝ) < b) :
        SimpleNegRooted (darbouxOperator a (-b) f) (d + 1) ∧
          StrictInterl f (darbouxOperator a (-b) f) ∧
          ∀ r, f.IsRoot r → ¬ (darbouxOperator a (-b) f).IsRoot r
  • Zhang–Zhao: the gamma operator preserves simple negative zeros

    RealRooted.MultisetEulerianNarayana.simpleNegRooted_gammaOperatorsource
    theorem simpleNegRooted_gammaOperator
        {d m : ℕ} {a : ℝ} {f : ℝ[X]} (ha : 0 < a)
        (hf : SimpleNegRooted f m) (hd : d = 2 * m ∨ d = 2 * m + 1) :
        (d = 2 * m ∧ SimpleNegRooted (gammaOperator d a f) m) ∨
          (d = 2 * m + 1 ∧ SimpleNegRooted (gammaOperator d a f) (m + 1))
  • Zhang–Zhao: output zeros move strictly right with each input zero

    RealRooted.MultisetEulerianNarayana.exists_hasDerivAt_gammaOperator_input_shiftsource
    theorem exists_hasDerivAt_gammaOperator_input_shift
        {n d : ℕ} {a : ℝ} {r : Fin n → ℝ} (ha : 0 < a) (hr : ∀ j, r j < 0)
        (hinj : Function.Injective r) (hd : d = 2 * n ∨ d = 2 * n + 1) (i : Fin n) {ρ : ℝ}
        (hρ : (gammaOperator d a (finRootPolynomial r)).IsRoot ρ) :
        ∃ branch : ℝ → ℝ,
          HasDerivAt branch
            ((gammaOperator d a (finRootPolynomial r / (X - C (r i)))).eval ρ /
              (gammaOperator d a (finRootPolynomial r)).derivative.eval ρ) 0 ∧
          0 < (gammaOperator d a (finRootPolynomial r / (X - C (r i)))).eval ρ /
              (gammaOperator d a (finRootPolynomial r)).derivative.eval ρ ∧
          branch 0 = ρ ∧
          ∀ᶠ s in 𝓝 0,
            (gammaOperator d a (finRootPolynomial (Function.update r i (r i + s)))).IsRoot
              (branch s)
  • Zhang–Zhao: the transition matrix has a closed binomial form

    RealRooted.MultisetEulerianNarayana.coefficientTransitionMatrix_eq_closedTransitionMatrixsource
    theorem coefficientTransitionMatrix_eq_closedTransitionMatrix {p r : ℕ} (hr : 0 < r) :
        coefficientTransitionMatrix p r = closedTransitionMatrix p r
  • Zhang–Zhao: the closed transition matrices are totally nonnegative

    RealRooted.MultisetEulerianNarayana.closedTransitionMatrix_isTotallyNonnegsource
    theorem closedTransitionMatrix_isTotallyNonneg {p r : ℕ} (hr : 0 < r) :
        (closedTransitionMatrix p r).IsTotallyNonnegRect

Lean source RealRooted/Challenges/Combinatorial/MultisetEulerianNarayana.lean at revision d6670742. Formalized 2026-10-07.