Narayana polynomials

The generalized Narayana polynomials are Pólya frequency polynomials, and the Narayana transform $x^n\mapsto N_{n,m}(x)$ preserves Pólya frequency polynomials, as do several related basis transforms and products of arrays built from them.

Results

A real polynomial is Pólya frequency (PF) if its coefficients are nonnegative and it is zero or real-rooted with all zeros $\le0$. For $m,n\ge0$ the generalized Narayana polynomial is $$ N_{n,m}(x) = \sum_{k=0}^{n} \frac{\binom{n}{k}\binom{n+m}{k}}{\binom{m+k}{k}}\, x^k . $$ For $m=1$ the coefficients are Narayana numbers; for example $N_{2,1}(x)=1+3x+x^2$.

Theorem (Narayana transform). For all $m,n\ge0$, $N_{n,m}$ is real-rooted and PF. If $p$ is PF, so is its Narayana transform, the image of $p$ under the linear map $x^n\mapsto N_{n,m}(x)$.

Proposition (Dyck paths and 132-avoiders). For $n\ge0$, the generating polynomial of Dyck paths of semilength $n+1$ by peaks is $x\,N_{n,1}(x)$, and that of the 132-avoiding permutations of $n+1$ letters by descents is $N_{n,1}(x)$. The number of Dyck paths of semilength $n$ with $k$ peaks is the Narayana number for $(n,k)\ne(1,0)$. The descent polynomials of the 132-avoiders of $n+2$ and $n+3$ letters satisfy $f\ll g$.

For polynomials $B_0,B_1,\dots$ the basis transform $T_B$ is the linear map with $T_B(x^n)=B_n(x)$. A polynomial has only nonpositive zeros if it is $0$ or real-rooted with all zeros $\le0$. Put $$ \langle x\rangle_k = x(x-1)\dotsm(x-k+1), \qquad (x \mid \mu)_k = x(x+\mu)\dotsm(x+(k-1)\mu), $$ and let $T_n$ be the Touchard polynomials, $T_0=1$ and $T_{n+1}=xT_n+xT_n'$.

Theorem (Brenti). [Bre89, Thm. 2.4.2] If $\sum_k a_k\langle x\rangle_k$ has only nonpositive zeros, then so does $\sum_k a_kx^k$.

Theorem. The Touchard transform $x^n\mapsto T_n(x)$ maps PF polynomials to PF polynomials. So does the transform $x^n\mapsto(x\mid\mu)_n$ for every $\mu>0$.

For a lower-triangular array $M=(M(n,k))_{n,k\ge0}$ the row polynomials are $M_n(x)=\sum_{k\le n}M(n,k)x^k$; we say $M$ has PF rows if every $M_n$ is PF. A matrix is a Mao–Wang factor if its row $n$ lists the coefficients of $B_n$, where $(B_n)$ is one of $(ax+d)^n$ with $a>0$, $d\ge0$; $T_n(x)$; $(x\mid\mu)_n$ with $\mu>0$; or $N_{n,m}(x)$ with $m\ge0$.

Theorem (Mao–Wang). [MW26, Thm. 1.3] Let $M$ be lower-triangular with PF rows and let $B_1,\dots,B_r$ be Mao–Wang factors. Then $MB_1\dotsm B_r$ has PF rows. In particular $MB^r$ has PF rows for every factor $B$ and $r\ge0$.

For real $\theta>-1$, the continuous Narayana interpolation is $$ N_\theta(n, k) = \binom{n}{k} \frac{(\theta + 1)_n}{(\theta + 1)_k\,(\theta + 1)_{n-k}}, \qquad P_n^{(\theta)}(t) = \sum_{k=0}^{n} N_\theta(n, k)\, t^k , $$ where $(a)_n=a(a+1)\dotsm(a+n-1)$. For $\theta=0$ these are the type B Narayana polynomials $\sum_k\binom nk^2t^k$; for $\theta=1$ they are the shifted type A Narayana polynomials.

Theorem. For every real $\theta>-1$ and $n\ge0$, $$ P_n^{(\theta)}(t) = \sum_{j \le n/2} \frac{n!}{j!\,(n - 2j)!\,(\theta + 1)_j}\, t^j (1 + t)^{n - 2j}, $$ so $P_n^{(\theta)}$ is $\gamma$-positive. Moreover $P_n^{(\theta)}$ is PF, and its zeros are real and negative. Its $\gamma$-polynomials are on the continuous Narayana interpolation page.

