Rook polynomials of generalized snake posets

The order polytope of a generalized snake poset has a real-rooted $h^*$-polynomial, and deleting the last letter of the defining word gives an interlacing polynomial.

Results

A generalized snake poset $P(w)$ is a width-two poset built from a word $w$ in the letters $L$ and $R$. Under the Alexandersson–Jal correspondence between naturally labeled width-two posets and skew shapes, the incomparable cross-chain pairs of $P(w)$ form a board, and the $P(w)$-Eulerian polynomial is the non-nesting rook polynomial $$ M_w(x)=\sum_P x^{|P|} $$ of this board with its columns reversed. Here $P$ runs over the sets of cells with no two in a row and with columns strictly decreasing as rows increase [AJ24]. By Braun and Jal, $M_w$ is the $h^*$-polynomial of the order polytope of $P(w)$.

Theorem (Braun–Jal). If $w$ is nonempty, then $M_w$ is nonzero and real-rooted, and $M_{w'}\ll M_w$, where $w'$ is $w$ with its last letter deleted [BJ26].

Proof

Let $N_n(x)=\sum_k\frac1n\binom nk\binom n{k-1}x^k$ be the Narayana polynomials and $P_n=x^{-1}N_{n+1}$. Then $P_n$ is the rook polynomial of the full truncated staircase board of size $n$, and $M_w=P_{|w|+1}$ for a constant word $w$. In general, let $k$ be the last position (counting from $0$) where $w$ differs from its final letter, and $s=|w|-k-1$. Then $$ M_w=M_{w[:k+1]}\,P_s+x\,M_{w[:k]}\,G_s, $$ where $w[:j]$ is the prefix of length $j$ and $x\,G_{n-1}=P_n-(1+x)P_{n-1}$; each $G_n$ is a sum of rook polynomials of truncated staircase boards. The theorem follows by induction along this recurrence from three facts: each $P_n$ has nonnegative coefficients and real nonpositive roots, with $P_n\ll P_{n+1}$; $G_n\ll P_n$, and $G_n-G_{n-1}$ has nonnegative coefficients; and $(\lambda x+\nu)P_{m-1}+P_m\ll(\lambda x+\nu)P_m+P_{m+1}$ for $m\ge2$, $\lambda\ge0$ and $\nu\ge-1$.

References

See also rook matroid polynomials on symmetricfunctions.com.

  1. [BJ26] Benjamin Braun & Aryaman Jal. Order polytopes of generalized snake posets are $h^*$-real-rooted. arXiv e-prints, 2026.
    BibTeX
    @article{BraunJal2026x,
      author = {Benjamin Braun and Aryaman Jal},
      title = {Order polytopes of generalized snake posets are {$h^*$}-real-rooted},
      year = {2026},
      eprint = {2607.00922},
      url = {https://arxiv.org/abs/2607.00922},
      journal = {arXiv e-prints}
    }
  2. [AJ24] Per Alexandersson & Aryaman Jal. Rook matroids and log-concavity of ${P}$-Eulerian polynomials. arXiv e-prints, 2024.
    BibTeX
    @article{AlexanderssonJal2024x,
    Author = {Per Alexandersson and Aryaman Jal},
    Title = {Rook matroids and log-concavity of ${P}$-{E}ulerian polynomials},
    Year = {2024},
    Eprint = {2410.00127},
      url = {https://arxiv.org/abs/2410.00127},
    journal = {arXiv e-prints}
    }

Definitions

  • Letters L and R of a snake word

    RealRooted.GeneralizedSnakePosets.SnakeLettersource
    inductive SnakeLetter where
      | L
      | R
      deriving DecidableEq, Repr
  • Constant snake words

    RealRooted.GeneralizedSnakePosets.SnakeWord.IsConstantsource
    def IsConstant (w : SnakeWord) : Prop :=
      ∀ a ∈ w, ∀ b ∈ w, a = b
  • Last position differing from the final letter

    RealRooted.GeneralizedSnakePosets.SnakeWord.IsLastChangeIndexsource
    def IsLastChangeIndex (w : SnakeWord) (k : ℕ) : Prop :=
      k ∈ changeIndices w ∧ ∀ j ∈ changeIndices w, j ≤ k
  • Board of a generalized snake poset

    RealRooted.GeneralizedSnakePosets.generalizedSnakeBoardsource
    def generalizedSnakeBoard (w : SnakeWord) : FiniteSkewBoard where
      cells := (snakeIncomparableBoard w).cells.image fun cell => (cell.1, w.length - cell.2)
  • Non-nesting rook polynomial of a board

    RealRooted.GeneralizedSnakePosets.FiniteSkewBoard.rookPolynomialsource
    def rookPolynomial (B : FiniteSkewBoard) : ℝ[X] := by
      classical
      exact (B.cells.powerset.filter (fun P => B.IsNonNestingPlacement P)).sum
        (fun P => X ^ P.card)
  • Modified Narayana polynomials Pₙ

    RealRooted.GeneralizedSnakePosets.modifiedNarayanaPolynomialsource
    def modifiedNarayanaPolynomial (n : ℕ) : ℝ[X] :=
      narayanaQuot (n + 1)
  • Auxiliary polynomials Gₙ

    RealRooted.GeneralizedSnakePosets.FiniteSkewBoard.rookSumsource
    def rookSum : ℕ → ℝ[X] :=
      fun n => ((List.range n).map fun i => truncatedStaircaseRookPolynomial n i).sum

Theorems

  • Modified Narayana polynomials are Pólya-frequency

    RealRooted.GeneralizedSnakePosets.modifiedNarayanaPolynomial_isPFPolynomialsource
    theorem modifiedNarayanaPolynomial_isPFPolynomial (n : ℕ) :
        IsPFPolynomial (modifiedNarayanaPolynomial n)
  • Consecutive modified Narayana polynomials interlace

    RealRooted.GeneralizedSnakePosets.modifiedNarayanaPolynomial_strictInterl_succsource
    theorem modifiedNarayanaPolynomial_strictInterl_succ (n : ℕ) :
        StrictInterl (modifiedNarayanaPolynomial n) (modifiedNarayanaPolynomial (n + 1))
  • Affine combinations of consecutive modified Narayana polynomials interlace

    RealRooted.GeneralizedSnakePosets.affineModifiedNarayanaInterlacing_modifiedsource
    theorem affineModifiedNarayanaInterlacing_modified :
        AffineModifiedNarayanaInterlacing modifiedNarayanaPolynomial
  • Full truncated staircases have rook polynomial Pₙ

    RealRooted.GeneralizedSnakePosets.FiniteSkewBoard.rookPolynomial_full_eq_modifiedNarayanasource
    theorem FiniteSkewBoard.rookPolynomial_full_eq_modifiedNarayana
        (n : ℕ) :
        FiniteSkewBoard.truncatedStaircaseRookPolynomial n n =
          modifiedNarayanaPolynomial n
  • The auxiliary polynomials Gₙ in terms of Pₙ

    RealRooted.GeneralizedSnakePosets.rookSum_recurrencesource
    theorem GeneralizedSnakePosets.rookSum_recurrence {n : ℕ} (hn : n ≠ 0) :
        X * FiniteSkewBoard.rookSum (n - 1) =
          modifiedNarayanaPolynomial n - (1 + X) * modifiedNarayanaPolynomial (n - 1)
  • The auxiliary polynomial Gₙ interlaces Pₙ

    RealRooted.GeneralizedSnakePosets.rookSum_strictInterl_modifiedNarayanasource
    theorem rookSum_strictInterl_modifiedNarayana {n : ℕ} (hn : n ≠ 0) :
        StrictInterl (FiniteSkewBoard.rookSum n) (modifiedNarayanaPolynomial n)
  • Constant words give modified Narayana polynomials

    RealRooted.GeneralizedSnakePosets.generalizedSnakeRookModel_snakePolynomial_of_isConstantsource
    theorem generalizedSnakeRookModel_snakePolynomial_of_isConstant {w : SnakeWord}
        (hw : w.IsConstant) :
        generalizedSnakeRookModel.snakePolynomial w = modifiedNarayanaPolynomial (w.length + 1)
  • Recurrence for the snake polynomials

    RealRooted.GeneralizedSnakePosets.rookPolynomial_recurrencesource
    theorem GeneralizedSnakePosets.rookPolynomial_recurrence {w : SnakeWord} {k : ℕ}
        (hk : w.IsLastChangeIndex k) :
        (generalizedSnakeBoard w).rookPolynomial =
          (generalizedSnakeBoard (w.take (k + 1))).rookPolynomial *
              modifiedNarayanaPolynomial (w.length - (k + 1)) +
            X * (generalizedSnakeBoard (w.take k)).rookPolynomial *
              FiniteSkewBoard.rookSum (w.length - (k + 1))
  • Snake polynomials are real-rooted and interlaceMain result

    RealRooted.GeneralizedSnakePosets.rookPolynomial_splits_and_interlacessource
    theorem GeneralizedSnakePosets.rookPolynomial_splits_and_interlaces {w : SnakeWord}
        (hw : w ≠ []) :
        ((generalizedSnakeBoard w).rookPolynomial ≠ 0 ∧
            (generalizedSnakeBoard w).rookPolynomial.Splits) ∧
          Interlaces (generalizedSnakeBoard w.dropLast).rookPolynomial
            (generalizedSnakeBoard w).rookPolynomial

Lean source RealRooted/Challenges/Combinatorial/GeneralizedSnakePosets.lean at revision d6670742. Formalized 2026-10-05.