Big-descent polynomials of 321-avoiding permutations

The big-descent polynomials of 321-avoiding permutations are real-rooted with negative roots, and the Motzkin reference polynomials interlace them.

Results

A big descent of a permutation $\pi$ is an index $i$ with $\pi(i)>\pi(i+1)+1$. Let $A_n(t)$ be the big-descent polynomial of the 321-avoiding permutations of length $n$. We define it by the first-return recurrence $A_0=1$, $A_n=\sum_{j=1}^n I_jA_{n-j}$, where $I_1=I_2=1$ and $I_j=t\,M_{j-2}$ for $j\ge3$. The reference Motzkin polynomials are $M_0=1$, $M_1=2$ and $$ M_{k+2}=2M_{k+1}+t\sum_{i=0}^{k}M_iM_{k-i},\qquad M_k=\sum_a\binom{k}{2a}\mathrm{Cat}_a\,2^{k-2a}t^a. $$

Theorem. For every $n\ge0$, $A_n$ is real-rooted and all its roots are negative. For $n\ge3$, $M_{n-2}\ll A_n$, both polynomials have simple roots, and they have no common root.

Use

By [ERZ26], the recurrence-defined $A_n$ is the big-descent enumerator of 321-avoiding permutations of length $n$. Together with that identification the theorem proves the case $\Pi=\{321\}$ of [ERZ26, Conj. 4.4]. See also big descents on symmetricfunctions.com.

Proof

For $n\ge25$ we expand $(c/2)^nA_n(1-c^{-2})$ in Gegenbauer polynomials and show $A_n(\rho)M_{n-2}'(\rho)<0$ at every zero $\rho$ of $M_{n-2}$, which gives interlacing. The cases $3\le n\le24$ are checked by exact computation.

References

  1. [ERZ26] Sergi Elizalde, Johnny Rivera, & Yan Zhuang. Counting Pattern-Avoiding Permutations by Big Descents. Annals of Combinatorics, 2026.
    BibTeX
    @article{ElizaldeRiveraZhuang2026,
      author = {Elizalde, Sergi and Rivera, Johnny and Zhuang, Yan},
      title = {Counting {P}attern-{A}voiding {P}ermutations by {B}ig {D}escents},
      year = {2026},
      journal = {Annals of Combinatorics},
      publisher = {Springer Science and Business Media LLC},
      doi = {10.1007/s00026-026-00805-1},
      url = {http://dx.doi.org/10.1007/s00026-026-00805-1},
      issn = {0219-3094}
    }

Definitions

  • Big-descent polynomial of 321-avoiders

    RealRooted.BigDescents321.bigDescentPolysource
    irreducible_def bigDescentPoly (n : ℕ) : R[X] := bigDescentPolyAux n
  • Reference Motzkin polynomial

    RealRooted.BigDescents321.motzkinRefsource
    irreducible_def motzkinRef (k : ℕ) : R[X] := motzkinRefAux k

Theorems

  • For n ≥ 3, M_{n-2} interlaces A_n; both have simple roots and no common rootMain resultRealRooted original

    RealRooted.BigDescents321.motzkinRef_interl_bigDescentPoly_and_noCommonRootssource
    theorem motzkinRef_interl_bigDescentPoly_and_noCommonRoots {n : ℕ} (hn : 3 ≤ n) :
        Interlaces (motzkinRef (n - 2) : ℝ[X]) (bigDescentPoly n) ∧
          (bigDescentPoly n : ℝ[X]).roots.Nodup ∧
          (motzkinRef (n - 2) : ℝ[X]).roots.Nodup ∧
          ∀ x, (motzkinRef (n - 2) : ℝ[X]).IsRoot x → ¬ (bigDescentPoly n : ℝ[X]).IsRoot x
  • A_n is real-rooted for every nRealRooted original

    RealRooted.BigDescents321.bigDescentPoly_splitssource
    theorem bigDescentPoly_splits (n : ℕ) : (bigDescentPoly n : ℝ[X]).Splits
  • Every root of A_n is negativeRealRooted original

    RealRooted.BigDescents321.neg_of_isRoot_bigDescentPolysource
    theorem neg_of_isRoot_bigDescentPoly {n : ℕ} {x : ℝ} (hx : (bigDescentPoly n : ℝ[X]).IsRoot x) :
        x < 0

Lean source RealRooted/Challenges/Combinatorial/BigDescents321.lean at revision d6670742. Formalized 2026-10-06.