Improve this page

#Catalan families

This page collects real-rootedness results from Catalan combinatorics: Dyck paths, ballot sequences, Motzkin paths, and related families. Many examples below are Sturm sequences, so consecutive polynomials interlace and every polynomial in the sequence is real-rooted. Other examples use Hadamard products, stable-polynomial refinements, or Pólya frequency and total-positivity methods. For the broader context, see unimodality and real-rootedness.

Example (Narayana polynomials).

Let \(P_n(t)\coloneqq \sum_{\pi \in Dyck(n)} t^{peaks(\pi)},\) where \(Dyck(n)\) is the set of Dyck paths of size \(n,\) and \(peaks(\pi)\) counts the number of peaks. Equivalently, this counts descents in binary words with \(n\) zeros and \(n\) ones such that, in each prefix, there are at least as many zeros as ones; see A001263. A closed-form formula is \[P_n(t) = \frac{1}{n} \sum_{k=1}^n \binom{n}{k} \binom{n}{k-1} t^k.\] These satisfy the recursion (see [Eq. (2), Sul02] and [Eq. (3.3), LW07]) \[(n+1) P_n(t) = (2n-1)(1+t)P_{n-1}(t) - (n-2)(1-t)^2 P_{n-2}(t),\] with initial conditions \(P_1(t)=t,\) \(P_2(t)=t(1+t),\) which is used to prove the interlacing property.

