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.

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.

  1. [GS78] Ira Gessel & Richard P Stanley. 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}
    }
  2. [MR03] Roberto Mantaci & Fanja Rakotondrajao. 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}
    }
  3. [Bon09] 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, 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}
    }
  4. [CS11] Chak-On Chow & Wai Chee Shiu. 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}
    }
  5. [Wan14] David Wang. 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
    }
  6. [BM16] Miklós Bóna & István Mező. 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}
    }

Definitions

  • Touchard polynomials

    RealRooted.touchardsource
    def touchard : Nat → ℝ[X]
      | 0 => 1
      | n + 1 => X * touchard n + X * (touchard n).derivative
  • Stirling-permutation descent polynomials

    RealRooted.stirlingPermutationssource
    def stirlingPermutations : Nat → ℝ[X]
      | 0 => 1
      | n + 1 =>
          stirlingPermutationsCoeffA n * stirlingPermutations n +
            stirlingPermutationsCoeffB * (stirlingPermutations n).derivative
  • Derangement polynomials by excedances

    RealRooted.sturmDerangementsExcsource
    def sturmDerangementsExc : Nat → ℝ[X]
      | 0 => 0
      | 1 => 0
      | 2 => X
      | n + 3 =>
          X * (((n + 2 : ℝ[X])) * sturmDerangementsExc (n + 1) +
            ((n + 2 : ℝ[X])) * sturmDerangementsExc (n + 2) +
            (1 - X) * (sturmDerangementsExc (n + 2)).derivative)
  • Simsun descent polynomials

    RealRooted.simsunsource
    def simsun : Nat → ℝ[X]
      | 0 => 1
      | n + 1 =>
          simsunCoeffA n * simsun n +
            simsunCoeffB * (simsun n).derivative
  • Set partitions without singleton blocks

    RealRooted.singletonFreeSetPartitionssource
    def singletonFreeSetPartitions : Nat → ℝ[X]
      | 0 => 1
      | 1 => 0
      | n + 2 =>
          X * (C (n + 1 : ℝ) * singletonFreeSetPartitions n +
            (singletonFreeSetPartitions (n + 1)).derivative)
  • Colored set-partition polynomials

    RealRooted.coloredSetPartitionssource
    def coloredSetPartitions (c m : Nat) : Nat → ℝ[X]
      | 0 => 1
      | n + 1 =>
          coloredSetPartitionsCoeffA c * coloredSetPartitions c m n +
            coloredSetPartitionsCoeffB m * (coloredSetPartitions c m n).derivative

Theorems

  • Consecutive Touchard polynomials interlaceMain result

    RealRooted.interlaces_touchard_succsourcestatement on symmetricfunctions.com
    theorem interlaces_touchard_succ (n : Nat) :
        Interlaces (touchard n) (touchard (n + 1))
  • Touchard coefficients are Stirling numbers of the second kind

    RealRooted.coeff_touchard_eq_stirlingSecondsource
    theorem coeff_touchard_eq_stirlingSecond : ∀ n k : ℕ,
        (touchard n).coeff k = (Nat.stirlingSecond n k : ℝ)
  • Consecutive Stirling-permutation descent polynomials interlace

    RealRooted.interlaces_stirlingPermutations_succsource
    theorem interlaces_stirlingPermutations_succ (n : Nat) :
        Interlaces (stirlingPermutations n) (stirlingPermutations (n + 1))
  • Consecutive derangement polynomials interlace

    RealRooted.interlaces_sturmDerangementsExc_succsourcestatement on symmetricfunctions.com
    theorem interlaces_sturmDerangementsExc_succ {n : Nat} (hn : 2 ≤ n) :
        Interlaces (sturmDerangementsExc n) (sturmDerangementsExc (n + 1))
  • Consecutive simsun polynomials interlace

    RealRooted.strictInterl_simsun_succsource
    theorem strictInterl_simsun_succ : ∀ n : Nat, StrictInterl (simsun n) (simsun (n + 1))
  • Consecutive singleton-free set-partition polynomials interlace

    RealRooted.strictInterl_singletonFreeSetPartitions_succsource
    theorem strictInterl_singletonFreeSetPartitions_succ :
        ∀ n : Nat, 2 ≤ n →
          StrictInterl (singletonFreeSetPartitions n) (singletonFreeSetPartitions (n + 1))
  • Consecutive colored set-partition polynomials interlace

    RealRooted.interlaces_coloredSetPartitions_succsource
    theorem interlaces_coloredSetPartitions_succ (c m n : Nat) :
        Interlaces (coloredSetPartitions c m n) (coloredSetPartitions c m (n + 1))
  • Touchard polynomials are colored set-partition polynomials with c = 0, m = 1

    RealRooted.touchard_eq_coloredSetPartitions_zero_onesource
    theorem touchard_eq_coloredSetPartitions_zero_one (n : ℕ) :
        touchard n = coloredSetPartitions 0 1 n
  • Motzkin polynomials are real-rooted

    RealRooted.isRealRooted_motzkinsource
    theorem isRealRooted_motzkin : ∀ n : Nat, ((motzkin n) ≠ 0 ∧ (motzkin n).Splits)
  • Consecutive Motzkin polynomials interlace

    RealRooted.strictInterl_motzkin_succsource
    theorem strictInterl_motzkin_succ (n : Nat) :
        StrictInterl (motzkin n) (motzkin (n + 1))
  • Independence polynomials of path powers ∑ C(m − rk, k) xᵏ are real-rooted

    RealRooted.splits_sum_choose_sub_mulsource
    theorem splits_sum_choose_sub_mul (r m : ℕ) :
        (∑ k ∈ range (m + 1), C (((m - r * k).choose k : ℕ) : ℝ) * X ^ k).Splits

Lean source RealRooted/Challenges/Roots/SturmSequenceFamilies.lean at revision d6670742. Formalized 2026-05-12.