Proof

The root statement for $P_n^{(\theta)}$ is a Schur–Szegő composition: $P_n^{(\theta)}$ is a positive multiple of the composition of the Jensen polynomial of $1/(\theta+1)_k$ with its reversal, and that Jensen polynomial is PF because $1/(\theta+1)_k$ is a multiplier sequence.

References

See also Narayana real-rootedness examples, Brenti's falling-factorial theorem and row-generating functions on symmetricfunctions.com.

  1. [MW26] Jianxi Mao & Lijie Wang. The Narayana transformation. arXiv e-prints, 2026.
    BibTeX
    @article{MaoWang2026x,
      author = {Jianxi Mao and Lijie Wang},
      title = {The {N}arayana transformation},
      year = {2026},
      eprint = {2607.01572},
      url = {https://arxiv.org/abs/2607.01572},
      journal = {arXiv e-prints}
    }
  2. [Bre89] Francesco Brenti. Unimodal, log-concave and Pólya frequency sequences in combinatorics. Mem. Amer. Math. Soc., 81(413), viii+106, 1989.
    BibTeX
    @article{Brenti1989,
        AUTHOR = {Brenti, Francesco},
         TITLE = {Unimodal, log-concave and {P}{\'{o}}lya frequency sequences in
                  combinatorics},
       JOURNAL = {Mem. Amer. Math. Soc.},
      FJOURNAL = {Memoirs of the American Mathematical Society},
        VOLUME = {81},
          YEAR = {1989},
        NUMBER = {413},
         PAGES = {viii+106},
          ISSN = {0065-9266,1947-6221},
       MRCLASS = {05A15 (05A10 05A20)},
      MRNUMBER = {963833},
    MRREVIEWER = {Ira\ Gessel},
           DOI = {10.1090/memo/0413},
           URL = {https://doi.org/10.1090/memo/0413},
    }
  3. [DJJ13] D. Dominici, S. J. Johnston, & K. Jordaan. Real zeros of 2F1 hypergeometric polynomials. arXiv e-prints, 2013.
    BibTeX
    @article{DominiciJohnstonJordaan2013x,
      author = {D. Dominici and S. J. Johnston and K. Jordaan},
      title = {Real zeros of 2{F}1 hypergeometric polynomials},
      year = {2013},
      eprint = {1301.4771v1},
      url = {https://arxiv.org/abs/1301.4771v1},
      journal = {arXiv e-prints},
      doi = {10.1016/j.cam.2012.12.024}
    }
  4. [Zen26] Jiang Zeng. Continuous Narayana Interpolations: Hankel Total Positivity and Log-Convexity Preservation. arXiv e-prints, 2026.
    BibTeX
    @article{Zeng2026x,
      author = {Jiang Zeng},
      title = {Continuous {N}arayana {I}nterpolations: {H}ankel {T}otal {P}ositivity and {L}og-{C}onvexity {P}reservation},
      year = {2026},
      eprint = {2610.19548v3},
      url = {https://arxiv.org/abs/2610.19548v3},
      journal = {arXiv e-prints}
    }

Definitions

  • Generalized Narayana polynomials

    RealRooted.narayanaPolynomialsource
    def narayanaPolynomial (m n : ℕ) : ℝ[X] :=
      ∑ k ∈ Finset.range (n + 1), C (narayanaTransformCoeff m n k) * X ^ k
  • Narayana transform

    RealRooted.narayanaTransformsource
    def narayanaTransform (m : ℕ) : ℝ[X] → ℝ[X] :=
      basisTransform (narayanaPolynomial m)
  • Zero, or real-rooted with nonpositive zeros

    RealRooted.HasOnlyNonposRootssource
    def HasOnlyNonposRoots (p : ℝ[X]) : Prop :=
      p = 0 ∨ p.Splits ∧ ∀ r ∈ p.roots, r ≤ 0
  • The linear map sending x^n to B_n

    Polynomial.basisTransformsource
    def basisTransform (B : ℕ → R[X]) (p : R[X]) : R[X] :=
      p.sum fun n a => C a * B n
  • Falling factorials

    RealRooted.fallingFactorialPolynomialsource
    def fallingFactorialPolynomial (k : ℕ) : ℝ[X] :=
      ∏ i ∈ Finset.range k, (X - C (i : ℝ))
  • Generalized rising factorials

    RealRooted.risingFactorialPolynomialsource
    def risingFactorialPolynomial (μ : ℝ) (k : ℕ) : ℝ[X] :=
      ∏ i ∈ Finset.range k, (X + C ((i : ℝ) * μ))
  • Every row-generating polynomial is Pólya-frequency

    RealRooted.LowerTriangularMatrix.RowGeneratingFunctionsPFsource
    def RowGeneratingFunctionsPF (A : LowerTriangularMatrix ℝ) : Prop :=
      ∀ i : ℕ, IsPFPolynomial (rowPolynomial A i)
  • The Mao–Wang one-step factors

    RealRooted.LowerTriangularMatrix.MaoWangAdmissibleMatrixsource
    inductive MaoWangAdmissibleMatrix : LowerTriangularMatrix ℝ → Prop
      | affine {a d : ℝ} (ha : 0 < a) (hd : 0 ≤ d) :
          MaoWangAdmissibleMatrix (affineSubstitutionMatrix a d)
      | touchard : MaoWangAdmissibleMatrix touchardMatrix
      | rising {μ : ℝ} (hμ : 0 < μ) :
          MaoWangAdmissibleMatrix (risingFactorialMatrix μ)
      | narayana (m : ℕ) :
          MaoWangAdmissibleMatrix (narayanaMatrix m)
  • Continuous Narayana interpolation between type B and shifted type A

    RealRooted.narayanaInterpolationsource
    noncomputable def narayanaInterpolation (θ : ℝ) (n : ℕ) : ℝ[X] :=
      ∑ k ∈ range (n + 1), C (narayanaInterpolationCoeff θ n k) * X ^ k

Theorems

  • Generalized Narayana polynomials are real-rooted

    RealRooted.splits_narayanaPolynomialsource
    theorem splits_narayanaPolynomial (m n : ℕ) :
        (narayanaPolynomial m n).Splits
  • Generalized Narayana polynomials are Pólya-frequency

    RealRooted.narayanaPolynomialRootLocationsource
    theorem narayanaPolynomialRootLocation :
        ∀ m n : ℕ, IsPFPolynomial (narayanaPolynomial m n)
  • The Narayana transform preserves Pólya-frequency polynomialsMain result

    RealRooted.IsPFPolynomial.narayanaTransformsourcestatement on symmetricfunctions.com
    theorem IsPFPolynomial.narayanaTransform :
        ∀ (m : ℕ) {p : ℝ[X]},
          IsPFPolynomial p → IsPFPolynomial (RealRooted.narayanaTransform m p)
  • Brenti: nonpositive zeros in the falling-factorial basis pull back

    RealRooted.HasOnlyNonposRoots.of_basisTransform_fallingFactorialsourcestatement on symmetricfunctions.com
    theorem HasOnlyNonposRoots.of_basisTransform_fallingFactorial {p : ℝ[X]}
        (h : HasOnlyNonposRoots (basisTransform fallingFactorialPolynomial p)) :
        HasOnlyNonposRoots p
  • The Touchard transform preserves Pólya-frequency polynomials

    RealRooted.IsPFPolynomial.basisTransform_touchardsource
    theorem IsPFPolynomial.basisTransform_touchard {p : ℝ[X]} (hp : IsPFPolynomial p) :
        IsPFPolynomial (basisTransform touchard p)
  • Rising-factorial transforms preserve Pólya-frequency polynomials

    RealRooted.IsPFPolynomial.basisTransform_risingFactorialsource
    theorem IsPFPolynomial.basisTransform_risingFactorial {μ : ℝ} (hμ : 0 < μ) {p : ℝ[X]}
        (hp : IsPFPolynomial p) :
        IsPFPolynomial (basisTransform (risingFactorialPolynomial μ) p)
  • Mao–Wang: products with admissible factors keep Pólya-frequency rows

    RealRooted.LowerTriangularMatrix.RowGeneratingFunctionsPF.mul_listProductsource
    theorem LowerTriangularMatrix.RowGeneratingFunctionsPF.mul_listProduct {M : LowerTriangularMatrix ℝ}
        {Bs : List (LowerTriangularMatrix ℝ)} (hBs : ∀ B ∈ Bs, MaoWangAdmissibleMatrix B)
        (hM : RowGeneratingFunctionsPF M) :
        RowGeneratingFunctionsPF (LowerTriangularMatrix.mul M (listProduct Bs))
  • Mao–Wang: powers of an admissible factor keep Pólya-frequency rows

    RealRooted.LowerTriangularMatrix.RowGeneratingFunctionsPF.mul_powsource
    theorem LowerTriangularMatrix.RowGeneratingFunctionsPF.mul_pow {M B : LowerTriangularMatrix ℝ}
        (hB : MaoWangAdmissibleMatrix B) (r : ℕ) (hM : RowGeneratingFunctionsPF M) :
        RowGeneratingFunctionsPF (LowerTriangularMatrix.mul M (LowerTriangularMatrix.pow B r))
  • Dyck paths of semilength n with k peaks are Narayana-counted, except n = 1, k = 0

    DyckWord.card_semilength_peakCountsource
    theorem card_semilength_peakCount (n k : ℕ) (h : ¬(n = 1 ∧ k = 0)) :
        Fintype.card {p : {p : DyckWord // p.semilength = n} // p.1.peakCount = k} =
          Nat.narayana n k
  • The peak polynomial of Dyck paths is x N_{n,1}(x)

    DyckWord.peakGeneratingPolynomial_eq_narayanaPolynomialsource
    theorem peakGeneratingPolynomial_eq_narayanaPolynomial (n : ℕ) :
        peakGeneratingPolynomial (n + 1) =
          X * RealRooted.narayanaPolynomial 1 n
  • 132-avoiding permutations counted by descents give N_{n,1}(x)

    RealRooted.Avoid132.descentGeneratingPolynomial_succ_eq_narayanaPolynomialsource
    theorem descentGeneratingPolynomial_succ_eq_narayanaPolynomial (n : ℕ) :
        Finset.genPoly (R := ℝ) (Equiv.Perm.avoiders (n + 1) [⟨3, SimionSchmidt.p132⟩])
          Equiv.Perm.descentCount = narayanaPolynomial 1 n
  • Descent polynomials of 132-avoiders are real-rooted and interlace

    RealRooted.Avoid132.strictInterl_descentGeneratingPolynomial_succsource
    theorem strictInterl_descentGeneratingPolynomial_succ (n : ℕ) :
        StrictInterl
          (Finset.genPoly (R := ℝ) (Equiv.Perm.avoiders (n + 2) [⟨3, SimionSchmidt.p132⟩])
            Equiv.Perm.descentCount)
          (Finset.genPoly (R := ℝ) (Equiv.Perm.avoiders (n + 3) [⟨3, SimionSchmidt.p132⟩])
            Equiv.Perm.descentCount)
  • γ-expansion of the continuous Narayana interpolation

    RealRooted.narayanaInterpolation_eq_sum_gammasource
    theorem narayanaInterpolation_eq_sum_gamma {θ : ℝ} (hθ : -1 < θ) (n : ℕ) :
        narayanaInterpolation θ n =
          ∑ j ∈ range (n / 2 + 1),
            C ((n.factorial : ℝ) /
              ((j.factorial : ℝ) * (n - 2 * j).factorial *
                (ascPochhammer ℝ j).eval (θ + 1))) *
              X ^ j * (1 + X) ^ (n - 2 * j)
  • The continuous Narayana interpolation is Pólya-frequency for θ > −1

    RealRooted.narayanaInterpolation_isPFsource
    theorem narayanaInterpolation_isPF {θ : ℝ} (hθ : -1 < θ) (n : ℕ) :
        IsPFPolynomial (narayanaInterpolation θ n)
  • The zeros of the continuous Narayana interpolation are real and negative

    RealRooted.narayanaInterpolation_roots_negsource
    theorem narayanaInterpolation_roots_neg {θ : ℝ} (hθ : -1 < θ) (n : ℕ) :
        ∀ r ∈ (narayanaInterpolation θ n).roots, r < 0

Lean source RealRooted/Challenges/Combinatorial/Narayana.lean at revision d6670742. Formalized 2026-07-18.