Real-rootedness and the interlacing property were first proved in [Br06]. See also [Eq. (31), Aga14], where a different recursive formula, involving derivatives, is listed: \[(n+1)(n+2) P_{n+1} = t\bigl((1-t)^2 P''_{n} + 2(1+2n)(1-t)P'_{n} + (1+2n)(2+2n)P_n\bigr).\] Another approach is given in [KMS09].


NN[1] := t;
NN[2] := t (1 + t);
NN[n_] := NN[n] = Expand[
    (
        (2 n - 1) (1 + t) NN[n - 1] -
        (n - 2) (1 - t)^2 NN[n - 2]
)/(n + 1)];

It is useful to keep the proof methods separate. The recurrence above gives a Sturm-sequence proof; the differential recurrence can be handled by interlacing criteria for derivative recurrences; stable multivariate refinements give a stability proof; and the Narayana transformation explains why the type \(A\) and type \(B\) Narayana bases preserve real roots on nonnegative coefficient cones.

One can also prove real-rootedness by observing that the Narayana polynomials are a simple transformation of Jacobi polynomials, or Gegenbauer polynomials (which are orthogonal polynomials on an interval). The Narayana polynomials are given by the hypergeometric series \[P_n(t) = {}_2F_1(-n, -n-1;2;t)\] or, in Wolfram-language notation, HypergeometricPFQ[-n, -n - 1, 2, t], see [Sec. 12, BH11].

Yet another recurrence is \[(1 + n)P_n=(3nt + n - t - 1) P_{n-1} - 2 t(t-1) P'_{n-1}\] which can be proved using the first theorem in [Dun22].

S.-M. Ma, J. Yeh, and Y.-N. Yeh give a context-free grammar for the Narayana polynomials [MYY23]. Their differential-operator framework also gives standard-Young-tableau interpretations for several Eulerian and Narayana-type polynomial families.

H. R. L. Yang and P. B. Zhang introduce stable multivariate refinements of the type \(A\) and type \(B\) Narayana polynomials [YZ24]. Their polynomials are generating functions for labeled plane trees with weights recording improper edges, and real stability is proved using the Borcea–Brändén characterization of stability-preserving linear operators. F. Chapoton and G.-N. Han study the roots of the Poupard and Kreweras polynomials [CH20].

Example (Type \(B\) Narayana polynomials).

The type \(B\) Narayana polynomials can be defined as \[P_n(t) = \sum_{k=0}^n \binom{n}{k}^2 t^k.\] Since these are produced by the Hadamard product of \((1+t)^n\) with itself, it follows that the \(P_n(t)\) are also real-rooted. See the Hadamard product subsection for a general statement. They also occur as the type \(B\) endpoint of the Narayana transformation discussed on the main real-rootedness page.

Example (Generalized Narayana polynomials).

A two-parameter family of Narayana-type polynomials \[P_{n,m}(t) = \sum_{k=0}^n \left(\binom{n}{k}\binom{m}{k} -\binom{n}{k+1}\binom{m}{k-1} \right)t^k\] is considered in [Thm. 1.4, CYZ18]; the authors use a fairly general recurrence relation to obtain interlacing roots.

Example (Boolean–Narayana numbers).

A family similar to the Narayana numbers, named the Boolean–Narayana numbers, is introduced by M. Bóna in [Bon26]. The corresponding polynomials are proved to be real-rooted. \[BoNa(n,k) = \frac{1}{n}\binom{n}{k-1} \sum_{j=0}^{k-1}2^j\binom{k-1}{j}\binom{n-k+1}{j+1}.\] If we define \(P_n(x) \coloneqq \sum_{k} BoNa(n,k)x^k,\) then these satisfy the recursion \[(n+1) P_n(x) = (2n-1)(1+x) P_{n-1}(x) - (n-2)(1-6x+x^2) P_{n-2}(x).\]

Example (NNE instances in Dyck paths with fixed number of peaks).

In [WZ24], the authors consider the polynomials \[W_{n,k}(t) \coloneqq [x^k] \sum_{\pi \in Dyck(n)} x^{\mathrm{peaks}(\pi)} t^{\mathrm{nne}(\pi)},\] where \(\mathrm{nne}(\pi)\) counts the number of North-North-East instances in the path. The authors show that \(\{ W_{n,k}(t) \}_{n \geq k}\) for fixed \(k\) form a Sturm sequence, and that \(\{ W_{n,k}(t) \}_{1\leq k \leq n}\) is Sturm-unimodal.

Conjecture (P. Alexandersson, 2023).

The generalization to Fuss–Catalan paths (in an \(n \times nm\) rectangle) seems to be real-rooted as well.

The following formula appears in [BDLL+25].

Let \(w_{n,k,m}\) be the number of Dyck paths of size \(n,\) with \(k\) instances of \(NE\) and \(m\) instances of \(NNE.\) Then the polynomials defined via \[W_{n,k}(t) = \sum_{m\geq 0} w_{n,k,m}t^m = \frac{1}{k} \binom{n}{k-1} \sum_{m=1}^{\min(k,n-k)} \binom{n-k-1}{m-1}\binom{k}{m} t^m\] are real-rooted. The formula above is valid for \(n \gt k,\) and for \(n \leq k\) the polynomials are constant. The authors conjectured that for fixed \(k,\) \(\{W_{n,k}\}_{n\geq k}\) form a Sturm sequence, and that for fixed \(n,\) \(\{W_{n,k}\}_{1 \leq k\leq n}\) is Sturm-unimodal. These conjectures were later proved in [WZ24]. They find a two-term recurrence involving \(W_{n-1,k}(t).\) Alternatively, \(W_{n,k}(t)\) can be expressed in terms of \(W_{n,k-1}(t)\) and its derivative.

Example (Motzkin polynomials).

The noncrossing matching polynomial of the complete graph \(K_n\) is the Motzkin polynomial, see A055151. These polynomials satisfy the recursion \[(n+2)M_n(x) = (2n+1)M_{n-1}(x) - (n-1)(1-4x)M_{n-2}(x), \qquad M_1(x)=1,\quad M_2(x)=x+1.\] Using the methods in [Sec. 3, Wag92], one can use induction to show that the roots of \(M_{n-1}(x)\) interlace those of \(M_{n}(x).\) In particular, these polynomials are real-rooted.

Bibliography

  1. [Aga14]José Agapito. On symmetric polynomials with only real zeros and nonnegative $\gamma$-vectors. Linear Algebra and its Applications, 451:260–289, June 2014.
    .bib
    @article{Agapito2014,
  doi = {10.1016/j.laa.2014.03.018},
  url2 = {https://doi.org/10.1016/j.laa.2014.03.018},
  year = {2014},
  month = jun,
  publisher = {Elsevier {BV}},
  volume = {451},
  pages = {260--289},
  author = {Jos{\'{e}} Agapito},
  title = {On symmetric polynomials with only real zeros and nonnegative $\gamma$-vectors},
  journal = {Linear Algebra and its Applications}
}
  2. [BH11]Paul Barry and Aoife Hennessy. A note on Narayana triangles and related polynomials, Riordan arrays, and MIMO capacity calculations. Journal of Integer Sequences, 14(11.3.8), 2011.
    .bib
    @article{BarryHennessy2011,
  Author        = {Paul Barry and Aoife Hennessy},
  Title         = {A Note on {N}arayana Triangles and Related Polynomials, {R}iordan Arrays, and {MIMO} Capacity Calculations},
  Year          = {2011},
  journal       = {Journal of Integer Sequences},
  Volume        = {14},
  Number        = {11.3.8},
  Url           = {https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry2/barry126.pdf}
}
  3. [Bon26]Miklos Bona. Boolean-Narayana numbers. arXiv:2602.11355, 2026.
    .bib
    @article{Bona2026x,
Author = {Miklos Bona},
Title = {Boolean-{N}arayana numbers},
Year = {2026},
Eprint = {2602.11355},
  url = {https://arxiv.org/abs/2602.11355},
journal = {arXiv e-prints}
}
  4. [BDLL+25]Miklós Bóna, Stoyan Dimitrov, Gilbert Labelle, Yifei Li, Joseph Pappe, Andrés R. Vindas-Meléndez and Yan Zhuang. A combinatorial proof of a symmetry for a refinement of the Narayana numbers. The Electronic Journal of Combinatorics, 32(2), June 2025.
    .bib
    @article{BonaDimitrovLabelleLiPappeVindasMelendezZhuang2025,
  title = {A Combinatorial Proof of a Symmetry for a Refinement of the {N}arayana Numbers},
  volume = {32},
  ISSN = {1077-8926},
  url = {http://dx.doi.org/10.37236/12681},
  DOI = {10.37236/12681},
  number = {2},
  journal = {The Electronic Journal of Combinatorics},
  publisher = {The Electronic Journal of Combinatorics},
  author = {Bóna,  Miklós and Dimitrov,  Stoyan and Labelle,  Gilbert and Li,  Yifei and Pappe,  Joseph and Vindas-Meléndez,  Andrés R. and Zhuang,  Yan},
  year = {2025},
  month = jun
}
  5. [Br06]Petter Brändén. On linear transformations preserving the Pólya frequency property. Transactions of the American Mathematical Society, 358(8):3697–3716, February 2006.
    .bib
    @article{Branden2006,
  title = {On linear transformations preserving the {P}{\'{o}}lya frequency property},
  volume = {358},
  ISSN = {1088-6850},
  url = {http://dx.doi.org/10.1090/S0002-9947-06-03856-6},
  DOI = {10.1090/s0002-9947-06-03856-6},
  number = {8},
  journal = {Transactions of the American Mathematical Society},
  publisher = {American Mathematical Society (AMS)},
  author = {Br{\"a}nd{\'e}n, Petter},
  year = {2006},
  month = feb,
  pages = {3697--3716}
}
  6. [CH20]Frédéric Chapoton and Guo-Niu Han. On the roots of the Poupard and Kreweras polynomials. Moscow Journal of Combinatorics and Number Theory, 9(2):163–172, 2020.
    .bib
    @article{ChapotonHan2020,
  author = {Fr{\'e}d{\'e}ric Chapoton and Guo-Niu Han},
  title = {On the roots of the {P}oupard and {K}reweras polynomials},
  year = {2020},
  journal = {Moscow Journal of Combinatorics and Number Theory},
  volume = {9},
  number = {2},
  pages = {163--172},
  doi = {10.2140/moscow.2020.9.163}
}
  7. [CYZ18]Herman Z. Q. Chen, Arthur L. B. Yang and Philip B. Zhang. The real-rootedness of generalized Narayana polynomials related to the Boros–Moll polynomials. Rocky Mountain Journal of Mathematics, 48(1), February 2018.
    .bib
    @article{ChenYangZhang2018,
  title = {The real-rootedness of generalized {N}arayana polynomials related to the {B}oros--{M}oll polynomials},
  volume = {48},
  ISSN = {0035-7596},
  url = {http://dx.doi.org/10.1216/RMJ-2018-48-1-107},
  DOI = {10.1216/rmj-2018-48-1-107},
  number = {1},
  journal = {Rocky Mountain Journal of Mathematics},
  publisher = {Rocky Mountain Mathematics Consortium},
  author = {Chen,  Herman Z.Q. and Yang,  Arthur L.B. and Zhang,  Philip B.},
  year = {2018},
  month = feb
}
  8. [Dun22]Nguyen Tien Dung. Some identities for the Narayana polynomial and its derivatives. arXiv:2206.08949, 2022.
    .bib
    @article{Dung2022x,
Author = {Nguyen Tien Dung},
Title = {Some identities for the {N}arayana polynomial and its derivatives},
Year = {2022},
Eprint = {2206.08949},
  url = {https://arxiv.org/abs/2206.08949},
journal = {arXiv e-prints}
}
  9. [KMS09]Vladimir P. Kostov, Andrei Martínez-Finkelshtein and Boris Z. Shapiro. Narayana numbers and Schur–Szegő composition. Journal of Approximation Theory, 161(2):464–476, December 2009.
    .bib
    @article{KostovFinkelshteinShapiro2009,
  title = {Narayana numbers and {S}chur--{S}zeg{\H{o}} composition},
  volume = {161},
  ISSN = {0021-9045},
  url = {http://dx.doi.org/10.1016/j.jat.2008.10.013},
  DOI = {10.1016/j.jat.2008.10.013},
  number = {2},
  journal = {Journal of Approximation Theory},
  publisher = {Elsevier BV},
  author = {Kostov,  Vladimir P. and Martínez-Finkelshtein,  Andrei and Shapiro,  Boris Z.},
  year = {2009},
  month = dec,
  pages = {464–476}
}
  10. [LW07]Lily L. Liu and Yi Wang. A unified approach to polynomial sequences with only real zeros. Advances in Applied Mathematics, 38(4):542–560, May 2007.
    .bib
    @article{LiuWang2007,
  doi = {10.1016/j.aam.2006.02.003},
  url2 = {https://doi.org/10.1016/j.aam.2006.02.003},
  year = {2007},
  month = may,
  publisher = {Elsevier {BV}},
  volume = {38},
  number = {4},
  pages = {542--560},
  author = {Lily L. Liu and Yi Wang},
  title = {A unified approach to polynomial sequences with only real zeros},
  journal = {Advances in Applied Mathematics}
}
  11. [MYY23]Shi-Mei Ma, Jean Yeh and Yeong-Nan Yeh. Differential operators, grammars and Young tableaux. arXiv:2312.02830, 2023.
    .bib
    @article{MaYehYeh2023x,
  author = {Shi-Mei Ma and Jean Yeh and Yeong-Nan Yeh},
  title = {Differential operators, grammars and {Y}oung tableaux},
  year = {2023},
  eprint = {2312.02830},
  url = {https://arxiv.org/abs/2312.02830},
  journal = {arXiv e-prints}
}
  12. [Sul02]Robert A. Sulanke. The Narayana distribution. Journal of Statistical Planning and Inference, 101(1-2):311–326, February 2002.
    .bib
    @article{Sulanke2002,
  doi = {10.1016/s0378-3758(01)00192-6},
  url2 = {https://doi.org/10.1016/s0378-3758(01)00192-6},
  year = {2002},
  month = feb,
  publisher = {Elsevier {BV}},
  volume = {101},
  number = {1-2},
  pages = {311--326},
  author = {Robert A. Sulanke},
  title = {The {N}arayana distribution},
  journal = {Journal of Statistical Planning and Inference}
}
  13. [Wag92]David G Wagner. Total positivity of Hadamard products. Journal of Mathematical Analysis and Applications, 163(2):459–483, January 1992.
    .bib
    @article{Wagner1992,
  doi = {10.1016/0022-247x(92)90261-b},
  url2 = {https://doi.org/10.1016/0022-247x(92)90261-b},
  year = {1992},
  month = jan,
  publisher = {Elsevier {BV}},
  volume = {163},
  number = {2},
  pages = {459--483},
  author = {David G Wagner},
  title = {Total positivity of {H}adamard products},
  journal = {Journal of Mathematical Analysis and Applications}
}
  14. [WZ24]Bo Wang and Candice X. T. Zhang. Interlacing property of a family of generating polynomials over Dyck paths. The Electronic Journal of Combinatorics, 31(1), March 2024.
    .bib
    @article{WangZhang2024,
  title = {Interlacing Property of a Family of Generating Polynomials over {D}yck Paths},
  volume = {31},
  ISSN = {1077-8926},
  url = {http://dx.doi.org/10.37236/12375},
  DOI = {10.37236/12375},
  number = {1},
  journal = {The Electronic Journal of Combinatorics},
  publisher = {The Electronic Journal of Combinatorics},
  author = {Wang,  Bo and Zhang,  Candice X.T.},
  year = {2024},
  month = mar,
  eprint = {2309.05903}
}
  15. [YZ24]Harold R. L. Yang and Philip B. Zhang. Stable multivariate Narayana polynomials and labeled plane trees. arXiv:2403.15058, 2024.
    .bib
    @article{YangZhang2024x,
  author = {Harold R. L. Yang and Philip B. Zhang},
  title = {Stable multivariate {N}arayana polynomials and labeled plane trees},
  year = {2024},
  eprint = {2403.15058},
  url = {https://arxiv.org/abs/2403.15058},
  journal = {arXiv e-prints}
}

I use cookies to detect website issues and track search terms.