#Set partitions
Example (Touchard polynomials (blocks in set partitions), with proof).
The Touchard polynomials may be defined via \[T_n(x) \coloneqq \sum_{P \in SP(n)} x^{\mathrm{blocks}(P)} = \sum_{k=1}^n S(n,k) x^k,\] where \(SP(n)\) is the set of set partitions of \([n],\) and we count the number of blocks. Note that the coefficients are Stirling numbers of the second type.
Wilf gives the recurrence [Wil94, pp. 20, 139] \[T_n(x) = x \cdot T_{n-1}(x) + x\cdot T'_{n-1}(x).\] We know \(T_{n-1} \interl x T_{n-1}.\) Moreover, \(T_{n-1} \interl x T'_{n-1},\) so by [Wag92], we have \(T_{n-1} \interl x T_{n-1} + x T'_{n-1}.\) But this is exactly \(T_{n-1} \interl T_n.\)
Another way to prove real-rootedness is by interpreting \(T_n(x)\) as a matching polynomial.
Example (Set partitions without singleton blocks).
Define \(D_n(t)=\sum_{\pi \in SP_2(n)} t^{\mathrm{blocks}(\pi)},\) where \(SP_2(n)\) is the set of set partitions of \([n]\) whose blocks all have size at least \(2.\) Then \[D_n(t) = t\left( D'_{n-1}(t) + (n-1) D_{n-2}(t) \right)\] and \(D_{n-1}(t)\) and \(D_n(t)\) have interlacing roots, see [BM16, Thm. 1]. Note that the degree of \(D_n(t)\) is \(\lfloor n/2 \rfloor.\)
The proof is short by using Wagner’s lemma and induction. The base case is immediate; assume \(D_{n-2} \interl D_{n-1}\) for some \(n \geq 2.\) We then know that \[D'_{n-1} \interl D_{n-1} \text{ and } (n-1)D_{n-2} \interl D_{n-1}.\] Wagner’s lemma now gives that \[D'_{n-1} + (n-1)D_{n-2} \interl D_{n-1} \implies D_{n-1} \interl t \left( D'_{n-1} + (n-1)D_{n-2} \right),\] and this is precisely \(D_{n-1} \interl D_n,\) which completes the induction step.
This result also follows from the general machinery in [Hit24, Subsec. 3.4]. A recursion for set partitions into blocks of size at least \(s\) is also mentioned there (originally due to L. Comtet) but it does not immediately imply real-rootedness.
Example (Type \(B\) set partitions).
D. Wang considers a type \(B\) version, and more generally a colored version, of counting blocks in set partitions [Wan14]. The polynomials considered satisfy the (general) recursion \[T_n(x) = (x+c) \cdot T_{n-1}(x) + mx\cdot T'_{n-1}(x),\] where \(m\) and \(c\) are positive integers.
P. Alexandersson, F. Beyene, and R. Mantaci study type \(B\) set partitions without a zero block [ABM26]. If \(b_{n,k}\) counts the merging-free ones with \(k\) blocks and \(M_n(t)=\sum_k b_{n,k}t^k,\) then \[M_n(t)=2tM'_{n-1}(t)+2(n-2)tM_{n-2}(t),\qquad n\geq2,\] with \(M_0(t)=1\) and \(M_1(t)=t.\) The polynomials \(M_n(t)\) are real-rooted and consecutive members interlace [ABM26, Prop. 27 and Cor. 28]; the paper also proves real-rootedness for the block polynomials of type \(B\) partitions that are both merging-free and separated [ABM26, Thm. 33]. Its flattened signed-permutation descent polynomial is gamma-positive and real-rooted [ABM26, Thm. 59 and Cor. 60].
Example (Ordered partitions).
Simion considers any multiset \(M\) and the number \(O(M,k)\) of compositions into exactly \(k\) parts [Sim84]. The polynomial \(\sum_k O(M,k)x^k\) is real-rooted.
In particular, this implies the real-rootedness of the Touchard polynomials.
#Stirling and quasi-Stirling permutations
Example (Stirling permutations).
The descent number of a Stirling permutation \(\pi \in Q_n\) is the cardinality of \[\{ i : \pi_i \gt \pi_{i+1} \} \cup \{2n\}.\] The Stirling permutation descent polynomials satisfy the recurrence \[P_n(t) = (2n+1)t \cdot P_{n-1}(t) + t(1-t) P'_{n-1}(t),\] see [Car65, Eq. 13] and [GS78, Thm. 2.1]. The coefficients can be found in A008517; the first few values are presented below.
\( 1 \) \( 1 \) \( 2 \) \( 1 \) \( 8 \) \( 6 \) \( 1 \) \( 22 \) \( 58 \) \( 24 \) \( 1 \) \( 52 \) \( 328 \) \( 444 \) \( 120 \) \( 1 \) \( 114 \) \( 1452 \) \( 4400 \) \( 3708 \) \( 720 \)These numbers appear in the Hilbert series of the Whitehouse complex; see [Rea05]. These polynomials are the \(h^*\)-polynomials of the order polytope defined by the inequalities \[y_1 \leq y_2 \leq \dotsb \leq y_n \qquad 0 \leq y_j \leq x_j \leq 1 \text{ for } j=1,\dotsc,n.\] S.-M. Ma, J. Ma, J. Yeh, and Y.-N. Yeh prove \(e\)-positivity for multivariate \(k\)th-order Eulerian polynomials attached to \(k\)-Stirling permutations [MMYY21]. They also give tree interpretations for the coefficients in related gamma-type expansions. For \(n=20,\) the linear term of the Ehrhart polynomial (of degree \(40\)) has negative coefficient \(-22354369153/6983776800.\)
M. Bóna proved that these have only real zeros [Bo09]. The Ma–Wang theorem also gives real-rootedness and interlacing.
J. Haglund and M. Visontai [HV12, Thm. 3.3] show that a multivariate generalization is stable.
Theorem (Dey’s interlacing criterion, [Dey23]).
Let \((F_n(x))_{n\geq 0}\) be a sequence of polynomials satisfying \[F_n(x)=\bigl(\alpha_1(n)x+\alpha_2\bigr)F_{n-1}(x) +\alpha_3x(1-x)F'_{n-1}(x),\] where \(\alpha_2,\alpha_3\in\setN\cup\{0\}.\) Suppose that each \(F_n(x)\) is real-rooted with distinct nonpositive zeros, and that some integer \(k\) satisfies, for all \(n\geq k,\) \[2\alpha_1(n)-n\alpha_3\gt{}0, \qquad n\alpha_1(n)\alpha_3+3n\alpha_2\alpha_3 -4\alpha_1(n)\alpha_2\gt{}0.\] Then \(F_{n-1}(x)\interl F_n(x)\) for all \(n\geq k.\)
Dey applies this criterion to the type \(A\) and type \(B\) Eulerian polynomials, to the Stirling permutation polynomials above, and to restricted Eulerian polynomials. Thus it is a useful way to upgrade an already known real-rootedness proof to a consecutive interlacing statement when the recurrence has the form above.
#Jacobi–Stirling descent polynomials
For \(k\geq1,\) let \[M_k=\{\overline{1},1,1,\overline{2},2,2,\dotsc,\overline{k},k,k\}, \qquad \overline{1}\lt{}1\lt{}\overline{2}\lt{}2\lt{}\dotsb\lt{}\overline{k}\lt{}k.\] For \(S\subseteq[k],\) delete the barred letters \(\overline{j}\) with \(j\in S.\) A Jacobi–Stirling permutation of the resulting multiset is a word in which every entry between the two unbarred copies of \(j\) is larger than \(j.\) Let \(\operatorname{JSP}_{k,S}\) be the set of these words, and define \[A_{k,S}(t)\coloneqq\sum_{w\in\operatorname{JSP}_{k,S}}t^{\des(w)}, \qquad A_{k,i}(t)\coloneqq \sum_{\substack{S\subseteq[k]\\|S|=i}}A_{k,S}(t).\] Here \(\des\) counts internal descents. In particular, \(A_{k,k}(t)\) is the second-order Eulerian polynomial with the final descent omitted, and \([t^j]A_{k,k}(t)\) is entry \((k,j+1)\) of A008517.
I. Gessel, Z. Lin, and J. Zeng observed that every \(A_{k,S}(t)\) is real-rooted and conjectured the same for every \(A_{k,i}(t)\) [GLZ12, Sec. 5 and Conj. 15]. Their normalization has an additional factor of \(t.\)
Theorem (S.-M. Ma and M.-X. Wang, [MW26, Thm. 2 and Cor. 2]).
Let \(k\geq1\) and \[i\in\{1,2,3,k-2,k-1\}\cap[k].\] Every nonzero nonnegative linear combination of the polynomials \(A_{k,S}(t)\) with \(|S|=i\) has only simple negative zeros. In particular, \(A_{k,i}(t)\) has only simple negative zeros.
The cases \(i=0\) and \(i=k\) were already known; the conjecture remains open for the remaining values of \(i.\)
Theorem ([MW26, Thms. 3 and 5]).
Write \(A_{k,i}(t)=\sum_{j=0}^{d}a_jt^j,\) where \(k\geq2\) and \(d=2k-i-1.\) Then \[a_j\lt{}a_{d-j}\quad(0\leq j\lt{}d/2), \qquad a_0\lt{}a_1\lt{}\dotsb\lt{}a_{\lfloor d/2\rfloor}.\] The same inequalities hold for every \(A_{k,S}(t),\) with \(d=2k-|S|-1.\)
#Quasi-Stirling descent polynomials
Example (Quasi-Stirling permutations).
A quasi-Stirling permutation of size \(n\) is a permutation of the multiset \(\{1,1,2,2,\dotsc,n,n\}\) avoiding the patterns \(1212\) and \(2121.\) Let \(\widetilde{Q}_n\) be the set of quasi-Stirling permutations of size \(n,\) and set \[\widetilde{Q}_n(t) \coloneqq \sum_{\pi \in \widetilde{Q}_n} t^{\des(\pi)},\] where the final position is counted as a descent, as above.
S. Elizalde [Eli21, Thm. 3.2] proved that \(\widetilde{Q}_n(t)\) has real, distinct, and nonpositive roots. More generally, for \(1 \leq r \leq n,\) let \[A_{n,r}(t) \coloneqq \sum_{\pi \in \symS_n} t^{\exc_r(\pi)}, \qquad J_{n,r}(t) \coloneqq \sum_{\pi \in \operatorname{Inj}([n-r],[n])} t^{\exc(\pi)},\] where \(\exc_r(\pi) \coloneqq |\{i:\pi_i \geq i+r\}|.\) Then \(A_{n,r}(t)\) and \(J_{n,r}(t)\) also have real, distinct, and nonpositive roots. The quasi-Stirling case follows from the relation \[\widetilde{Q}_n(t)=t J_{2n,n+1}(t).\] Elizalde also proves asymptotic normality for the descent distribution and extends the analysis to a one-parameter family generalizing \(k\)-Stirling permutations.
Bibliography
- [ABM26]Per Alexandersson, Fufa Beyene and Roberto Mantaci. Some Families of Type ${B}$ Set Partitions Counted by the Dowling Numbers. arXiv:2601.17174, 2026.
.bib
@article{AlexanderssonBeyeneMantaci2026x, author = {Per Alexandersson and Fufa Beyene and Roberto Mantaci}, title = {Some {F}amilies of {T}ype ${B}$ {S}et {P}artitions {C}ounted by the {D}owling {N}umbers}, year = {2026}, journal = {arXiv e-prints}, eprint = {2601.17174}, url = {https://arxiv.org/abs/2601.17174} } - [Bo09]Miklós Bóna. Real zeros and normal distribution for statistics on Stirling permutations defined by Gessel and Stanley. SIAM Journal on Discrete Mathematics, 23(1):401–406, January 2009.
.bib
@article{Bona2009, doi = {10.1137/070702254}, url = {https://doi.org/10.1137/070702254}, year = {2009}, month = jan, publisher = {Society for Industrial \& Applied Mathematics ({SIAM})}, volume = {23}, number = {1}, pages = {401--406}, author = {Mikl{\'{o}}s B{\'{o}}na}, title = {Real Zeros and Normal Distribution for Statistics on {S}tirling Permutations Defined by {G}essel and {S}tanley}, journal = {{SIAM} Journal on Discrete Mathematics} } - [BM16]Miklós Bóna and István Mező. Real zeros and partitions without singleton blocks. European Journal of Combinatorics, 51:500–510, January 2016.
.bib
@article{BonaHezo2016, doi = {10.1016/j.ejc.2015.07.021}, url = {https://doi.org/10.1016/j.ejc.2015.07.021}, year = {2016}, month = jan, publisher = {Elsevier {BV}}, volume = {51}, pages = {500--510}, author = {Mikl{\'{o}}s B{\'{o}}na and Istv{\'{a}}n Mez{\H{o}}}, title = {Real zeros and partitions without singleton blocks}, journal = {European Journal of Combinatorics} } - [Car65]L. Carlitz. The coefficients in an asymptotic expansion. Proceedings of the American Mathematical Society, 16(2):248–252, 1965.
.bib
@article{Carlitz1965, doi = {10.1090/s0002-9939-1965-0172814-6}, url = {https://doi.org/10.1090/s0002-9939-1965-0172814-6}, year = {1965}, publisher = {American Mathematical Society ({AMS})}, volume = {16}, number = {2}, pages = {248--252}, author = {L. Carlitz}, title = {The coefficients in an asymptotic expansion}, journal = {Proceedings of the American Mathematical Society} } - [Dey23]Hiranya Kishore Dey. Interlacing of zeroes of certain real-rooted polynomials. Archiv der Mathematik, 120(5):457–466, 2023.
.bib
@article{Dey2023InterlacingZeroes, author = {Dey, Hiranya Kishore}, title = {Interlacing of zeroes of certain real-rooted polynomials}, journal = {Archiv der Mathematik}, volume = {120}, number = {5}, pages = {457--466}, year = {2023}, doi = {10.1007/s00013-023-01837-2}, url2 = {https://doi.org/10.1007/s00013-023-01837-2} } - [Eli21]Sergi Elizalde. Descents on quasi-Stirling permutations. Journal of Combinatorial Theory, Series A, 180:105429, 2021.
.bib
@article{Elizalde2021, doi = {10.1016/j.jcta.2021.105429}, url2 = {https://doi.org/10.1016/j.jcta.2021.105429}, year = {2021}, publisher = {Elsevier {BV}}, volume = {180}, pages = {105429}, author = {Sergi Elizalde}, title = {Descents on quasi-{S}tirling permutations}, journal = {Journal of Combinatorial Theory, Series A}, eprint = {2002.00985} } - [GLZ12]Ira M. Gessel, Zhicong Lin and Jiang Zeng. Jacobi–Stirling polynomials and $P$-partitions. European Journal of Combinatorics, 33(8):1987–2000, 2012.
.bib
@article{GesselLinZeng2012, author = {Gessel, Ira M. and Lin, Zhicong and Zeng, Jiang}, title = {Jacobi--{S}tirling polynomials and {$P$}-partitions}, year = {2012}, journal = {European Journal of Combinatorics}, volume = {33}, number = {8}, pages = {1987--2000}, doi = {10.1016/j.ejc.2012.06.008}, eprint = {1201.0622v2}, url = {https://doi.org/10.1016/j.ejc.2012.06.008} } - [GS78]Ira Gessel and Richard P Stanley. Stirling polynomials. Journal of Combinatorial Theory, Series A, 24(1):24–33, January 1978.
.bib
@article{GesselStanley1978, doi = {10.1016/0097-3165(78)90042-0}, url2 = {https://doi.org/10.1016/0097-3165(78)90042-0}, year = {1978}, month = jan, publisher = {Elsevier {BV}}, volume = {24}, number = {1}, pages = {24--33}, author = {Ira Gessel and Richard P Stanley}, title = {Stirling polynomials}, journal = {Journal of Combinatorial Theory, Series A} } - [HV12]Jim Haglund and Mirkó Visontai. Stable multivariate Eulerian polynomials and generalized Stirling permutations. European Journal of Combinatorics, 33(4):477–487, May 2012.
.bib
@article{HaglundVisontai2012, doi = {10.1016/j.ejc.2011.10.007}, url2 = {https://doi.org/10.1016/j.ejc.2011.10.007}, year = {2012}, month = may, publisher = {Elsevier {BV}}, volume = {33}, number = {4}, pages = {477--487}, author = {Jim Haglund and Mirk{\'{o}} Visontai}, title = {Stable multivariate {E}ulerian polynomials and generalized {S}tirling permutations}, journal = {European Journal of Combinatorics} } - [Hit24]Paweł Hitczenko. A class of polynomial recurrences resulting in $(n/\log n, n/\log^2n)$-asymptotic normality. arXiv:2403.03422, 2024.
.bib
@article{Hitczenko2024x, Author = {Pawe{\l} Hitczenko}, Title = {A class of polynomial recurrences resulting in $(n/\log n, n/\log^2n)$-asymptotic normality}, Year = {2024}, journal = {arXiv e-prints}, Eprint = {2403.03422} } - [MMYY21]Shi-Mei Ma, Jun Ma, Jean Yeh and Yeong-Nan Yeh. Eulerian polynomials, Stirling permutations and increasing trees. arXiv:2106.16189, 2021.
.bib
@article{MaMaYehYeh2021x, author = {Shi-Mei Ma and Jun Ma and Jean Yeh and Yeong-Nan Yeh}, title = {Eulerian polynomials, {S}tirling permutations and increasing trees}, year = {2021}, eprint = {2106.16189}, url = {https://arxiv.org/abs/2106.16189}, journal = {arXiv e-prints} } - [MW26]Shi-Mei Ma and Ming-Xin Wang. Binomial expansions of Jacobi-Stirling numbers and real-rootedness of Jacobi-Stirling descent polynomials. arXiv:2610.03111v1, 2026.
.bib
@article{MaWang2026x, author = {Shi-Mei Ma and Ming-Xin Wang}, title = {Binomial expansions of {J}acobi-{S}tirling numbers and real-rootedness of {J}acobi-{S}tirling descent polynomials}, year = {2026}, eprint = {2610.03111v1}, url = {https://arxiv.org/abs/2610.03111v1}, journal = {arXiv e-prints} } - [Rea05]Margaret A. Readdy. The pre-WDVV ring of physics and its topology. The Ramanujan Journal, 10(2):269–281, October 2005.
.bib
@article{Readdy2005, title={The Pre-{WDVV} Ring of Physics and its Topology}, volume={10}, ISSN={1572-9303}, doi={10.1007/s11139-005-4850-1}, number={2}, journal={The Ramanujan Journal}, publisher={Springer Science and Business Media LLC}, author={Readdy, Margaret A.}, year={2005}, month=oct, pages={269–281} } - [Sim84]Rodica Simion. A multiindexed sturm sequence of polynomials and unimodality of certain combinatorial sequences. Journal of Combinatorial Theory, Series A, 36(1):15–22, January 1984.
.bib
@article{Simion1984, doi = {10.1016/0097-3165(84)90075-x}, url = {https://doi.org/10.1016/0097-3165(84)90075-x}, year = {1984}, month = jan, publisher = {Elsevier {BV}}, volume = {36}, number = {1}, pages = {15--22}, author = {Rodica Simion}, title = {A multiindexed sturm sequence of polynomials and unimodality of certain combinatorial sequences}, journal = {Journal of Combinatorial Theory, Series A} } - [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} } - [Wan14]David Wang. On colored set partitions of type $B_n$. Open Mathematics, 12(9), January 2014.
.bib
@article{Wang2014, title = {On colored set partitions of type $B_n$}, volume = {12}, ISSN = {2391-5455}, url = {http://dx.doi.org/10.2478/s11533-014-0419-9}, DOI = {10.2478/s11533-014-0419-9}, number = {9}, journal = {Open Mathematics}, publisher = {Walter de Gruyter GmbH}, author = {Wang, David}, year = {2014}, month = jan } - [Wil94]Herbert S. Wilf. Generatingfunctionology. Elsevier, 1994.
.bib
@book{Wilf1994, doi = {10.1016/c2009-0-02369-1}, url2 = {https://doi.org/10.1016%2Fc2009-0-02369-1}, year = {1994}, author = {Herbert S. Wilf}, publisher = {Elsevier}, title = {generatingfunctionology} }