Sturm sequences from derivative recurrences
Rows of the Touchard, Stirling-permutation, derangement, simsun, singleton-free and colored set-partition polynomials, defined by first-order derivative recurrences, are real-rooted and consecutive rows interlace.
Results
Each family is defined by its recurrence.
Theorem (recurrences). In each family below, consecutive polynomials interlace.
- Touchard: $T_0=1$, $T_{n+1}=xT_n+xT_n'$. Then $T_n\ll T_{n+1}$ for all $n$.
- Stirling permutations: $P_0=1$, $P_{n+1}=(2n+1)xP_n+x(1-x)P_n'$. Then $P_n\ll P_{n+1}$ for all $n$.
- Derangements: $P_0=P_1=0$, $P_2=x$ and $P_{n+3}=x\bigl((n+2)P_{n+1}+(n+2)P_{n+2}+(1-x)P_{n+2}'\bigr)$. Then $P_n\ll P_{n+1}$ for all $n\ge2$.
- Simsun permutations: $P_0=1$, $P_{n+1}=(1+nx)P_n+x(1-2x)P_n'$. Then $P_n\ll P_{n+1}$ for all $n$.
- Singleton-free set partitions: $D_0=1$, $D_1=0$ and $D_{n+2}=x\bigl((n+1)D_n+D_{n+1}'\bigr)$. Then $D_n\ll D_{n+1}$ for all $n\ge2$.
- Colored set partitions for natural numbers $c,m$: $T_0=1$, $T_{n+1}=(x+c)T_n+mxT_n'$. Then $T_n\ll T_{n+1}$ for all $n$.
In the Touchard, Stirling-permutation, derangement and colored families, moreover $\deg P_{n+1}=\deg P_n+1$, so these polynomials form Sturm sequences. In the derangement and singleton-free families $P_1$, respectively $D_1$, is zero, so interlacing starts at index $2$.
Theorem (Touchard). The Touchard polynomials are the case $c=0$, $m=1$ of the colored family, and $$T_n(x)=\sum_kS(n,k)\,x^k,$$ where $S(n,k)$ is the Stirling number of the second kind. The case $c=1$, $m=2$ gives the type $B$ set partitions of D. Wang.
Theorem (Motzkin polynomials). Let $M_k=\sum_a\binom k{2a}\mathrm{Cat}_a\,x^a$, so that $(k+2)M_k=(2k+1)M_{k-1}+(k-1)(4x-1)M_{k-2}$ for $k\ge3$, with $M_1=1$ and $M_2=1+x$. Then each $M_k$ with $k\ge1$ is real-rooted and $M_k\ll M_{k+1}$.
Theorem (path powers). For all natural numbers $r,m$ the polynomial $\sum_k\binom{m-rk}{k}x^k$ is real-rooted.
Use
Classically, $T_n$ counts set partitions of $\{1,\dotsc,n\}$ by blocks, the Stirling-permutation polynomials count Stirling permutations by descents, the derangement polynomials count derangements of $\{1,\dotsc,n\}$ by excedances, the simsun polynomials count simsun permutations of $\{1,\dotsc,n\}$ by descents, and $D_n$ counts set partitions of $\{1,\dotsc,n\}$ without singleton blocks by blocks. For $r\le m$ the path-power polynomial is the independence polynomial of the $r$th power of the path on $m-r$ vertices, a claw-free graph, so its real-rootedness also follows from the Chudnovsky–Seymour theorem.
Proof
The first-order recurrences have the form $P_{n+1}=uP_n+vP_n'$ with $v$ one of $x$, $x(1-x)$, $x(1-2x)$ and $mx$. The polynomial $P_n$ has nonnegative coefficients, so its zeros are nonpositive and $v$ is nonpositive there. The Liu–Wang criterion with the interlacer $P_n'\ll P_n$ then gives $P_n\ll P_{n+1}$. In the derangement and singleton-free recurrences the earlier row enters with a nonnegative coefficient, and Wagner's lemma on nonnegative combinations of common interlacers handles the extra term.
References
See [GS78]; [MR03]; [Bon09]; [CS11]; [Wan14]; [BM16]. See also the Touchard polynomials, Stirling permutations, the derangement polynomials, and the Motzkin-polynomial theorem on symmetricfunctions.com.
- [GS78] Stirling polynomials. Journal of Combinatorial Theory, Series A, 24(1), 24-33, 1978.
BibTeX
@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} } - [MR03] Exceedingly deranging!. Advances in Applied Mathematics, 30(1-2), 177-188, 2003.
BibTeX
@article{MantaciRakotondrajao2003, doi = {10.1016/s0196-8858(02)00531-6}, url2 = {https://doi.org/10.1016/s0196-8858(02)00531-6}, year = {2003}, month = feb, publisher = {Elsevier {BV}}, volume = {30}, number = {1-2}, pages = {177--188}, author = {Roberto Mantaci and Fanja Rakotondrajao}, title = {Exceedingly deranging!}, journal = {Advances in Applied Mathematics} } - [Bon09] Real Zeros and Normal Distribution for Statistics on Stirling Permutations Defined by Gessel and Stanley. SIAM Journal on Discrete Mathematics, 23(1), 401-406, 2009.
BibTeX
@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} } - [CS11] Counting simsun permutations by descents. Annals of Combinatorics, 15(4), 625-635, 2011.
BibTeX
@article{ChowShiu2011, doi = {10.1007/s00026-011-0113-6}, url2 = {https://doi.org/10.1007/s00026-011-0113-6}, year = {2011}, month = oct, publisher = {Springer Science and Business Media {LLC}}, volume = {15}, number = {4}, pages = {625--635}, author = {Chak-On Chow and Wai Chee Shiu}, title = {Counting Simsun Permutations by Descents}, journal = {Annals of Combinatorics} } - [Wan14] On colored set partitions of type $B_n$. Open Mathematics, 12(9), 2014.
BibTeX
@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 } - [BM16] Real zeros and partitions without singleton blocks. European Journal of Combinatorics, 51, 500-510, 2016.
BibTeX
@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} }