Bernstein Transfers and Greedy Records for Fence and Circular-Fence Order Polynomials

Pyuyi Chufeng Huang

Abstract

Let $P_{ε}$ be the fence poset associated with an orientation $ε \in {+, -}^{n - 1}$ of a path. We define a greedy right-to-left record statistic ${rec}_{ε}$ on $S_{n}$ and prove $\sum_{π \in S_{n}} t^{{rec}_{ε} (π)} = n! Ω (P_{ε}; t),$ by a Bernstein-basis transfer between a continuous threshold recurrence and endpoint-refined order-preserving maps. Under reflection, this statistic agrees pointwise with Kahane’s independently obtained greedy block statistic; the alternating specialization gives the zig-zag case posed by Ferroni, Morales, and Panova. A finite form of the transfer yields a direct recursive bijection for $m \leq n$ , extended algorithmically to arbitrary alphabets. Refining by record set, direction, and terminal value identifies fixed fibers with decorated endpoint paths and pointed linear extensions of posets whose cover graphs are caterpillars. We also define cyclic records for every nonconstant orientation $η$ of a cycle and prove $\sum_{π \in S_{n}} t^{{crec}_{η} (π)} = n! Ω (C_{η}; t) .$ When the Hasse diagram is a cycle, reflection identifies these records with Kahane’s circular blocks and establishes his circular-fence conjecture.

Introduction

Let $P$ be a finite poset. Its order polynomial $Ω (P; t)$ is characterized by $Ω (P; m) = # {f : P \to [m] order-preserving}$ for all positive integers $m$ ; see [20, Chapter 3]. Order polynomials are closely tied to order polytopes [17] and hence to Ehrhart theory. Ferroni, Morales, and Panova proved coefficient nonnegativity for skew-shape cell posets, hence for fences, and separately for circular fences [5, Corollary 5.1 and Theorem 7.7]. For the alternating, or zig-zag, fence $Z_{n}$ , they asked for a direct permutation-statistic interpretation of $n! Ω (Z_{n}; t)$ [5, Problem 5.3].

Independently, Kahane introduced a greedy block statistic and proved the corresponding identity for every fence; he also obtained a lower bound for the linear coefficient of order-polytope Ehrhart polynomials and a coefficient interpretation for Ehrhart polynomials of Schubert-matroid base polytopes [9, Sections 5 and 6]. After reflection, Proposition 2.4 identifies the statistic used here pointwise with Kahane’s. The additional path results are the Bernstein transfer, its finite and bijective forms, and the fixed-fiber refinements developed below. The cyclic construction is separate and gives a record formula for every nonconstant orientation of a cycle.

We work with an arbitrary orientation $ε = (ε_{1}, \dots, ε_{n - 1}) \in {+, -}^{n - 1}$ of a path. Let $P_{ε}$ be the transitive closure of $ε_{i} = + ⟹ x_{i} ≻ x_{i + 1}, ε_{i} = - ⟹ x_{i} ≺ x_{i + 1}$ on ${x_{1}, \dots, x_{n}}$ . Thus $Z_{n} = P_{ε^{zz}}$ , where $ε_{i}^{zz} = +$ for odd $i$ and $ε_{i}^{zz} = -$ for even $i$ .

For $π = π_{1} \dots π_{n} \in S_{n}$ , the statistic starts with threshold $π_{n}$ and scans from right to left. At a $+$ -edge it records a value larger than the current threshold, and at a $-$ -edge a value smaller than the threshold; every record resets the threshold. The total number of records is ${rec}_{ε} (π)$ . A precise definition and an equivalent greedy-chain formulation are given in Definition 2.2 and proposition 2.3.

Theorem 1.

For every $n \geq 1$ and every $ε \in {+, -}^{n - 1}$ , $\sum_{π \in S_{n}} t^{{rec}_{ε} (π)} = n! Ω (P_{ε}; t) .$

For alternating signs, Theorem 1.1 specializes to the zig-zag case of [5, Problem 5.3]. When all signs are $+$ or all are $-$ , it specializes to the classical right-to-left maximum or minimum statistic.

The relation with Kahane’s statistic is pointwise: if $δ_{j} = - ε_{n - j}, π_{j}^{rev} = π_{n + 1 - j},$ then Proposition 2.4 gives $\underset{ε}{rec} (π) = {bl}_{P_{δ}} (π^{rev}) .$ Thus greedy records and block roots are two descriptions of the same statistic under reflection.

Beyond the path generating identity, the results developed here are as follows.

For every nonconstant orientation $η$ of a cycle, a canonical root chosen from the labeled cycle defines a cyclic record statistic for which $\sum_{π \in S_{n}} t^{{crec}_{η} (π)} = n! Ω (C_{η}; t) .$ When the undirected Hasse diagram is a cycle, reflection identifies the cyclic records with Kahane’s circular block roots and proves his circular-fence conjecture [9, Conjecture 4.8].
The Bernstein recurrence lifts the path identity to endpoint-refined finite transfers and a direct recursive bijection for $m \leq n$ , with an algorithmic extension to arbitrary alphabets: $\begin{matrix} S_{n} \times {f : P_{ε} \to [m] order-preserving} \\ ⟷ {(π, λ) : π \in S_{n}, λ : {Rec}_{ε} (π) \to [m]} . \end{matrix}$
Refining by the complete record set, record directions, and terminal value identifies every fixed fiber with decorated endpoint paths and with pointed linear extensions of a record poset $Q_{ε, R}$ , whose cover graph is a caterpillar. Atkinson’s recursion for posets whose cover graph is a tree [1], specialized to record-gap coordinates, then gives the terminal-value spectrum. Standard $P$ -partition theory supplies a further quasisymmetric consequence.

Related rank-polynomial work concerns fences [15, 13] and their circular or loop analogues [12, 10]; rank-matrix models appear in [11]. These polynomials enumerate lower ideals by cardinality. By contrast, work on $h^{*}$ -polynomials of zig-zag order and chain polytopes [2, 3] and on zig-zag Eulerian polynomials [16] encodes descent data. Here the transfer tracks maps to arbitrary chains together with their endpoint and complete record-set data.

After defining the statistic and comparing it pointwise with Kahane’s blocks, we prove the Bernstein transfer and the cyclic identity. We then develop the finite bijection, the record-set refinements, and their record-poset consequences.

Greedy records for oriented paths

Definition 2.

Let $n \geq 1$ and $ε \in {+, -}^{n - 1}$ . The $ε$ -fence $P_{ε}$ is the poset on ${x_{1}, \dots, x_{n}}$ obtained as the transitive closure of the relations $ε_{i} = + ⟹ x_{i} ≻ x_{i + 1}, ε_{i} = - ⟹ x_{i} ≺ x_{i + 1}$ for $1 \leq i \leq n - 1$ . Equivalently, its order-preserving maps to a chain are exactly the maps satisfying $ε_{i} = + ⟹ f (x_{i}) \geq f (x_{i + 1}), ε_{i} = - ⟹ f (x_{i}) \leq f (x_{i + 1})$ for $1 \leq i \leq n - 1$ .

Two fence posets. A

+

-edge is directed downward from left to right, and a

-

-edge upward.

Definition 3.

Let $π = π_{1} \dots π_{n} \in S_{n}$ . The greedy $ε$ -record sequence of $π$ is the decreasing sequence of positions $i_{0} > i_{1} > \dots > i_{s}$ constructed as follows. Start with $i_{0} = n$ . Once $i_{j}$ has been chosen, form $A_{j} (π) = {i < i_{j} : \begin{matrix} π_{i} > π_{i_{j}}, & if ε_{i} = +, \\ π_{i} < π_{i_{j}}, & if ε_{i} = - \end{matrix}} .$ If $A_{j} (π) = ⌀$ , the construction stops. Otherwise, set $i_{j + 1} = \max A_{j} (π)$ . The positions $i_{0}, i_{1}, \dots, i_{s}$ are the $ε$ -records of $π$ . Set ${Rec}_{ε} (π) = {i_{0}, i_{1}, \dots, i_{s}} .$ The record number is $\underset{ε}{rec} (π) = | {Rec}_{ε} (π) | = s + 1.$ We also set ${rec}_{ε}^{+} (π) = # {1 \leq j \leq s : ε_{i_{j}} = +}, {rec}_{ε}^{-} (π) = # {1 \leq j \leq s : ε_{i_{j}} = -} .$ Thus $\underset{ε}{rec} (π) = 1 + {rec}_{ε}^{+} (π) + {rec}_{ε}^{-} (π),$ where the additional $1$ comes from the terminal record at position $n$ , which has no incoming sign.

The greedy-chain definition is equivalent to the following threshold scan.

Proposition 4.

The sequence in Definition 2.2 is obtained by the following right-to-left threshold scan. Declare $n$ to be a record and set $h = π_{n}$ . For $i = n - 1, n - 2, \dots, 1$ , declare $i$ to be a record exactly when $π_{i} > h$ if $ε_{i} = +$ , and exactly when $π_{i} < h$ if $ε_{i} = -$ . Whenever a record is declared, replace $h$ by $π_{i}$ .

Proof. After $i_{j}$ is chosen, the scan threshold is $π_{i_{j}}$ . If $A_{j} (π) \neq ⌀$ , its largest element is the first position met from the right that satisfies the required comparison, and both constructions reset to its value. If $A_{j} (π) = ⌀$ , both stop. Induction on $j$ proves the claim. ◻

Proposition 5 (Reflection to the block statistic).

For $ε \in {+, -}^{n - 1}$ , define $δ_{j} = - ε_{n - j} (1 \leq j \leq n - 1), π_{j}^{rev} = π_{n + 1 - j} (1 \leq j \leq n) .$ Then $P_{δ}$ is the reflection of $P_{ε}$ , and $\underset{ε}{rec} (π) = {bl}_{P_{δ}} (π^{rev}),$ where $bl$ is Kahane’s greedy block statistic [9, Definition 3.5 and Proposition 3.4]. More precisely, position $i$ is an $ε$ -record of $π$ if and only if reflected position $n + 1 - i$ is the root of a block of $(P_{δ}, π^{rev})$ .

Proof. Write $y_{j} = x_{n + 1 - j}$ . The edge between $y_{j}$ and $y_{j + 1}$ has sign $δ_{j} = - ε_{n - j}$ , so the relabeling $y_{j} \leftrightarrow x_{n + 1 - j}$ identifies $P_{δ}$ with $P_{ε}$ .

Kahane’s greedy construction reads the reflected fence from left to right and keeps the label of the leftmost vertex of the current block as its root threshold. At a reflected ascent, a new block begins exactly when the new label is larger than that threshold; at a reflected descent, it begins exactly when the new label is smaller. For $j \geq 2$ , put $i = n + 1 - j$ . The vertex $y_{j}$ is an ascent when $δ_{j - 1} = -$ , equivalently when $ε_{i} = +$ , and it is a descent when $δ_{j - 1} = +$ , equivalently when $ε_{i} = -$ . Hence a new block begins at $j$ exactly when $ε_{i} = + and π_{i} > h, or ε_{i} = - and π_{i} < h,$ where $h$ is the current root label. These are precisely the two record conditions in Proposition 2.3. Both scans start at the same reflected endpoint and reset the threshold at the same positions, which proves the pointwise correspondence and the equality of the two statistics. ◻

Example 6.

For the zig-zag sign sequence $ε^{zz}$ of length $n - 1$ , given by $ε_{i}^{zz} = +$ for odd $i$ and $ε_{i}^{zz} = -$ for even $i$ , and for $π = 41532$ , the greedy record sequence is $5 ⟶ 3 ⟶ 2 ⟶ 1.$ Starting from position $5$ , whose value is $2$ , position $4$ is even and therefore has sign $-$ , so it would have to satisfy $π_{4} < 2$ ; but $π_{4} = 3$ . The nearest admissible position is therefore $3$ , since $π_{3} = 5 > 2$ . From position $3$ , the next admissible position is $2$ , and from position $2$ , the next admissible position is $1$ . Hence ${rec}_{ε^{zz}} (41532) = 4$ , which is $zzrec (41532)$ in the notation used below.

The Bernstein transfer proof

The proof of Theorem 1.1 compares two explicit models for the same right-to-left process. The first model uses polynomial recurrences $H_{w}^{(m)} (x) \in ℚ [x]$ derived from a continuous record process. The second model uses endpoint-refined order-preserving maps. The bridge between the two is the Bernstein basis.

Let $w = w_{1} \dots w_{r} \in {+, -}^{r}$ be a word. The letter $w_{1}$ is the first comparison made with the current right endpoint, $w_{2}$ is the next comparison after moving one step to the left, and so on.

Definition 7.

Fix $m \geq 1$ . For $1 \leq k \leq m$ , define endpoint-refined counts $C_{w}^{(m)} (k)$ recursively by $C_{⌀}^{(m)} (k) = 1$ , and for a word $v$ , $C_{+ v}^{(m)} (k) = \sum_{ℓ = k}^{m} C_{v}^{(m)} (ℓ), C_{- v}^{(m)} (k) = \sum_{ℓ = 1}^{k} C_{v}^{(m)} (ℓ) .$ Equivalently, $C_{w}^{(m)} (k)$ counts sequences $(g_{0}, g_{1}, \dots, g_{r}) \in {[m]}^{r + 1}$ with $g_{0} = k$ such that $w_{j} = + ⟹ g_{j} \geq g_{j - 1}, w_{j} = - ⟹ g_{j} \leq g_{j - 1}$ for $1 \leq j \leq r$ .

Lemma 8 (Endpoint-refined order polynomials).

Let $ε \in {+, -}^{n - 1}$ , and put $w = ε_{n - 1} ε_{n - 2} \dots ε_{1}$ . For $1 \leq k \leq m$ , the number $C_{w}^{(m)} (k)$ counts order-preserving maps $f : P_{ε} \to [m]$ with $f (x_{n}) = k$ . Consequently, $Ω (P_{ε}; m) = \sum_{k = 1}^{m} C_{w}^{(m)} (k) .$

Proof. Given $f : P_{ε} \to [m]$ , set $g_{j} = f (x_{n - j})$ for $0 \leq j \leq n - 1$ . Then $g_{0} = f (x_{n})$ . For $1 \leq j \leq n - 1$ , the sign $w_{j}$ is $ε_{n - j}$ . If $w_{j} = +$ , then the order-preserving condition is $f (x_{n - j}) \geq f (x_{n - j + 1})$ , or $g_{j} \geq g_{j - 1}$ . If $w_{j} = -$ , it is $g_{j} \leq g_{j - 1}$ . These are exactly the inequalities in Definition 3.1, and the correspondence is reversible. ◻

Definition 9.

For $m \geq 1$ , $x \in [0,1]$ , and a word $w \in {+, -}^{r}$ , let $H_{w}^{(m)} (x)$ be the expected value of $m^{N}$ in the following process. We start with threshold $x$ , inspect $r$ independent uniform random variables in order, and use the comparison directions $w_{1}, \dots, w_{r}$ . Whenever the current direction is $+$ , a new record occurs if the inspected value is larger than the current threshold; whenever the current direction is $-$ , a new record occurs if the inspected value is smaller than the current threshold. On a record, the threshold is replaced by the inspected value; otherwise it is unchanged. The random variable $N$ is the number of new records among these $r$ inspected variables.

Conditioning on the first inspected value gives the recurrences $\begin{matrix} H_{⌀}^{(m)} (x) & = 1, & (1) \\ H_{+ v}^{(m)} (x) & = x H_{v}^{(m)} (x) + m \int_{x}^{1} H_{v}^{(m)} (u) d u, & (2) \\ H_{- v}^{(m)} (x) & = (1 - x) H_{v}^{(m)} (x) + m \int_{0}^{x} H_{v}^{(m)} (u) d u . & (3) \end{matrix}$ For example, in a $+$ -step, a first inspected value $u \leq x$ is not a record, keeps the threshold $x$ , and contributes $x H_{v}^{(m)} (x)$ . A value $u > x$ is a record, contributes the factor $m$ , changes the threshold to $u$ , and contributes $m \int_{x}^{1} H_{v}^{(m)} (u) d u$ . The $-$ -step is the same argument with the intervals $[0, x]$ and $[x, 1]$ interchanged. These recurrences recursively determine $H_{w}^{(m)}$ from the constant polynomial $1$ . Hence each $H_{w}^{(m)}$ is a polynomial in $x$ , and all integrations are ordinary integrations of polynomials.

For $1 \leq k \leq m$ , set $b_{m, k} (x) = (\binom{m - 1}{k - 1}) x^{k - 1} {(1 - x)}^{m - k} .$ These are the Bernstein basis polynomials of degree $m - 1$ [4], indexed so that $k \in [m]$ matches the endpoint value in Lemma 3.2. Probabilistically, if $U_{1}, \dots, U_{m - 1}$ are independent uniform random variables on $[0,1]$ , then $b_{m, k} (x) = \Pr (# {j : U_{j} < x} = k - 1) .$ Thus $b_{m, k} (x)$ is the probability that $x$ has rank $k$ after being inserted among $m - 1$ auxiliary uniform points.

Lemma 10 (Bernstein summation identities).

For $1 \leq ℓ \leq m$ , $\begin{matrix} x b_{m, ℓ} (x) + m \int_{x}^{1} b_{m, ℓ} (u) d u & = \sum_{k = 1}^{ℓ} b_{m, k} (x), & (4) \\ (1 - x) b_{m, ℓ} (x) + m \int_{0}^{x} b_{m, ℓ} (u) d u & = \sum_{k = ℓ}^{m} b_{m, k} (x) . & (5) \end{matrix}$ Moreover, $\int_{0}^{1} b_{m, k} (x) d x = \frac{1}{m}$ for every $k$ .

Proof. For the first identity, differentiate both sides: each derivative equals $- (m - ℓ) (\binom{m - 1}{ℓ - 1}) x^{ℓ - 1} {(1 - x)}^{m - ℓ - 1}$ when $ℓ < m$ , and both sides vanish at $x = 1$ ; the case $ℓ = m$ is the binomial theorem. The second identity follows by replacing $(x, ℓ)$ with $(1 - x, m + 1 - ℓ)$ . Finally, the beta integral gives $\int_{0}^{1} b_{m, k} (x) d x = (\binom{m - 1}{k - 1}) \frac{(k - 1)! (m - k)!}{m!} = \frac{1}{m},$ . ◻

Lemma 11 (Transfer lemma).

For every $m \geq 1$ and every word $w \in {+, -}^{r}$ , $H_{w}^{(m)} (x) = \sum_{k = 1}^{m} C_{w}^{(m)} (k) b_{m, k} (x) .$

Proof. We induct on the length of $w$ . For $w = ⌀$ , the statement is $1 = \sum_{k = 1}^{m} b_{m, k} (x)$ , the binomial theorem.

Assume the statement for $v$ . Using (2), the induction hypothesis, and (4), we get $\begin{matrix} H_{+ v}^{(m)} (x) & = x \sum_{ℓ = 1}^{m} C_{v}^{(m)} (ℓ) b_{m, ℓ} (x) + m \int_{x}^{1} \sum_{ℓ = 1}^{m} C_{v}^{(m)} (ℓ) b_{m, ℓ} (u) d u \\ = \sum_{ℓ = 1}^{m} C_{v}^{(m)} (ℓ) (x b_{m, ℓ} (x) + m \int_{x}^{1} b_{m, ℓ} (u) d u) \\ = \sum_{ℓ = 1}^{m} C_{v}^{(m)} (ℓ) \sum_{k = 1}^{ℓ} b_{m, k} (x) \\ = \sum_{k = 1}^{m} (\sum_{ℓ = k}^{m} C_{v}^{(m)} (ℓ)) b_{m, k} (x) \\ = \sum_{k = 1}^{m} C_{+ v}^{(m)} (k) b_{m, k} (x) . \end{matrix}$ The proof for $- v$ is identical, using (3) and (5): $\begin{matrix} H_{- v}^{(m)} (x) & = (1 - x) \sum_{ℓ = 1}^{m} C_{v}^{(m)} (ℓ) b_{m, ℓ} (x) + m \int_{0}^{x} \sum_{ℓ = 1}^{m} C_{v}^{(m)} (ℓ) b_{m, ℓ} (u) d u \\ = \sum_{ℓ = 1}^{m} C_{v}^{(m)} (ℓ) ((1 - x) b_{m, ℓ} (x) + m \int_{0}^{x} b_{m, ℓ} (u) d u) \\ = \sum_{ℓ = 1}^{m} C_{v}^{(m)} (ℓ) \sum_{k = ℓ}^{m} b_{m, k} (x) \\ = \sum_{k = 1}^{m} (\sum_{ℓ = 1}^{k} C_{v}^{(m)} (ℓ)) b_{m, k} (x) \\ = \sum_{k = 1}^{m} C_{- v}^{(m)} (k) b_{m, k} (x) . \end{matrix}$ This completes the induction. ◻

Proof of Theorem 1.1. It suffices to prove the identity after the specialization $t = m$ for every positive integer $m$ , since both sides are polynomials in $t$ .

Let $X_{1}, \dots, X_{n}$ be independent continuous uniform random variables. Their relative order is almost surely uniformly distributed over $S_{n}$ , and ${rec}_{ε}$ depends only on comparisons among entries. Therefore $\frac{1}{n!} \sum_{π \in S_{n}} m^{{rec}_{ε} (π)}$ is the expected value of $m^{{rec}_{ε}}$ in this continuous model.

Set $w = ε_{n - 1} ε_{n - 2} \dots ε_{1}$ . The rightmost position is always a record, contributing one factor $m$ . After conditioning on $X_{n} = x$ , the remaining variables are inspected with comparison word $w$ . Hence $\begin{matrix} \frac{1}{n!} \sum_{π \in S_{n}} m^{{rec}_{ε} (π)} = m \int_{0}^{1} H_{w}^{(m)} (x) d x . & (6) \end{matrix}$

By Lemma 3.5 and Lemma 3.4, $m \int_{0}^{1} H_{w}^{(m)} (x) d x = m \sum_{k = 1}^{m} C_{w}^{(m)} (k) \int_{0}^{1} b_{m, k} (x) d x = \sum_{k = 1}^{m} C_{w}^{(m)} (k) .$ By Lemma 3.2, the last sum is $Ω (P_{ε}; m)$ . Combining this with (6) proves $\frac{1}{n!} \sum_{π \in S_{n}} m^{{rec}_{ε} (π)} = Ω (P_{ε}; m)$ for all positive integers $m$ . The polynomial identity in $t$ follows. ◻

For the alternating sign word $ε_{i}^{zz} = +$ for odd $i$ and $ε_{i}^{zz} = -$ for even $i$ , write $zzrec (π) = \underset{ε^{zz}}{rec} (π) .$ Then $P_{ε^{zz}} = Z_{n}$ , and Theorem 1.1 specializes to $\sum_{π \in S_{n}} t^{zzrec (π)} = n! Ω (Z_{n}; t) .$ This is the zig-zag specialization posed in [5, Problem 5.3].

Remark 12 (Symmetries and checks).

Complementing values, $c {(π)}_{i} = n + 1 - π_{i}$ , interchanges the two record directions: $\begin{matrix} \underset{- ε}{rec} (c (π)) & = \underset{ε}{rec} (π), \\ {rec}_{- ε}^{+} (c (π)) & = {rec}_{ε}^{-} (π), \\ {rec}_{- ε}^{-} (c (π)) & = {rec}_{ε}^{+} (π) . \end{matrix}$ This follows directly by complementing the threshold at every step. If $ε_{i}^{\leftarrow} = ε_{n - i}$ , reversing the vertices identifies $P_{ε}$ with $P_{η}$ , where $η_{i} = - ε_{n - i}$ . Complementing the values of an order-preserving map then identifies $P_{η}$ with $P_{- η}$ , so $Ω (P_{ε}; t) = Ω (P_{ε^{\leftarrow}}; t) .$ Thus sign reversal and word reversal do not produce new order polynomials.

For the monotone word $(+, \dots, +)$ , the statistic is the classical number of right-to-left maxima and $\sum_{π \in S_{n}} t^{{rec}_{ε} (π)} = n! (\binom{t + n - 1}{n}) = t (t + 1) \dots (t + n - 1) .$ The all- $-$ case follows by complementation.

For the alternating sign word, the covering relations are $x_{1} ≻ x_{2} ≺ x_{3} ≻ x_{4} ≺ \dots .$ Under the opposite convention $x_{1} ≺ x_{2} ≻ x_{3} ≺ \dots$ , the signs in $ε^{zz}$ are reversed, so the two statistics are equidistributed by value complementation. Every position is a record exactly for a down-up alternating permutation; hence, as a consistency check, $[t^{n}] \sum_{π \in S_{n}} t^{zzrec (π)} = E_{n},$ the classical Euler zig-zag number [18].

Circular fences and cyclic records

Let $η = (η_{1}, \dots, η_{n}) \in {+, -}^{n}$ be nonconstant, and read subscripts modulo $n$ . The cyclic orientation poset $C_{η}$ is the transitive closure of $η_{i} = + ⟹ x_{i} ≻ x_{i + 1}, η_{i} = - ⟹ x_{i} ≺ x_{i + 1} .$ Nonconstancy makes this orientation acyclic and ensures that both signs occur. Thus $C_{η}$ is a poset, and its order-preserving maps to $[m]$ are the cyclic sequences satisfying the corresponding weak inequalities. Rank-matrix and trace models for related oriented and circular fences were developed by Kantarcı Oğuz [11]. If one sign occurs only once, its edge is redundant in the transitive closure and the Hasse diagram is a path. If both signs occur at least twice, the undirected Hasse diagram is a cycle and $C_{η}$ is a circular fence in the usual sense. The record identity below includes both cases; the comparison with Kahane’s circular blocks applies only in the latter.

Proposition 13 (Trace formula).

For a positive integer $m$ , let $M_{+} [a, b] = 𝟏_{a \geq b}, M_{-} [a, b] = 𝟏_{a \leq b} (a, b \in [m]) .$ Then $Ω (C_{η}; m) = tr (M_{η_{1}} \dots M_{η_{n}}) .$

Proof. The $(a_{1}, a_{n + 1})$ -entry of the product sums the indicators of the edge inequalities over $a_{2}, \dots, a_{n} \in [m]$ . Taking the trace imposes $a_{n + 1} = a_{1}$ , and hence counts the order-preserving maps. This is the standard transfer-matrix argument; compare [20, §4.7]. For an analogous trace construction for circular-fence rank polynomials, see [11, Proposition 5.3]. ◻

Ferroni, Morales, and Panova proved coefficient nonnegativity for every circular fence using the Gessel–Krattenthaler determinant for cylindric partitions [5, Theorem 7.7], based on the determinant of Gessel and Krattenthaler [8]. For closed alternating zig-zags, Lundström and Saud Maia Leite give a cyclic-swap interpretation of the $h^{*}$ -polynomial [14]. Here we seek instead a statistic for the coefficients of $n! Ω (C_{η}; t)$ . The trace formula admits such a record interpretation once the missing endpoint is replaced by a canonical root.

Definition 14 (Cyclic right-to-left records).

Let $I_{+} (η) = {i \in [n] : η_{i} = +}$ . For $π = π_{1} \dots π_{n} \in S_{n}$ , let $r = r_{η} (π)$ be the unique index in $I_{+} (η)$ such that $π_{r} = \max {π_{i} : i \in I_{+} (η)}$ . The position $r$ is declared to be a record, and the initial threshold is $h = π_{r}$ . We then inspect the remaining positions in cyclic right-to-left order $r - 1, r - 2, \dots, r + 1$ . When position $i$ is inspected, it is a record if $η_{i} = + and π_{i} > h, or η_{i} = - and π_{i} < h .$ Whenever a record occurs, the threshold is reset to $h = π_{i}$ . The total number of records is denoted by ${crec}_{η} (π)$ .

Thus the terminal position used for paths is replaced by the largest value sitting at the tail of a $+$ -edge. This choice is intrinsic to the labeled cycle and is almost surely unique in the continuous model used below. Rooting at a $+$ -edge maximum is a convention: value complementation together with sign reversal exchanges it with rooting at the smallest value on a $-$ -edge.

Theorem 15 (Circular records).

For every nonconstant $η \in {+, -}^{n}$ , we have $\sum_{π \in S_{n}} t^{{crec}_{η} (π)} = n! Ω (C_{η}; t) .$

Proof. It suffices to prove the identity after substituting $t = m$ for every positive integer $m$ , since both sides are polynomials in $t$ .

Let $X_{1}, \dots, X_{n}$ be independent uniform random variables on $[0,1]$ . Their relative order is almost surely uniform on $S_{n}$ , and ${crec}_{η}$ depends only on this relative order. Hence $\frac{1}{n!} \sum_{π \in S_{n}} m^{{crec}_{η} (π)} = 𝔼 [m^{{crec}_{η} (X)}] .$

Let $A_{+}$ and $A_{-}$ be the $m \times m$ matrices $A_{+} [a, b] = {\begin{matrix} 1, & a \leq b, \\ 0, & a > b, \end{matrix} A_{-} [a, b] = {\begin{matrix} 1, & a \geq b, \\ 0, & a < b, \end{matrix}$ with rows and columns indexed by $[m]$ . These are the one-step transfer matrices for the endpoint recurrences in Definition 3.1: a $+$ -step sends a continuation vector $v$ to $A_{+} v$ , and a $-$ -step sends it to $A_{-} v$ . Put $N_{+} (x) = x A_{+}, N_{-} (x) = (1 - x) I + x A_{-} .$ Let $e_{m}$ be the last standard basis vector and let $𝟏$ be the all-one column vector. These are the boundary states of the transfer. After conditioning on a root value $x$ and rescaling $[0, x]$ to $[0,1]$ , the initial threshold is $1$ . Since $b_{m, k} (1) = δ_{k, m}$ , the Bernstein expansion in Lemma 3.5 evaluates this state by $e_{m}^{T}$ . At the other end the empty continuation has coefficient vector $𝟏$ , because $C_{⌀}^{(m)} (k) = 1$ for all $k$ . For $r \in I_{+} (η)$ , define $T_{r} (x) = N_{η_{r - 1}} (x) N_{η_{r - 2}} (x) \dots N_{η_{r + 1}} (x),$ where the product contains the $n - 1$ indices met in cyclic decreasing order. We claim that $\begin{matrix} \frac{1}{n!} \sum_{π \in S_{n}} m^{{crec}_{η} (π)} = m \int_{0}^{1} \sum_{r \in I_{+} (η)} e_{m}^{T} T_{r} (x) 𝟏 d x . & (7) \end{matrix}$ Indeed, fix $r \in I_{+} (η)$ and condition on $X_{r} = x$ . The contribution in which $r$ is the chosen root requires every other $+$ -position to have value in $[0, x]$ . During the cyclic scan the threshold never exceeds $x$ . Thus a non-root $+$ -position contributes the probability factor $x$ and, after rescaling $[0, x]$ to $[0,1]$ , the ordinary $+$ -transfer $A_{+}$ . A $-$ -position has two possibilities: values in $(x, 1]$ cannot be records and contribute $(1 - x) I$ , while values in $[0, x]$ contribute, after the same rescaling, the ordinary $-$ -transfer $x A_{-}$ . The root itself contributes one factor $m$ . Multiplying the transfers in the scan order and integrating over $x$ gives (7).

To evaluate the integral, set $𝒩_{η} (x) = N_{η_{n}} (x) N_{η_{n - 1}} (x) \dots N_{η_{1}} (x) .$ We shall show that $\begin{matrix} \frac{d}{d x} tr 𝒩_{η} (x) = m \sum_{r \in I_{+} (η)} e_{m}^{T} T_{r} (x) 𝟏. & (8) \end{matrix}$ Let $R = m 𝟏 e_{m}^{T}$ and let $L$ be the lower bidiagonal matrix $L_{a, a} = a - m (1 \leq a \leq m), L_{a, a - 1} = - (a - 1) (2 \leq a \leq m),$ with all other entries equal to $0$ . A direct entrywise check gives $L A_{-} - A_{-} L = A_{-} - I, L A_{+} - A_{+} L = A_{+} - R .$ Indeed, multiplication by the two nonzero diagonals of $L$ gives $\begin{matrix} (L A_{-} - A_{-} L) [a, b] & = 𝟏_{a \geq b} - δ_{a, b}, \\ (L A_{+} - A_{+} L) [a, b] & = 𝟏_{a \leq b} - m 𝟏_{b = m}, \end{matrix}$ which are the entries of $A_{-} - I$ and $A_{+} - m 𝟏 e_{m}^{T}$ , respectively. Equivalently, for $x > 0$ , with $D (x) = L / x$ , $N_{-}^{'} (x) = [D (x), N_{-} (x)], N_{+}^{'} (x) = R + [D (x), N_{+} (x)] .$ Differentiating $tr 𝒩_{η} (x)$ , the Leibniz sum of the commutator terms telescopes by the derivation rule: $\sum_{i = 1}^{n} N_{η_{n}} \dots N_{η_{i + 1}} [D, N_{η_{i}}] N_{η_{i - 1}} \dots N_{η_{1}} = [D, 𝒩_{η}] .$ (Here every matrix is evaluated at $x$ .) Its trace is zero. The remaining terms insert $R$ at the $+$ -positions. By cyclicity of trace, these insertions give $\sum_{r \in I_{+} (η)} tr (R T_{r} (x)) = m \sum_{r \in I_{+} (η)} e_{m}^{T} T_{r} (x) 𝟏,$ which proves (8). Although $D (x)$ has a pole at $0$ , the displayed derivative identity is an identity of polynomials on $(0,1]$ , hence extends to the interval after integration.

Since $I_{+} (η) \neq ⌀$ , we have $N_{+} (0) = 0$ in at least one factor, so $tr 𝒩_{η} (0) = 0$ . Also $N_{+} (1) = A_{+}$ and $N_{-} (1) = A_{-}$ . Integrating (8) over $[0,1]$ gives $m \int_{0}^{1} \sum_{r \in I_{+} (η)} e_{m}^{T} T_{r} (x) 𝟏 d x = tr (A_{η_{n}} A_{η_{n - 1}} \dots A_{η_{1}}) .$ The matrices $A_{+}$ and $A_{-}$ are the transposes of the matrices $M_{+}$ and $M_{-}$ in Proposition 4.1. Therefore $tr (A_{η_{n}} A_{η_{n - 1}} \dots A_{η_{1}}) = tr (M_{η_{1}} M_{η_{2}} \dots M_{η_{n}}) = Ω (C_{η}; m) .$ Combining this with (7) proves the desired identity at $t = m$ , and polynomial interpolation completes the proof. ◻

We next compare the cyclic records with Kahane’s circular blocks. This comparison requires the undirected Hasse diagram to be a cycle.

Lemma 16 (Closing a greedy block path).

Let $C$ be a circular fence whose Hasse diagram is a cycle, and let $y_{s}$ be the ascent vertex with largest label among all ascent vertices. Delete the incoming cover $y_{s - 1} < y_{s}$ , and read the resulting path from $y_{s}$ to $y_{s - 1}$ . If $B_{1}, \dots, B_{k}$ is Kahane’s greedy block partition of this path, then the same consecutive blocks form the unique valid circular block partition of $C$ .

Proof. The first block has root $y_{s}$ . Every later ascent root has smaller label by the choice of $y_{s}$ , while a descent root is created by a downward threshold reset and therefore also has smaller label. If $k = 1$ , all other ascent labels lie below the label of $y_{s}$ , and every descent label lies above it. Thus the whole cycle satisfies Kahane’s block condition.

Suppose $k \geq 2$ . The ascent case in the proof of [9, Lemma 4.7] deletes the incoming cover at an ascent vertex and extends the resulting path partition back to the cycle. Inspection of that argument shows that it uses maximality of the chosen label only to ensure that the chosen root has larger label than the root of the block containing its predecessor. Here that predecessor lies in $B_{k}$ , and the required inequality follows from the first paragraph. Thus the path blocks are admissible circular blocks after the cover is restored.

For completeness, validity between blocks can also be checked directly. All relations not using the restored cover were already present in the path block poset and are valid. The restored cover gives the additional block relation $B_{k} < B_{1}$ , and the root of $B_{k}$ has smaller label than the root $y_{s}$ of $B_{1}$ . Any new transitive relation between blocks is represented by a directed path in the block quotient that uses this additional edge. Root labels increase along every edge of that path, so every new relation satisfies Kahane’s validity condition. The restored partition is therefore valid, and its uniqueness follows again from [9, Lemma 4.7]. ◻

Proposition 17 (Reflection and circular blocks).

Assume that both signs occur at least twice in $η$ , equivalently that the Hasse diagram of $C_{η}$ is a cycle. Read subscripts modulo $n$ , with $η_{0} = η_{n}$ , and define $δ_{j} = - η_{n - j}, π_{j}^{rev} = π_{n + 1 - j} (1 \leq j \leq n) .$ Let ${bl}_{C_{δ}}^{\circ}$ denote Kahane’s $\overset{}{bl}$ , the number of blocks in the unique valid circular block partition [9, §4.2 and Lemma 4.7]. Then ${crec}_{η} (π) = {bl}_{C_{δ}}^{\circ} (π^{rev}) .$ Under this correspondence, the canonical cyclic record becomes the root with largest label among the ascent vertices of the reflected cycle, and every subsequent cyclic record becomes the root of the next block.

Proof. Put $y_{j} = x_{n + 1 - j}$ . As in Proposition 2.4, the signs of the reflected cycle are $δ_{j} = - η_{n - j}$ . Moreover, $y_{n + 1 - i} = x_{i}$ is an ascent vertex of the reflected cycle exactly when $i \in I_{+} (η)$ . The chosen cyclic record therefore becomes the maximum-labeled ascent vertex, say $y_{s}$ .

Cut the edge entering $y_{s}$ and read the resulting path from $y_{s}$ in the forward cyclic direction. This is the reflection of the cyclic right-to-left scan. The local comparison in Kahane’s greedy block construction is the same as in the proof of Proposition 2.4: at an ascent a new block starts when the new label is larger than the current root label, and at a descent it starts when the new label is smaller. Hence the block roots of the cut path are exactly the reflected cyclic records.

By Lemma 4.4, restoring the cut edge produces Kahane’s unique valid circular partition without changing the block roots. The pointwise equality follows. ◻

Corollary 18 (Kahane’s circular-fence conjecture).

Let $C$ be a circular fence of size $n$ whose Hasse diagram is a cycle, in the sense of [9, Definition 4.6]. Then $n! Ω (C; t) = \sum_{σ \in S_{n}} t^{{bl}_{C}^{\circ} (σ)} .$ Consequently, [9, Conjecture 4.8] holds.

Proof. Choose a cyclic presentation $C = C_{δ}$ and reflect it to $C_{η}$ , where $η_{i} = - δ_{n - i}$ . Reflection is a bijection on labelings and preserves the order polynomial. The result follows by combining Proposition 4.5 with Theorem 4.3. ◻

Example 19. For the four-vertex crown $η = (+, -, +, -)$ , $Ω (C_{η}; m) = \sum_{a, c = 1}^{m} \min {(a, c)}^{2} = \frac{m (m + 1) (m^{2} + m + 1)}{6} .$ The cyclic record statistic therefore gives $\sum_{π \in S_{4}} t^{{crec}_{η} (π)} = 4 t + 8 t^{2} + 8 t^{3} + 4 t^{4} = 4! Ω (C_{η}; t) .$

Finite Bernstein transfers

We now discretize the Bernstein transfer. Finite counting recurrences for a rank-vector analogue of $H_{w}^{(m)}$ give a transfer between rank-vector sums and endpoint counts. Its diagonal case is realized bijectively in Section 6.

Definition 20 (Rank-vector record sums).

Let $w = w_{1} \dots w_{r} \in {+, -}^{r}$ , let $m \geq 1$ , and let $1 \leq k \leq r + 1$ . For a permutation $α = (a_{1}, \dots, a_{r})$ of the set $[r + 1] ∖ {k}$ , start with threshold $h_{0} = k$ . At step $j$ , declare a record if $w_{j} = + and a_{j} > h_{j - 1}, or w_{j} = - and a_{j} < h_{j - 1} .$ If a record occurs, set $h_{j} = a_{j}$ ; otherwise set $h_{j} = h_{j - 1}$ . Let $N_{w} (α; k)$ be the number of records declared in these $r$ steps, not including the initial threshold. Define $D_{w}^{(m)} (k) = \sum_{α} m^{N_{w} (α; k)},$ where the sum is over all permutations of $[r + 1] ∖ {k}$ . For indices outside $1, \dots, r + 1$ , we set $D_{w}^{(m)} (k) = 0$ .

Lemma 21 (Entry from permutations).

Let $ε \in {+, -}^{n - 1}$ , put $w = ε_{n - 1} ε_{n - 2} \dots ε_{1}$ , and let $1 \leq k \leq n$ . Then, for every positive integer $m$ , $\sum_{\begin{matrix} π \in S_{n} \\ π_{n} = k \end{matrix}} m^{{rec}_{ε} (π)} = m D_{w}^{(m)} (k) .$ Consequently, $\sum_{π \in S_{n}} m^{{rec}_{ε} (π)} = m \sum_{k = 1}^{n} D_{w}^{(m)} (k) .$

Proof. The position $n$ is always a greedy $ε$ -record, so it contributes one factor $m$ . If $π_{n} = k$ , then the right-to-left scan of the remaining positions reads a permutation of $[n] ∖ {k}$ , and the comparison word is $w = ε_{n - 1} \dots ε_{1}$ . The rule in Definition 5.1 is exactly the threshold scan of Proposition 2.3, with the terminal record removed. Summing over all permutations with fixed terminal value $k$ gives the first identity, and summing over $k$ gives the second. ◻

Proposition 22 (Rank-vector recurrences).

Let $v \in {+, -}^{r - 1}$ , so that $+ v$ and $- v$ have length $r$ . For $1 \leq k \leq r + 1$ , $\begin{matrix} D_{+ v}^{(m)} (k) & = (k - 1) D_{v}^{(m)} (k - 1) + m \sum_{j = k}^{r} D_{v}^{(m)} (j), & (9) \\ D_{- v}^{(m)} (k) & = (r + 1 - k) D_{v}^{(m)} (k) + m \sum_{j = 1}^{k - 1} D_{v}^{(m)} (j) . & (10) \end{matrix}$

Proof. For $D_{+ v}^{(m)} (k)$ , separate the first scanned value $a$ . If $a < k$ , then no record occurs. After deleting $a$ and standardizing the remaining ordered set, the threshold $k$ has rank $k - 1$ . There are $k - 1$ choices for $a$ , giving the first term in (9). If $a > k$ , then a record occurs, contributing the factor $m$ . After deleting the old threshold $k$ and standardizing the ordered set $[r + 1] ∖ {k}$ , the new threshold $a$ has rank $j = a - 1$ , where $j$ ranges from $k$ to $r$ . This gives the sum in (9).

For $D_{- v}^{(m)} (k)$ , the same first-step decomposition is reversed. If $a > k$ , no record occurs; deleting $a$ leaves the threshold with rank $k$ , and there are $r + 1 - k$ choices. If $a < k$ , a record occurs, contributes $m$ , and the new threshold has rank $j = a$ after standardization, with $1 \leq j < k$ . This gives (10). ◻

For $r \geq 0$ , write $B_{r, k} (x) = (\binom{r}{k - 1}) x^{k - 1} {(1 - x)}^{r + 1 - k}, 1 \leq k \leq r + 1,$ for the degree $r$ Bernstein basis.

Lemma 23 (Degree-raising identities).

Let $r \geq 1$ and $1 \leq j \leq r$ . Then $\begin{matrix} x B_{r - 1, j} (x) & = \frac{j}{r} B_{r, j + 1} (x), \\ \int_{x}^{1} B_{r - 1, j} (u) d u & = \frac{1}{r} \sum_{h = 1}^{j} B_{r, h} (x), & (11) \\ (1 - x) B_{r - 1, j} (x) & = \frac{r + 1 - j}{r} B_{r, j} (x), \\ \int_{0}^{x} B_{r - 1, j} (u) d u & = \frac{1}{r} \sum_{h = j + 1}^{r + 1} B_{r, h} (x) . & (12) \end{matrix}$

Proof. The two product identities follow from the definition of $B_{r, k}$ and the binomial ratios $\frac{(\binom{r - 1}{j - 1})}{(\binom{r}{j})} = \frac{j}{r}, \frac{(\binom{r - 1}{j - 1})}{(\binom{r}{j - 1})} = \frac{r + 1 - j}{r} .$ The two integral identities follow by differentiating the displayed sums, which telescope, and checking the value at $x = 1$ , respectively $x = 0$ . ◻

The next lemma packages the rank-vector sums in the Bernstein basis. Here and in the rest of this section, $H_{w}^{(m)}$ denotes the polynomial determined by the recurrences (1)–(3).

Lemma 24 (Bernstein packaging of rank vectors).

For every $m \geq 1$ , every $r \geq 0$ , and every word $w \in {+, -}^{r}$ , $r! H_{w}^{(m)} (x) = \sum_{k = 1}^{r + 1} D_{w}^{(m)} (k) B_{r, k} (x) .$

Proof. We induct on the length of $w$ . For $w = ⌀$ , both sides equal $1$ , since $D_{⌀}^{(m)} (1) = 1$ and $B_{0,1} = 1$ .

Let $w = + v$ , where $v$ has length $r - 1 \geq 0$ , and assume the statement for $v$ . By (2) and the induction hypothesis, $r! H_{+ v}^{(m)} (x) = r \sum_{j = 1}^{r} D_{v}^{(m)} (j) (x B_{r - 1, j} (x) + m \int_{x}^{1} B_{r - 1, j} (u) d u) .$ By the degree-raising identities (11), the right-hand side equals $\begin{matrix} \sum_{j = 1}^{r} D_{v}^{(m)} (j) (j B_{r, j + 1} (x) + m \sum_{h = 1}^{j} B_{r, h} (x)) \\ = \sum_{k = 1}^{r + 1} ((k - 1) D_{v}^{(m)} (k - 1) + m \sum_{j = k}^{r} D_{v}^{(m)} (j)) B_{r, k} (x), \end{matrix}$ where the coefficient of $B_{r, k}$ collects the term $j = k - 1$ from the first summand and the terms $j \geq k$ from the second. By (9), this coefficient is $D_{+ v}^{(m)} (k)$ .

The case $w = - v$ is identical, using (3), (12), and (10). ◻

The following positive kernel converts endpoint counts into rank-vector sums.

Definition 25.

For $r \geq m - 1$ , $1 \leq k \leq r + 1$ , and $1 \leq ℓ \leq m$ , set $κ_{r}^{(m)} (k, ℓ) = (k - 1)! (r + 1 - k)! (\binom{m - 1}{ℓ - 1}) (\binom{r - m + 1}{k - ℓ}) .$ We use the convention that $(\binom{a}{b}) = 0$ when $b < 0$ or $b > a$ .

Lemma 26 (Degree elevation for the kernel).

If $r \geq m - 1$ , then $b_{m, ℓ} (x) = \sum_{k = 1}^{r + 1} \frac{κ_{r}^{(m)} (k, ℓ)}{r!} B_{r, k} (x)$ for every $1 \leq ℓ \leq m$ .

Proof. This is the standard degree elevation of the Bernstein basis [4], written in the present normalization. Substituting the definitions gives $\frac{κ_{r}^{(m)} (k, ℓ)}{r!} B_{r, k} (x) = (\binom{m - 1}{ℓ - 1}) (\binom{r - m + 1}{k - ℓ}) x^{k - 1} {(1 - x)}^{r + 1 - k} .$ After summing over $k$ , factor out $(\binom{m - 1}{ℓ - 1}) x^{ℓ - 1} {(1 - x)}^{m - ℓ}$ . The remaining sum is $\sum_{a = 0}^{r - m + 1} (\binom{r - m + 1}{a}) x^{a} {(1 - x)}^{r - m + 1 - a} = 1$ by the binomial theorem. The result is exactly $b_{m, ℓ} (x)$ . ◻

Combining the packaging lemma with the transfer lemma and degree elevation gives the finite transfer directly.

Theorem 27 (Finite Bernstein transfer).

Let $m \geq 1$ , and let $w \in {+, -}^{r}$ with $r \geq m - 1$ . Then, for $1 \leq k \leq r + 1$ , $D_{w}^{(m)} (k) = \sum_{ℓ = 1}^{m} C_{w}^{(m)} (ℓ) κ_{r}^{(m)} (k, ℓ) .$

Proof. By Lemma 3.5 and Lemma 5.7, $r! H_{w}^{(m)} (x) = r! \sum_{ℓ = 1}^{m} C_{w}^{(m)} (ℓ) b_{m, ℓ} (x) = \sum_{k = 1}^{r + 1} (\sum_{ℓ = 1}^{m} C_{w}^{(m)} (ℓ) κ_{r}^{(m)} (k, ℓ)) B_{r, k} (x) .$ By Lemma 5.5, the left-hand side is also $\sum_{k = 1}^{r + 1} D_{w}^{(m)} (k) B_{r, k} (x) .$ The polynomials $B_{r, 1}, \dots, B_{r, r + 1}$ form a basis of the space of polynomials of degree at most $r$ , so the coefficients agree. ◻

Corollary 28 (Diagonal case).

Let $m \geq 1$ and $w \in {+, -}^{m - 1}$ . Then $D_{w}^{(m)} (k) = (m - 1)! C_{w}^{(m)} (k) (1 \leq k \leq m) .$ Equivalently, in the notation of Lemma 5.2: for $n \geq 1$ , $ε \in {+, -}^{n - 1}$ , $w = ε_{n - 1} \dots ε_{1}$ , and $1 \leq k \leq n$ , $\sum_{\begin{matrix} π \in S_{n} \\ π_{n} = k \end{matrix}} n^{{rec}_{ε} (π)} = n! C_{w}^{(n)} (k) .$

Proof. Take $r = m - 1$ in Theorem 5.8: the factor $(\binom{r - m + 1}{k - ℓ}) = (\binom{0}{k - ℓ})$ in Definition 5.6 vanishes unless $k = ℓ$ , so $κ_{m - 1}^{(m)} (k, ℓ) = (m - 1)! δ_{k, ℓ}$ . The permutation form is the case $m = n$ , $r = n - 1$ of the first identity, multiplied by $n$ using Lemma 5.2. ◻

Integrating the degree-elevation identity in Lemma 5.7 gives the column sum $\sum_{k = 1}^{r + 1} κ_{r}^{(m)} (k, ℓ) = \frac{(r + 1)!}{m} .$ Here we used $\int_{0}^{1} B_{r, k} (x) d x = 1 / (r + 1)$ and $\int_{0}^{1} b_{m, ℓ} (x) d x = 1 / m$ . Consequently the finite transfer gives a second, probability-free proof of Theorem 1.1. Indeed, for $w = ε_{n - 1} \dots ε_{1}$ and $1 \leq m \leq n$ , $\begin{matrix} \sum_{π \in S_{n}} m^{{rec}_{ε} (π)} & = m \sum_{k = 1}^{n} D_{w}^{(m)} (k) \\ = m \sum_{ℓ = 1}^{m} C_{w}^{(m)} (ℓ) \sum_{k = 1}^{n} κ_{n - 1}^{(m)} (k, ℓ) \\ = m \sum_{ℓ = 1}^{m} C_{w}^{(m)} (ℓ) \frac{(n - 1)! n}{m} \\ = n! Ω (P_{ε}; m) . \end{matrix}$ The two degree- $\leq n$ polynomials also agree at $m = 0$ , so interpolation completes the argument.

A bijective form of the finite transfer

We construct an object-level bijection between pairs $(σ, f)$ , with $σ \in S_{n}$ and $f : P_{ε} \to [m]$ order-preserving, and pairs $(π, λ)$ , with $π \in S_{n}$ and $λ : {Rec}_{ε} (π) \to [m]$ . A weak map $f$ has $\prod_{a \in [m]} | f^{- 1} (a) |!$ linear refinements inside its level fibers, so direct rank discretization is not fiberwise uniform. The window kernel records this ordering data.

The construction has three ingredients: a window model for the degree-elevation kernel, a local window exchange, and a hole construction for the diagonal identity $D_{w}^{(m)} (k) = (m - 1)! C_{w}^{(m)} (k)$ . Theorem 6.6 gives a direct recursive bijection when $m \leq n$ ; Theorem 6.7 extends it algorithmically to arbitrary alphabets by a finite used-label sieve.

Throughout this section, if $A$ is a finite totally ordered set and $a \in A$ , we write ${std}_{A ∖ {a}} : A ∖ {a} ⟶ [| A | - 1]$ for the increasing bijection. When $A = [N]$ , this is the map $x ⟼ {\begin{matrix} x, & x < a, \\ x - 1, & x > a . \end{matrix}$ We use the inverse map without further comment when we pass back from a standardized set to the original set.

Throughout the constructions below, an instruction to insert an entry in the $b$ -th position of a word or board of length $L - 1$ means that the entry is inserted after the first $b - 1$ entries, so that it occupies position $b$ in the resulting word or board of length $L$ . Thus $b = 1$ means insertion at the beginning and $b = L$ means insertion at the end.

Let $N \geq m$ . For $1 \leq k \leq N$ and $1 \leq ℓ \leq m$ , define $𝒦_{N, m} (k, ℓ)$ to be the set of words $ω = (k; r_{1}, r_{2}, \dots, r_{N - 1})$ , whose entries are the elements of $[N]$ , with first entry $k$ , such that $k$ has rank $ℓ$ in the $m$ -window $k, r_{1}, \dots, r_{m - 1}$ . Equivalently, $ℓ = 1 + # {1 \leq s \leq m - 1 : r_{s} < k} .$ We use the convention that $𝒦_{N, m} (k, ℓ) = ⌀$ whenever one of the indices is outside its natural range.

Direct counting gives $| 𝒦_{N, m} (k, ℓ) | = (k - 1)! (N - k)! (\binom{m - 1}{ℓ - 1}) (\binom{N - m}{k - ℓ}) = κ_{N - 1}^{(m)} (k, ℓ) .$ Indeed, choose the $ℓ - 1$ window elements below $k$ and the $m - ℓ$ window elements above $k$ , then order the window and its complement. The count is $(\binom{k - 1}{ℓ - 1}) (\binom{N - k}{m - ℓ}) (m - 1)! (N - m)!,$ which simplifies to the displayed kernel.

The following local exchange realizes one step of the finite transfer. First suppose $N > m$ , so that the buffer entry $r_{m}$ exists.

Lemma 29 (The $+$ -window exchange).

Fix $N > m$ , $1 \leq k \leq N$ , and $1 \leq j \leq m$ . There is an explicit bijection $\begin{matrix} ⨆_{ℓ \leq j} 𝒦_{N, m} (k, ℓ) & ⟷ ({1, \dots, k - 1} \times 𝒦_{N - 1, m} (k - 1, j)) \\ ⊔ ([m] \times ⨆_{q = k}^{N - 1} 𝒦_{N - 1, m} (q, j)) . \end{matrix}$

Proof. Take $ω = (k; r_{1}, \dots, r_{N - 1}) \in 𝒦_{N, m} (k, ℓ), ℓ \leq j$ , and set $ρ = 1 + # {1 \leq s \leq m - 1 : r_{s} < k} .$ Thus $ρ = ℓ \leq j$ . Let $S = (r_{1}, \dots, r_{m})$ be the extended window.

If $ρ = j$ and $r_{m} < k$ , we are in the non-record case. Put $a = r_{m}$ . Delete $a$ from $ω$ and standardize the remaining entries. The threshold $k$ becomes $k - 1$ , and the first $m$ -window still has threshold rank $j$ . Hence the output is $(a, ω^{'}) \in {1, \dots, k - 1} \times 𝒦_{N - 1, m} (k - 1, j) .$

In all other cases, let $a$ be the $j$ -th smallest element of the extended window $S$ , and let $b \in [m]$ be its position in $S$ . We claim that $a > k$ . Indeed, if $r_{m} > k$ , then the extended window has at most $j - 1$ entries smaller than $k$ . If $r_{m} < k$ , then failure of the non-record case forces $ρ < j$ , and again the extended window has at most $j - 1$ entries smaller than $k$ . Thus the $j$ -th smallest entry of $S$ is larger than $k$ .

This is the record case. Delete the old threshold $k$ , put the new threshold $a$ in front, remove $a$ from the rest word, and standardize. Since $a > k$ , the new threshold has standardized value $q = a - 1, k \leq q \leq N - 1$ . The first $m$ -window after this operation has the same underlying set as $S$ , hence the new threshold has rank $j$ . We output $(b, ω^{'}) \in [m] \times 𝒦_{N - 1, m} (q, j) .$

The inverse map is explicit. In the non-record branch, start with $a < k, ω^{'} \in 𝒦_{N - 1, m} (k - 1, j) .$ Unstandardize by inserting $a$ , so that the threshold $k - 1$ becomes $k$ , and insert $a$ as the $m$ -th entry of the rest word. This recovers the unique $ω$ which falls into the non-record case.

In the record branch, start with $b \in [m], ω^{'} \in 𝒦_{N - 1, m} (q, j), k \leq q \leq N - 1.$ Unstandardize by inserting the old threshold $k$ . The current threshold $q$ becomes $a = q + 1$ . Remove this leading $a$ , put $k$ in front, and insert $a$ in the $b$ -th position of the rest word. Its extended window has $a > k$ as its $j$ -th smallest entry. Every entry below $k$ is below $a$ , so the rank $ℓ$ of $k$ in the reconstructed first window satisfies $ℓ \leq j$ ; hence the object lies in the domain on the left. It cannot satisfy simultaneously $ℓ = j$ and $r_{m} < k$ , because then the extended window would contain at least $j$ entries below $k < a$ , contrary to $a$ being its $j$ -th smallest entry. Thus the reconstruction lies in the record branch, with the prescribed position $b$ . The two inverse constructions are therefore well-defined and inverse to the forward branches. ◻

Corollary 30 (The $-$ -window exchange).

Fix $N > m$ , $1 \leq k \leq N$ , and $1 \leq j \leq m$ . There is an explicit bijection $\begin{matrix} ⨆_{ℓ \geq j} 𝒦_{N, m} (k, ℓ) & ⟷ ({k + 1, \dots, N} \times 𝒦_{N - 1, m} (k, j)) \\ ⊔ ([m] \times ⨆_{q = 1}^{k - 1} 𝒦_{N - 1, m} (q, j)) . \end{matrix}$

Proof. Apply the order-reversing involution $(k; r_{1}, \dots, r_{N - 1}) ⟼ (N + 1 - k; N + 1 - r_{1}, \dots, N + 1 - r_{N - 1}) .$ It sends $𝒦_{N, m} (k, ℓ)$ to $𝒦_{N, m} (N + 1 - k, m + 1 - ℓ)$ . Therefore $ℓ \geq j$ becomes $m + 1 - ℓ \leq m + 1 - j$ , and Lemma 6.1, with threshold $N + 1 - k$ and index $m + 1 - j$ , applies. On the size- $N - 1$ output word use the corresponding order reversal $x \mapsto N - x$ . Its non-record branch becomes ${k + 1, \dots, N} \times 𝒦_{N - 1, m} (k, j),$ and its record thresholds $q^{'} = N + 1 - k, \dots, N - 1$ become $q = N - q^{'} = 1, \dots, k - 1$ . Positions in the extended window are unchanged, so the label in $[m]$ is unchanged. Conjugating the forward and inverse maps of Lemma 6.1 by these order reversals proves the stated bijection and its reversibility. ◻

When $N = m$ , the buffer entry $r_{m}$ is absent; the diagonal case is handled by the following hole construction.

Lemma 31 (The diagonal hole bijection).

Let $m \geq 1$ , let $w \in {+, -}^{m - 1}$ , and fix $1 \leq k \leq m$ . There is a bijection $\begin{matrix} {(α, λ) : α is a scan order of [m] ∖ {k}, λ : {Rec}_{w} (α; k) \to [m]} \\ ⟷ & {(g, ρ) : g is counted by C_{w}^{(m)} (k), ρ \in S_{m - 1}} . \end{matrix}$ Here ${Rec}_{w} (α; k)$ denotes the set of record steps in the threshold scan with initial threshold $k$ and comparison word $w$ .

Proof. We give the map from labeled scan orders to pairs $(g, ρ)$ . Maintain a board with $m$ positions. Each position contains either an actual value $A_{x}$ , $x \in [m]$ , or a hole $H_{t}$ , where $t$ records the time at which the hole was created. Initially the board is $(A_{1}, A_{2}, \dots, A_{m})$ , and the threshold is $A_{k}$ . Thus $g_{0} = k$ .

Process the scan order $α = (a_{1}, \dots, a_{m - 1})$ from left to right. Suppose we are at time $t$ . If the $t$ -th inspected value is not a record, replace the board entry $A_{a_{t}}$ by the hole $H_{t}$ , and keep the threshold unchanged. If it is a record, let $b = λ (t)$ . Delete the old threshold from the board, insert the hole $H_{t}$ in the $b$ -th position, and make $A_{a_{t}}$ the new threshold. After either operation, define $g_{t}$ to be the current position of the threshold.

After time $t$ , the following board invariant holds:

the holes are exactly $H_{1}, \dots, H_{t}$ ;
the actual tokens are the current threshold together with the uninspected values $A_{a_{t + 1}}, \dots, A_{a_{m - 1}}$ , and they occur in increasing value order when the holes are ignored;
the current threshold occupies position $g_{t}$ .

This follows by induction: a non-record replaces its inspected token by a hole, while a record deletes the old threshold and retains the inspected token as the new threshold; neither operation changes the relative order of the remaining actual tokens. Consequently, at a $+$ -step a non-record lies to the left of the threshold and leaves its position unchanged, whereas a record selects an actual token to its right, so the threshold position weakly increases. Thus $w_{t} = + ⟹ g_{t} \geq g_{t - 1} .$ The same argument with left and right interchanged gives $w_{t} = - ⟹ g_{t} \leq g_{t - 1} .$ After $m - 1$ steps, only the final threshold remains actual; the other entries are the holes $H_{1}, \dots, H_{m - 1}$ . Reading their time labels from left to right gives a permutation $ρ \in S_{m - 1}$ .

For the inverse map, start from $(g, ρ)$ and construct the final board by putting one unnamed actual token in position $g_{m - 1}$ , and by putting the holes $H_{ρ_{1}}, H_{ρ_{2}}, \dots, H_{ρ_{m - 1}}$ from left to right in the other positions. This actual token is the current threshold.

For $t = m - 1, m - 2, \dots, 1$ , let $q = g_{t}$ be the current threshold position and let $p$ be the current position of $H_{t}$ . If $w_{t} = +, g_{t} = g_{t - 1}, p < q,$ or if $w_{t} = -, g_{t} = g_{t - 1}, p > q,$ then the original step was a non-record: replace $H_{t}$ by a new actual token, and declare this token to be the $t$ -th scanned token. Otherwise the original step was a record: the current threshold token is the $t$ -th scanned token, the label is $λ (t) = p$ , then delete $H_{t}$ , insert a new actual token in position $g_{t - 1}$ , and make this new token the threshold.

After reversing all steps, the board contains $m$ actual tokens and no holes. Assign the values $1,2, \dots, m$ to these tokens from left to right. Since the threshold is in position $g_{0} = k$ , the initial threshold receives value $k$ . The values assigned to the scanned tokens, in times $1, \dots, m - 1$ , form $α$ , and the labels recovered in the record steps form $λ$ .

To prove reversibility, use descending induction on $t$ . After the steps $m - 1, m - 2, \dots, t + 1$ have been undone, the board is, up to the still unnamed actual tokens, exactly the forward board just after time $t$ , with the same threshold and holes. For a $+$ -step, a forward non-record creates $H_{t}$ strictly to the left of the unchanged threshold, so $g_{t} = g_{t - 1}$ and $p < q$ . In a forward record the new threshold comes from the right of the old one. If deletion of the old threshold and insertion of $H_{t}$ leave the threshold in position $g_{t - 1}$ , then the new threshold was the next actual token to the right and the inserted hole lies to its right; thus $p < q$ is impossible. Hence the inverse criterion detects exactly the non-record $+$ -steps. The argument for a $-$ -step is obtained by interchanging left and right. In either branch the stated reverse operation is the unique inverse of the forward operation, so the induction invariant is restored at time $t - 1$ . After all steps are undone, assigning values in left-to-right order recovers the comparisons, the scan order, and every record label. The constructions are mutually inverse. ◻

Example 32 (The hole construction in action).

Take $m = 4$ , $w = (+, +, -)$ , initial threshold $k = 1$ , scan order $α = (4,3,2)$ , and labels $λ (1) = 2$ and $λ (3) = 1$ . The board starts as $[A_{1}, A_{2}, A_{3}, A_{4}]$ , with the threshold $A_{1}$ in position $g_{0} = 1$ .

$t = 1$ ( $+$ ): $a_{1} = 4 > 1$ is a record. Delete the threshold $A_{1}$ and insert the hole $H_{1}$ in position $λ (1) = 2$ ; the new threshold is $A_{4}$ . The board is $[A_{2}, H_{1}, A_{3}, A_{4}]$ and $g_{1} = 4$ .
$t = 2$ ( $+$ ): $a_{2} = 3 < 4$ is a non-record. Replace $A_{3}$ by $H_{2}$ in place, leaving the threshold $A_{4}$ unchanged. The board is $[A_{2}, H_{1}, H_{2}, A_{4}]$ and $g_{2} = 4$ .
$t = 3$ ( $-$ ): $a_{3} = 2 < 4$ is a record. Delete the threshold $A_{4}$ and insert the hole $H_{3}$ in position $λ (3) = 1$ ; the new threshold is $A_{2}$ . The board is $[H_{3}, A_{2}, H_{1}, H_{2}]$ and $g_{3} = 2$ .

Reading the hole time-labels from left to right gives $ρ = (3,1,2)$ , and the endpoint sequence is $g = (1,4,4,2)$ , weakly increasing across the two $+$ -steps and weakly decreasing across the $-$ -step, as required of a path counted by $C_{w}^{(4)} (1)$ . Thus $(α, λ) \mapsto (g, ρ)$ ; the inverse rebuilds the board from $g$ and $ρ$ , reversing the three steps to recover $(α, λ)$ .

We can now assemble the finite-transfer bijection. For $N \geq m$ , $w \in {+, -}^{N - 1}$ , and $1 \leq k \leq N$ , let $ℛ_{N, m} (w; k)$ denote the set of pairs $(α, λ)$ , where $α$ is a scan order of $[N] ∖ {k}$ and $λ : {Rec}_{w} (α; k) \to [m] .$ Let $𝒯_{N, m} (w; k)$ be the disjoint union $𝒯_{N, m} (w; k) = ⨆_{ℓ = 1}^{m} {g : g is counted by C_{w}^{(m)} (ℓ)} \times 𝒦_{N, m} (k, ℓ) .$

Proposition 33 (Finite-transfer bijection).

For $N \geq m$ , $w \in {+, -}^{N - 1}$ , and $1 \leq k \leq N$ , there is a bijection $Θ_{N, m, w, k} : 𝒯_{N, m} (w; k) ⟶ ℛ_{N, m} (w; k) .$

Proof. We define $Θ_{N, m, w, k}$ recursively on $N$ . If $N = m$ , then $𝒦_{m, m} (k, ℓ)$ is empty unless $ℓ = k$ . For $ω = (k; r_{1}, \dots, r_{m - 1}) \in 𝒦_{m, m} (k, k)$ , standardize the rest word by deleting $k$ : $ρ = ({std}_{[m] ∖ {k}} (r_{1}), \dots, {std}_{[m] ∖ {k}} (r_{m - 1})) \in S_{m - 1} .$ Then apply the inverse direction of Lemma 6.3 to $(g, ρ)$ .

Assume now that $N > m$ , and write $w = s v$ , where $s \in {+, -}$ . Take an input $(g, ω) \in 𝒯_{N, m} (w; k)$ , with $g = (g_{0}, g_{1}, \dots, g_{N - 1}), g_{0} = ℓ$ . Put $j = g_{1}$ and $g^{'} = (g_{1}, \dots, g_{N - 1})$ . In every recursive call below, the labeled scan order returned by the recursive bijection is a tail scan of length $N - 2$ . When this tail is attached after the first scanned value, its scan times are reindexed by $u \mapsto u + 1$ , and the labels on its record steps are transported by this reindexing.

If $s = +$ , then $ℓ \leq j$ , so Lemma 6.1 applies to $ω$ . There are two cases.

In the non-record case it returns $a < k, ω^{'} \in 𝒦_{N - 1, m} (k - 1, j)$ . Recursively apply $Θ_{N - 1, m, v, k - 1}$ to $(g^{'}, ω^{'})$ , obtaining a labeled scan order on the standardized set. Unstandardize the tail by reinserting $a$ , and put $a$ as the first scanned value. No new label is added.

In the record case it returns $b \in [m], ω^{'} \in 𝒦_{N - 1, m} (q, j), k \leq q \leq N - 1.$ The first scanned value is the unstandardized value $a = q + 1$ . Recursively apply $Θ_{N - 1, m, v, q}$ to $(g^{'}, ω^{'})$ , unstandardize the tail by reinserting the old threshold $k$ , put $a$ first, and give this first record the label $b$ .

The construction for $s = -$ is identical, using Lemma 6.2. In the non-record case one has $a > k, ω^{'} \in 𝒦_{N - 1, m} (k, j)$ . Recursively apply $Θ_{N - 1, m, v, k}$ to $(g^{'}, ω^{'})$ , unstandardize the tail by reinserting $a$ , and put $a$ first, with no new label. In the record case one has $b \in [m], ω^{'} \in 𝒦_{N - 1, m} (q, j), 1 \leq q \leq k - 1.$ The first scanned value is the unstandardized value $a = q < k$ . Recursively apply $Θ_{N - 1, m, v, q}$ to $(g^{'}, ω^{'})$ , unstandardize the tail by reinserting the old threshold $k$ , put $a$ first, and give this first record the label $b$ .

The inverse recursion is obtained by reversing these steps. If $N = m$ , apply the forward direction of Lemma 6.3 to the labeled scan order, obtaining $(g, ρ)$ , and then unstandardize $ρ$ by reinserting $k$ to recover $ω = (k; r_{1}, \dots, r_{m - 1})$ . If $N > m$ , read the first scanned value $a$ . Remove this first scanned value from the scan order, and reindex every remaining scan time $i$ as $i - 1$ ; the labels on record steps in the tail are transported by the same reindexing. For a $+$ -step, $a < k$ is the non-record case and $a > k$ is the record case; for a $-$ -step, $a > k$ is the non-record case and $a < k$ is the record case.

In a non-record case there is no label at the first scan time. Standardize the tail by deleting $a$ ; its initial threshold is $k - 1$ for a $+$ -step and $k$ for a $-$ -step. Apply the inverse recursion to recover $g^{'}$ and $ω^{'}$ , and then use the inverse non-record branch of the appropriate local exchange. In a record case the first scan time has a unique label $b$ . Remove it, standardize the tail by deleting the old threshold $k$ , and use initial threshold $q = a - 1$ for a $+$ -step and $q = a$ for a $-$ -step. The inverse recursion followed by the inverse record branch of Lemma 6.1 or Lemma 6.2 recovers $ω$ .

In both cases let $ℓ$ be the rank of $k$ in the reconstructed first $m$ -window and set $g = (ℓ, g^{'})$ . The inverse local exchange places its input in a summand with $ℓ \leq j = g_{0}^{'}$ when $s = +$ , and with $ℓ \geq j$ when $s = -$ . Since, inductively, $g^{'}$ is counted by $C_{v}^{(m)} (j)$ , these inequalities show that $g$ is counted by $C_{s v}^{(m)} (ℓ)$ . Thus the reconstructed pair lies in $𝒯_{N, m} (w; k)$ , and every parameter used by the forward recursion is recovered, so the inverse recursion proves bijectivity. ◻

Theorem 34 (An explicit bijection for $m \leq n$ ).

Let $1 \leq m \leq n$ . For every $ε \in {+, -}^{n - 1}$ , there is an explicit bijection between pairs $(σ, f), σ \in S_{n}, f : P_{ε} \to [m] order-preserving,$ and pairs $(π, λ), π \in S_{n}, λ : {Rec}_{ε} (π) \to [m] .$

Proof. Put $w = ε_{n - 1} ε_{n - 2} \dots ε_{1}$ . Given $(σ, f)$ , set $g_{i} = f (x_{n - i}), 0 \leq i \leq n - 1$ . Then $g$ is counted by $C_{w}^{(m)} (g_{0})$ . Let $ℓ = g_{0}$ . In the first $m$ entries of $σ$ , let $k$ be the $ℓ$ -th smallest entry, and let $a_{0} \in [m]$ be its position. Move $k$ to the first position of $σ$ , preserving the relative order of all other entries. Because $k$ starts among the first $m$ entries, this operation preserves the underlying set of the first $m$ entries; in the resulting word $k$ still has rank $ℓ$ in that set. Thus it gives $ω \in 𝒦_{n, m} (k, ℓ)$ . Apply $Θ_{n, m, w, k} (g, ω)$ to obtain a scan order $α = (α_{1}, \dots, α_{n - 1})$ of $[n] ∖ {k}$ , with labels on its non-terminal records. Define $π_{n} = k, π_{n - i} = α_{i} 1 \leq i \leq n - 1,$ and give the terminal record $n$ the label $λ (n) = a_{0}$ . The remaining labels are those produced by $Θ_{n, m, w, k}$ , translated from scan time $i$ to position $n - i$ . This produces a labeled greedy $ε$ -record object $(π, λ)$ .

The inverse starts with $(π, λ)$ . Put $k = π_{n}$ and $a_{0} = λ (n)$ , and form the scan order $α = (π_{n - 1}, π_{n - 2}, \dots, π_{1})$ . Define a labeling $λ_{tail}$ of the non-terminal record steps of this scan by $λ_{tail} (i) = λ (n - i) i \in {Rec}_{w} (α; k) .$ Apply $Θ_{n, m, w, k}^{- 1}$ to $(α, λ_{tail})$ . This recovers $g$ and $ω = (k; r_{1}, \dots, r_{n - 1}) \in 𝒦_{n, m} (k, g_{0})$ .

Finally, insert the leading $k$ back into the $a_{0}$ -th position of the first $m$ -window: $σ = (r_{1}, \dots, r_{a_{0} - 1}, k, r_{a_{0}}, r_{a_{0} + 1}, \dots, r_{n - 1}) .$ Since $a_{0} \leq m$ , this is exactly the inverse of moving $k$ to the front: it restores the first-window set and the relative order of every other entry. Set $f (x_{n - i}) = g_{i}, 0 \leq i \leq n - 1.$ The inequalities defining $C_{w}^{(m)}$ are exactly the order-preserving conditions for $P_{ε}$ , so this recovers a unique pair $(σ, f)$ . All steps are inverse to the forward construction. ◻

To pass from $m \leq n$ to arbitrary $m$ , observe that every map $f : P_{ε} \to [m]$ , and every record labeling $λ : {Rec}_{ε} (π) \to [m]$ , uses at most $n$ labels.

For a nonempty subset $T \subseteq [m]$ , let $𝒜_{T}$ be the set of pairs $(σ, f)$ with $f : P_{ε} \to T$ order-preserving, where $T$ has the inherited order. Let $ℬ_{T}$ be the set of pairs $(π, λ)$ with $λ : {Rec}_{ε} (π) \to T .$ If $1 \leq | T | = t \leq n$ , let $c_{T} : [t] \to T$ be the increasing bijection. The bijection of Theorem 6.6, transported by $c_{T}$ , gives a bijection $Φ_{T} : 𝒜_{T} ⟶ ℬ_{T} .$ We shall use $Φ_{T}$ only for subsets $T$ of size at most $n$ .

Corollary 35 (Arbitrary alphabets).

For every $m, n \geq 1$ and every $ε \in {+, -}^{n - 1}$ , there is an algorithmic bijection between pairs $(σ, f), σ \in S_{n}, f : P_{ε} \to [m] order-preserving,$ and pairs $(π, λ), π \in S_{n}, λ : {Rec}_{ε} (π) \to [m] .$

Proof. Fix the nonempty set $S \subseteq [m]$ of labels used by an object. Both strata are empty when $| S | > n$ , so assume $| S | \leq n$ , and write $𝒜_{S}^{=} = {(σ, f) \in 𝒜_{S} : im (f) = S}, ℬ_{S}^{=} = {(π, λ) \in ℬ_{S} : im (λ) = S} .$ Apply the Garsia–Milne involution principle [6] to ${\tilde{𝒜}}_{S} = ⨆_{⌀ \neq T \subseteq S} {T} \times 𝒜_{T}, {\tilde{ℬ}}_{S} = ⨆_{⌀ \neq T \subseteq S} {T} \times ℬ_{T},$ with sign ${(- 1)}^{| S | - | T |}$ on the $T$ -summand. On either side, unless all labels of $S$ are used, toggle $c = \min (S ∖ im)$ in $T$ . This is a sign-reversing involution whose fixed points are, respectively, ${S} \times 𝒜_{S}^{=}$ and ${S} \times ℬ_{S}^{=}$ . Since $| T | \leq n$ , the maps $Φ_{T}$ assemble into a sign-preserving bijection between the two signed sets. The involution principle therefore gives an algorithmic bijection $𝒜_{S}^{=} ⟶ ℬ_{S}^{=}$ . Taking the disjoint union over the unique used-label set $S$ proves the result. ◻

Directional and record-set refinements

Decorated directional transfer

The continuous process separates $+$ -records from $-$ -records. For indeterminates $p, q$ and a word $w \in {+, -}^{r}$ , define $K_{w}^{(p, q)} (x) \in ℚ [p, q] [x]$ by $\begin{matrix} K_{⌀}^{(p, q)} (x) & = 1, \\ K_{+ v}^{(p, q)} (x) & = x K_{v}^{(p, q)} (x) + p \int_{x}^{1} K_{v}^{(p, q)} (u) d u, \\ K_{- v}^{(p, q)} (x) & = (1 - x) K_{v}^{(p, q)} (x) + q \int_{0}^{x} K_{v}^{(p, q)} (u) d u . \end{matrix}$ The same conditioning argument as in the proof of Theorem 1.1 gives, for $w = ε_{n - 1} ε_{n - 2} \dots ε_{1}$ , $\sum_{π \in S_{n}} p^{{rec}_{ε}^{+} (π)} q^{{rec}_{ε}^{-} (π)} = n! \int_{0}^{1} K_{w}^{(p, q)} (x) d x .$ Moreover $K_{w}^{(m, m)} = H_{w}^{(m)}$ . At the finite level, the threshold history alone forgets the value inspected at a non-record step. We retain that value as a decoration on the corresponding equality step.

Let $w = w_{1} \dots w_{r} \in {+, -}^{r}$ , and let $1 \leq k \leq r + 1$ . A decorated endpoint path of type $(w, k)$ is a pair $(g, θ)$ with $g = (g_{0}, g_{1}, \dots, g_{r}) \in {[r + 1]}^{r + 1}, g_{0} = k,$ such that $w_{i} = + ⟹ g_{i} \geq g_{i - 1}, w_{i} = - ⟹ g_{i} \leq g_{i - 1}$ for $1 \leq i \leq r$ , together with decorations on the equality steps. More precisely, set $\begin{matrix} S_{+} (g) & = {i : w_{i} = + and g_{i} > g_{i - 1}}, \\ S_{-} (g) & = {i : w_{i} = - and g_{i} < g_{i - 1}}, \end{matrix}$ and $E (g) = {i : g_{i} = g_{i - 1}} .$ For every $i \in E (g)$ we choose a value $θ_{i} \in [r + 1]$ , subject to the following two conditions: $w_{i} = + ⟹ θ_{i} < g_{i - 1}, w_{i} = - ⟹ θ_{i} > g_{i - 1},$ and the list $g_{0}, g_{i} (i \in S_{+} (g) \cup S_{-} (g)), θ_{i} (i \in E (g))$ is a rearrangement of $[r + 1]$ . Let $ℳ_{w} (k)$ denote the set of decorated endpoint paths of type $(w, k)$ , and define $R_{w}^{(p, q)} (k) = \sum_{(g, θ) \in ℳ_{w} (k)} p^{| S_{+} (g) |} q^{| S_{-} (g) |} .$ The scan-order bijection below gives $R_{w}^{(m, m)} (k) = D_{w}^{(m)} (k),$ so this construction refines the rank-vector sums of Definition 5.1 by record direction. The forgetful map $(g, θ) \mapsto g$ preserves the strict $+$ - and strict $-$ -steps, but its fibers need not be singletons. For example, when $w = + +$ and $k = 3$ , the weak path $(3,3,3)$ has two admissible decorations, corresponding to the two orders of the failed values $1$ and $2$ . The decorations retain exactly this missing ordering data.

Theorem 36 (Decorated signed transfer).

Let $w \in {+, -}^{r}$ . Then $r! K_{w}^{(p, q)} (x) = \sum_{k = 1}^{r + 1} R_{w}^{(p, q)} (k) B_{r, k} (x) .$ Consequently, if $n = r + 1$ and $w = ε_{n - 1} ε_{n - 2} \dots ε_{1}$ , then $\sum_{π \in S_{n}} p^{{rec}_{ε}^{+} (π)} q^{{rec}_{ε}^{-} (π)} = \sum_{k = 1}^{n} R_{w}^{(p, q)} (k) = n! \int_{0}^{1} K_{w}^{(p, q)} (x) d x .$ In particular, $n! Ω (P_{ε}; t) = t \sum_{k = 1}^{n} R_{w}^{(t, t)} (k),$ where the factor $t$ marks the terminal record. Thus the direction-refined record weights are matched, in this diagonal model, by direction-marked strict edges on admissibly decorated order-preserving maps.

Proof. We first give the finite bijection behind $R_{w}^{(p, q)} (k)$ . Fix $k \in [r + 1]$ , and let $α = (a_{1}, \dots, a_{r})$ be a permutation of $[r + 1] ∖ {k}$ . Start with threshold $h_{0} = k$ . At step $i$ , declare a record if $w_{i} = + and a_{i} > h_{i - 1}, or w_{i} = - and a_{i} < h_{i - 1} .$ If a record occurs, set $h_{i} = a_{i}$ ; otherwise set $h_{i} = h_{i - 1}$ .

From $α$ construct $(g, θ)$ by setting $g_{i} = h_{i}$ . If step $i$ is not a record, then $g_{i} = g_{i - 1}$ and we set $θ_{i} = a_{i}$ . If step $i$ is a record, no decoration is added. A record in a $+$ -step is exactly a strict $+$ -step $g_{i} > g_{i - 1}$ , and a record in a $-$ -step is exactly a strict $-$ -step $g_{i} < g_{i - 1}$ . A non-record in a $+$ -step has $a_{i} < h_{i - 1} = g_{i - 1}$ , and a non-record in a $-$ -step has $a_{i} > h_{i - 1} = g_{i - 1}$ . Since the entries $k, a_{1}, \dots, a_{r}$ form a permutation of $[r + 1]$ , the defining list for $(g, θ)$ is also a permutation of $[r + 1]$ . Hence $(g, θ) \in ℳ_{w} (k)$ .

Conversely, given $(g, θ) \in ℳ_{w} (k)$ , define $a_{i} = {\begin{matrix} g_{i}, & if g_{i} \neq g_{i - 1}, \\ θ_{i}, & if g_{i} = g_{i - 1} . \end{matrix}$ The permutation condition for $ℳ_{w} (k)$ implies that $(a_{1}, \dots, a_{r})$ is a permutation of $[r + 1] ∖ {k}$ . Moreover, the decoration inequalities force equality steps to be precisely non-record steps, while strict steps are precisely records. Thus the two constructions are inverse to each other and preserve the weight $p^{| S_{+} |} q^{| S_{-} |}$ .

This bijection gives the recurrences $R_{⌀}^{(p, q)} (1) = 1$ and for $v \in {+, -}^{r - 1}$ , $\begin{matrix} R_{+ v}^{(p, q)} (k) & = (k - 1) R_{v}^{(p, q)} (k - 1) + p \sum_{j = k}^{r} R_{v}^{(p, q)} (j), & (13) \\ R_{- v}^{(p, q)} (k) & = (r + 1 - k) R_{v}^{(p, q)} (k) + q \sum_{j = 1}^{k - 1} R_{v}^{(p, q)} (j), & (14) \end{matrix}$ with the boundary convention $R_{v}^{(p, q)} (0) = R_{v}^{(p, q)} (r + 1) = 0$ , so that the out-of-range terms $(k - 1) R_{v}^{(p, q)} (k - 1)$ at $k = 1$ and $(r + 1 - k) R_{v}^{(p, q)} (k)$ at $k = r + 1$ vanish. For instance, in the $+$ -case, a first inspected value below $k$ is a non-record; after deleting it and standardizing, the threshold has rank $k - 1$ , giving the first term. A first inspected value above $k$ is a record and contributes the factor $p$ ; after deleting the old threshold and standardizing, the new threshold has rank $j$ , where $k \leq j \leq r$ . The $-$ -case is analogous.

The Bernstein expansion now follows by induction on $r = | w |$ . Substitute the expansion for the suffix $v$ into the defining recurrence for $K_{+ v}^{(p, q)}$ or $K_{- v}^{(p, q)}$ , and apply the four degree-raising identities in Lemma 5.4. The coefficient of $B_{r, k}$ is respectively the right-hand side of (13) or (14). This is the same coefficient comparison as in Lemma 5.5, with the two record directions carrying separate weights $p$ and $q$ .

Finally, $\int_{0}^{1} B_{r, k} (x) d x = 1 / (r + 1)$ by the same beta integral as for $b_{m, k}$ above. Therefore $(r + 1)! \int_{0}^{1} K_{w}^{(p, q)} (x) d x = \sum_{k = 1}^{r + 1} R_{w}^{(p, q)} (k) .$ When $w = ε_{n - 1} \dots ε_{1}$ , reading a permutation $π \in S_{n}$ with terminal value $π_{n} = k$ from right to left gives a permutation of $[n] ∖ {k}$ with comparison word $w$ . The bijection above identifies its $+$ -records and $-$ -records with strict $+$ - and strict $-$ -steps of the decorated endpoint path. Summing over $k$ gives the direction-refined identity. The order-polynomial specialization follows from Theorem 1.1, since the terminal record contributes one additional factor $t$ . ◻

Record-set fibers and record posets

We refine the greedy statistic by its full record set. For $π \in S_{n}$ , recall that ${Rec}_{ε} (π)$ is the set of greedy $ε$ -record positions of $π$ . Thus $n \in {Rec}_{ε} (π)$ and ${rec}_{ε} (π) = | {Rec}_{ε} (π) |$ .

Fix $R \subseteq [n]$ with $n \in R$ . For $i < n$ , set $ρ_{R} (i) = \min {r \in R : r > i} .$ Thus $ρ_{R} (i)$ is the nearest element of $R$ to the right of $i$ .

Definition 37.

The record poset $Q_{ε, R}$ is the labeled poset on $[n]$ obtained as follows. For each $i < n$ , impose the relation $i <_{Q_{ε, R}} ρ_{R} (i)$ if $(ε_{i} = + and i \notin R) or (ε_{i} = - and i \in R),$ and otherwise impose the opposite relation $ρ_{R} (i) <_{Q_{ε, R}} i .$ Then take the transitive closure.

This indeed defines a poset. The undirected graph formed by the defining edges has one edge ${i, ρ_{R} (i)}$ for each $i < n$ . Iterating $i \mapsto ρ_{R} (i)$ always reaches $n$ , so the graph is connected; since it has $n - 1$ edges, it is a tree. Hence no orientation of these edges can contain a directed cycle.

Example 38.

Let $ε = (+, -, +)$ and $π = 2413$ . The terminal value is $3$ , and none of the values $1,4,2$ , inspected from right to left, resets the threshold. Thus ${Rec}_{ε} (π) = {4}$ . Since $ρ_{{4}} (i) = 4$ for $i = 1,2,3$ , the defining relations of the record tree are $1 <_{Q_{ε, {4}}} 4, 4 <_{Q_{ε, {4}}} 2, 3 <_{Q_{ε, {4}}} 4.$ The inverse word is $π^{- 1} = 3142$ , which respects all three relations.

Lemma 39.

For every $π \in S_{n}$ and every $R \subseteq [n]$ with $n \in R$ , ${Rec}_{ε} (π) = R ⟺ π^{- 1} \in ℒ (Q_{ε, R}),$ where $ℒ (Q_{ε, R})$ denotes the set of linear extensions of $Q_{ε, R}$ .

Proof. Assume first that ${Rec}_{ε} (π) = R$ . When the right-to-left scan reaches a position $i < n$ , the current threshold is $π_{ρ_{R} (i)}$ , because $ρ_{R} (i)$ is the closest record position to the right of $i$ . Since the entries of $π$ are distinct, the condition that $i$ is, or is not, declared a record is equivalent to $π_{i} < π_{ρ_{R} (i)} ⟺ (ε_{i} = + and i \notin R) or (ε_{i} = - and i \in R) .$ This is exactly the comparison encoded by the defining relation between $i$ and $ρ_{R} (i)$ in $Q_{ε, R}$ .

Now $π^{- 1}$ , written in one-line notation, is the word of positions of $1,2, \dots, n$ in $π$ . Therefore a position $a$ occurs before a position $b$ in $π^{- 1}$ if and only if $π_{a} < π_{b}$ . Hence the comparisons above say precisely that $π^{- 1}$ respects every defining relation of $Q_{ε, R}$ , and hence is a linear extension.

Conversely, suppose $π^{- 1} \in ℒ (Q_{ε, R})$ . We show by downward induction on $i$ that the greedy scan of $π$ has record set exactly $R$ . The terminal position $n$ lies in $R$ and is always a record. Assume that every position $> i$ has been scanned and that the record positions among them are exactly $R \cap {i + 1, \dots, n}$ ; then the current threshold when position $i$ is reached is $π_{ρ_{R} (i)}$ . Because $π^{- 1}$ is a linear extension, the relation between $i$ and $ρ_{R} (i)$ in $Q_{ε, R}$ holds, which by the displayed equivalence says that $i$ satisfies the record comparison exactly when $i \in R$ . Hence $i$ is declared a record if and only if $i \in R$ , completing the induction. Therefore the greedy record set is exactly $R$ . ◻

For $R \subseteq [n]$ with $n \in R$ , set $R_{ε}^{+} (R) = {i \in R \cap [n - 1] : ε_{i} = +}, R_{ε}^{-} (R) = {i \in R \cap [n - 1] : ε_{i} = -},$ and write $𝐲^{A} = \prod_{i \in A} y_{i}$ . For a labeled poset $Q$ on $[n]$ and $1 \leq k \leq n$ , define $ℒ_{k} (Q) = {σ = σ_{1} \dots σ_{n} \in ℒ (Q) : σ_{k} = n} .$ For the record poset, define $𝔖_{ε, R} (k) = {π \in S_{n} : {Rec}_{ε} (π) = R, π_{n} = k}$ and $ℓ_{ε, R} (k) = | ℒ_{k} (Q_{ε, R}) | .$

Attach a separate variable to the record status of every inspected position. If $w = w_{1} \dots w_{r}$ , $𝐳 = (z_{1}, \dots, z_{r})$ , and $𝐳^{'} = (z_{2}, \dots, z_{r})$ , define $𝒦_{w}^{(p, q)} (x; 𝐳)$ by $\begin{matrix} 𝒦_{⌀}^{(p, q)} (x; ⌀) & = 1, \\ 𝒦_{+ v}^{(p, q)} (x; z_{1}, 𝐳^{'}) & = x 𝒦_{v}^{(p, q)} (x; 𝐳^{'}) + p z_{1} \int_{x}^{1} 𝒦_{v}^{(p, q)} (u; 𝐳^{'}) d u, \\ 𝒦_{- v}^{(p, q)} (x; z_{1}, 𝐳^{'}) & = (1 - x) 𝒦_{v}^{(p, q)} (x; 𝐳^{'}) + q z_{1} \int_{0}^{x} 𝒦_{v}^{(p, q)} (u; 𝐳^{'}) d u . \end{matrix}$ Thus $𝒦_{w}^{(p, q)} (x; 1, \dots, 1) = K_{w}^{(p, q)} (x)$ .

For $(g, θ) \in ℳ_{w} (k)$ , put $J (g) = S_{+} (g) \cup S_{-} (g)$ . When $n = r + 1$ and $w = ε_{n - 1} \dots ε_{1}$ , define $ℳ_{w} (k; R) = {(g, θ) \in ℳ_{w} (k) : {n - j : j \in J (g)} = R ∖ {n}} .$

Theorem 40 (Record-set Bernstein transfer).

Let $n \geq 1$ , $ε \in {+, -}^{n - 1}$ , and $w = ε_{n - 1} \dots ε_{1}$ . For every $R \subseteq [n]$ with $n \in R$ and every $k \in [n]$ , there are explicit bijections $ℳ_{w} (k; R) ⟷ 𝔖_{ε, R} (k) ⟷ ℒ_{k} (Q_{ε, R}) .$ In particular, $| ℳ_{w} (k; R) | = | 𝔖_{ε, R} (k) | = ℓ_{ε, R} (k) .$ Moreover, with $r = n - 1$ , $\begin{matrix} r! 𝒦_{w}^{(p, q)} (x; y_{n - 1}, y_{n - 2}, \dots, y_{1}) \\ = \sum_{k = 1}^{n} \sum_{\begin{matrix} R \subseteq [n] \\ n \in R \end{matrix}} ℓ_{ε, R} (k) p^{| R_{ε}^{+} (R) |} q^{| R_{ε}^{-} (R) |} 𝐲^{R ∖ {n}} B_{r, k} (x) . & (15) \end{matrix}$ Consequently, $\begin{matrix} y_{n} n! \int_{0}^{1} 𝒦_{w}^{(p, q)} (x; y_{n - 1}, \dots, y_{1}) d x \\ = \sum_{π \in S_{n}} 𝐲^{{Rec}_{ε} (π)} p^{{rec}_{ε}^{+} (π)} q^{{rec}_{ε}^{-} (π)} \\ = \sum_{\begin{matrix} R \subseteq [n] \\ n \in R \end{matrix}} 𝐲^{R} p^{| R_{ε}^{+} (R) |} q^{| R_{ε}^{-} (R) |} | ℒ (Q_{ε, R}) | . & (16) \end{matrix}$

Proof. Fix $k$ , and write the entries inspected from right to left as $α = (a_{1}, \dots, a_{r})$ , where $a_{j} = π_{n - j}$ . Thus $α$ is a permutation of $[n] ∖ {k}$ . The bijection in the proof of Theorem 7.1 sends $α$ to its threshold history $g$ and stores $a_{j}$ as $θ_{j}$ precisely when step $j$ is not a record. A strict step at time $j$ is equivalent to a record at position $n - j$ . Hence that bijection restricts to $ℳ_{w} (k; R) ⟷ 𝔖_{ε, R} (k) .$ By Lemma 7.4, the map $π \mapsto π^{- 1}$ sends the latter set bijectively to linear extensions of $Q_{ε, R}$ . Finally, $π_{n} = k ⟺ {(π^{- 1})}_{k} = n,$ so its image is exactly $ℒ_{k} (Q_{ε, R})$ .

For the Bernstein expansion, attach the additional weight $z_{j}$ to a record at scan time $j$ in the proof of Theorem 7.1. The same first-step recurrence, with $p, q$ replaced by $p z_{j}, q z_{j}$ , gives $r! 𝒦_{w}^{(p, q)} (x; 𝐳) = \sum_{k = 1}^{r + 1} A_{w} (k; 𝐳) B_{r, k} (x) .$ Here $A_{w} (k; 𝐳)$ is the weighted generating polynomial of scan orders on $[r + 1] ∖ {k}$ . Taking $z_{j} = y_{n - j}$ , the two bijections above give $A_{w} (k; y_{n - 1}, \dots, y_{1}) = \sum_{\begin{matrix} R \subseteq [n] \\ n \in R \end{matrix}} ℓ_{ε, R} (k) p^{| R_{ε}^{+} (R) |} q^{| R_{ε}^{-} (R) |} 𝐲^{R ∖ {n}},$ which proves (15). Integrating and using $\int_{0}^{1} B_{r, k} (x) d x = 1 / n$ gives (16), since $\sum_{k} ℓ_{ε, R} (k) = | ℒ (Q_{ε, R}) |$ . ◻

A $P$ -partition consequence

For a word $σ = σ_{1} \dots σ_{n}$ with distinct letters, set $Des (σ) = {i : σ_{i} > σ_{i + 1}}$ . For $S \subseteq [n - 1]$ , let $F_{S, n} (𝐱) = \sum_{\begin{matrix} 1 \leq a_{1} \leq \dots \leq a_{n} \\ a_{i} < a_{i + 1} for i \in S \end{matrix}} x_{a_{1}} \dots x_{a_{n}}$ be Gessel’s fundamental quasisymmetric function. For a labeled poset $Q$ on $[n]$ , define its pointed enumerators $Γ_{k} (Q) = \sum_{σ \in ℒ_{k} (Q)} F_{Des (σ), n} (𝐱) .$ Their sum over $k$ is the usual fundamental $P$ -partition enumerator [19, 7].

For $k \in [n]$ , define $ℛ_{ε, k}^{∙} (𝐱; 𝐲; u, v) = \sum_{\begin{matrix} π \in S_{n} \\ π_{n} = k \end{matrix}} 𝐲^{{Rec}_{ε} (π) ∖ {n}} u^{{rec}_{ε}^{+} (π)} v^{{rec}_{ε}^{-} (π)} F_{Des (π^{- 1}), n} (𝐱) .$

Corollary 41 (Fixed-terminal $P$ -partition lift).

For every $k \in [n]$ , $ℛ_{ε, k}^{∙} = \sum_{\begin{matrix} R \subseteq [n] \\ n \in R \end{matrix}} 𝐲^{R ∖ {n}} u^{| R_{ε}^{+} (R) |} v^{| R_{ε}^{-} (R) |} Γ_{k} (Q_{ε, R}) .$

Proof. By Lemma 7.4, inversion maps the permutations with record set $R$ bijectively to $ℒ (Q_{ε, R})$ . Moreover, $π_{n} = k$ if and only if ${(π^{- 1})}_{k} = n$ , so the fixed-terminal fiber maps to $ℒ_{k} (Q_{ε, R})$ . Grouping the defining sum by $R$ gives the identity. ◻

Summing over $k$ and applying the standard stable principal specialization ${ps}_{q} : x_{i} \mapsto q^{i - 1}$ , for which ${ps}_{q} (F_{S, n}) = q^{{comaj}_{n} (S)} / {(q; q)}_{n}$ , where ${comaj}_{n} (S) = \sum_{i \in S} (n - i)$ , gives ${(q; q)}_{n} {ps}_{q} (y_{n} \sum_{k = 1}^{n} ℛ_{ε, k}^{∙}) = \sum_{π \in S_{n}} q^{{comaj}_{n} (Des (π^{- 1}))} 𝐲^{{Rec}_{ε} (π)} u^{{rec}_{ε}^{+} (π)} v^{{rec}_{ε}^{-} (π)} .$ Here ${(q; q)}_{n} = \prod_{i = 1}^{n} (1 - q^{i})$ .

Record caterpillars and terminal values

Atkinson’s algorithm for posets whose cover graph is a tree proceeds through the position spectrum of a distinguished element and runs in quadratic time [1]. Record posets have caterpillar cover graphs, so its recursion has the following explicit form in record-gap coordinates. By Theorem 7.5, this distinguished-element spectrum is the terminal-value distribution in a fixed record-set fiber.

Lemma 42 (Record-caterpillar structure).

Write $R = {r_{1} < \dots < r_{s} = n}$ and set $r_{0} = 0$ . The undirected Hasse diagram of $Q_{ε, R}$ is a caterpillar with spine $r_{1} - r_{2} - \dots - r_{s} .$ For $r_{j - 1} < i < r_{j}$ , the vertex $i$ is a leaf adjacent to $r_{j}$ , and $i <_{Q_{ε, R}} r_{j} ⟺ ε_{i} = + .$ For $2 \leq j \leq s$ , the orientation of the $j$ -th spine edge is $r_{j - 1} <_{Q_{ε, R}} r_{j} ⟺ ε_{r_{j - 1}} = - .$

Proof. If $i \notin R$ , then $ρ_{R} (i) = r_{j}$ for the unique $j$ satisfying $r_{j - 1} < i < r_{j}$ . No defining edge can have such an $i$ as its right endpoint, so $i$ is a leaf. If $i = r_{j - 1} \in R$ , then $ρ_{R} (i) = r_{j}$ , producing the spine edge. The two orientation statements are immediate from Definition 7.2. The defining undirected graph is a tree, so none of its edges can be made redundant by transitive closure; therefore it is the undirected Hasse diagram. ◻

For $1 \leq j \leq s$ , let $Q_{j}$ be the subposet of $Q_{ε, R}$ induced by $[r_{j}]$ , and define the root spectrum $h_{j} (k) = # {σ \in ℒ (Q_{j}) : σ_{k} = r_{j}} (1 \leq k \leq r_{j}) .$ Also put $a_{j} = # {i : r_{j - 1} < i < r_{j}, ε_{i} = +}, b_{j} = # {i : r_{j - 1} < i < r_{j}, ε_{i} = -} .$ Thus $a_{j} + b_{j} = r_{j} - r_{j - 1} - 1$ .

Proposition 43 (Record-gap specialization of Atkinson’s recursion).

The initial spectrum is concentrated at one position: $h_{1} (k) = {\begin{matrix} a_{1}! b_{1}!, & k = a_{1} + 1, \\ 0, & k \neq a_{1} + 1. \end{matrix}$ For $2 \leq j \leq s$ and $0 \leq d \leq r_{j - 1}$ , define $C_{j} (d) = {\begin{matrix} \sum_{t = 1}^{d} h_{j - 1} (t), & ε_{r_{j - 1}} = -, \\ \sum_{t = d + 1}^{r_{j - 1}} h_{j - 1} (t), & ε_{r_{j - 1}} = + . \end{matrix}$ Then $\begin{matrix} h_{j} (d + a_{j} + 1) = a_{j}! b_{j}! (\binom{d + a_{j}}{a_{j}}) (\binom{r_{j - 1} - d + b_{j}}{b_{j}}) C_{j} (d) . & (17) \end{matrix}$ All other entries of $h_{j}$ are zero. In particular, $ℓ_{ε, R} (k) = h_{s} (k), # {π \in S_{n} : {Rec}_{ε} (π) = R} = \sum_{k = 1}^{n} h_{s} (k) .$ After factorials and binomial coefficients have been precomputed, the entire vector $(h_{s} (1), \dots, h_{s} (n))$ is obtained in $O (n^{2})$ arithmetic operations.

Proof. For $j = 1$ , the $a_{1}$ lower leaves must occur before $r_{1}$ , the $b_{1}$ upper leaves must occur after $r_{1}$ , and the leaves within either group may be ordered arbitrarily. This gives the stated initial spectrum.

Fix $j \geq 2$ and a linear extension $τ$ of $Q_{j - 1}$ . When $r_{j}$ is inserted, let $d$ be the number of entries of $τ$ placed before $r_{j}$ . If $r_{j - 1} <_{Q_{ε, R}} r_{j}$ , the entry $r_{j - 1}$ must belong to this prefix, so its position in $τ$ is at most $d$ . If $r_{j} <_{Q_{ε, R}} r_{j - 1}$ , it must belong to the suffix, so its position is larger than $d$ . By Lemma 8.1, the number of admissible choices of $τ$ is therefore exactly $C_{j} (d)$ .

For a fixed admissible $τ$ , interleave its ordered prefix of length $d$ with the $a_{j}$ distinct lower leaves. This can be done in $a_{j}! (\binom{d + a_{j}}{a_{j}})$ ways. Independently, interleave its ordered suffix of length $r_{j - 1} - d$ with the $b_{j}$ distinct upper leaves, in $b_{j}! (\binom{r_{j - 1} - d + b_{j}}{b_{j}})$ ways. The root $r_{j}$ lies between these two words and hence occupies position $d + a_{j} + 1$ . This construction is reversible by restricting a linear extension of $Q_{j}$ to $[r_{j - 1}]$ and to the two leaf sets, so it counts every extension exactly once and proves (17). The final identities follow from Theorem 7.5. Prefix or suffix sums compute every array $C_{j}$ in $O (r_{j - 1})$ operations, and summing over $j$ gives the stated quadratic bound. ◻

Remark 44 (Terminal-value range).

For any finite poset $Q$ and $x \in Q$ , the possible positions of $x$ among the linear extensions form the interval $[| Q_{< x} | + 1, | Q | - | Q_{> x} |] \cap ℤ .$ For the record caterpillar this gives integers $L_{j} \leq U_{j}$ such that $h_{j} (k) > 0 ⟺ L_{j} \leq k \leq U_{j} .$ In gap coordinates, $L_{1} = U_{1} = a_{1} + 1$ and $(L_{j}, U_{j}) = {\begin{matrix} (a_{j} + L_{j - 1} + 1, r_{j} - b_{j}), & ε_{r_{j - 1}} = -, \\ (a_{j} + 1, a_{j} + U_{j - 1}), & ε_{r_{j - 1}} = + . \end{matrix}$ Consequently, ${π_{n} : {Rec}_{ε} (π) = R} = [L_{s}, U_{s}] \cap ℤ .$

Remark 45 (Gap-data invariance).

Fix $R = {r_{1} < \dots < r_{s} = n}$ . Suppose that $ε, ε^{'} \in {+, -}^{n - 1}$ have the same signs at $r_{1}, \dots, r_{s - 1}$ and the same number of $+$ -signs in every open gap $(r_{j - 1}, r_{j})$ . Then, for every $k \in [n]$ , $# {π : {Rec}_{ε} (π) = R, π_{n} = k} = # {π : {Rec}_{ε^{'}} (π) = R, π_{n} = k} .$ Indeed, the hypotheses give an isomorphism of rooted record caterpillars: match the spine vertices and, in each gap, match $+$ -leaves to $+$ -leaves and $-$ -leaves to $-$ -leaves. The isomorphism fixes the distinguished vertex $n$ , so the spectra agree.

Example 46.

Let $ε = (+, -, +)$ and $R = {1,2,4}$ . The record poset has cover relations $2 < 1, 2 < 4, 3 < 4.$ The recursion gives $\begin{matrix} (h_{1} (1)) & = (1), & (h_{2} (1), h_{2} (2)) & = (1,0), \\ (h_{3} (1), \dots, h_{3} (4)) & = (0,0,2,3) . \end{matrix}$ Indeed, its five linear extensions are $2134, 2314, 2341, 3214, 3241.$ The corresponding inverse permutations are $2134, 3124, 4123, 3214, 4213.$ Two have terminal value $3$ , three have terminal value $4$ , and all have record set $R$ . Thus the contribution of this fixed record set to (15) is $p q y_{1} y_{2} (2 B_{3,3} (x) + 3 B_{3,4} (x)) .$

Concluding remarks

The path construction is refined above by endpoint, record-set, direction, and terminal-value data, while the cyclic construction replaces the distinguished endpoint by a canonical root. It remains open whether the record-set Bernstein transfer and its $P$ -partition consequence admit cyclic analogues.

Acknowledgements

The author thanks Neil J. Y. Fan for drawing attention to Problem 5.3 of Ferroni–Morales–Panova and for his encouragement, and Quanyu Tang for helpful discussions and suggestions.

References

M. D. Atkinson, On computing the number of linear extensions of a tree, Order 7 (1990), no. 1, 23–25, doi:10.1007/BF00383170.
H. Z. Q. Chen and P. B. Zhang, The unimodality of the Ehrhart $δ$ -polynomial of the chain polytope of the zig-zag poset, arXiv:1603.08283, 2016.
J. I. Coons and S. Sullivant, The $h^{*}$ -polynomial of the order polytope of the zig-zag poset, Electron. J. Combin. 30 (2023), no. 2, Paper No. 2.44, 20 pp.
R. T. Farouki, The Bernstein polynomial basis: a centennial retrospective, Comput. Aided Geom. Design 29 (2012), no. 6, 379–419, doi:10.1016/j.cagd.2012.03.001.
L. Ferroni, A. H. Morales, and G. Panova, Skew shapes, Ehrhart positivity and beyond, Proc. Lond. Math. Soc., to appear; arXiv:2503.16403v3, 2026.
A. M. Garsia and S. C. Milne, A Rogers–Ramanujan bijection, J. Combin. Theory Ser. A 31 (1981), no. 3, 289–339, doi:10.1016/0097-3165(81)90062-5.
I. M. Gessel, Multipartite $P$ -partitions and inner products of skew Schur functions, in Combinatorics and Algebra (Boulder, Colo., 1983), Contemp. Math., vol. 34, Amer. Math. Soc., Providence, RI, 1984, pp. 289–317.
I. M. Gessel and C. Krattenthaler, Cylindric partitions, Trans. Amer. Math. Soc. 349 (1997), no. 2, 429–479, doi:10.1090/S0002-9947-97-01791-1.
Y. Kahane, Combinatorial interpretation of the coefficients of the order polynomial of fence posets, arXiv:2607.11225v1 [math.CO], 13 July 2026.
W. Kang, K. Lee, and E. Lim, Unimodality and cluster algebras from surfaces, European J. Combin. 136 (2026), Paper No. 104392, doi:10.1016/j.ejc.2026.104392.
E. Kantarcı Oğuz, Oriented posets, rank matrices and $q$ -deformed Markov numbers, Discrete Math. 348 (2025), no. 2, Paper No. 114256, 17 pp., doi:10.1016/j.disc.2024.114256.
E. Kantarcı Oğuz, C. Y. Özel, and M. Ravichandran, Chainlink polytopes and Ehrhart equivalence, Ann. Comb. 28 (2024), no. 4, 1141–1166, doi:10.1007/s00026-023-00683-x.
E. Kantarcı Oğuz and M. Ravichandran, Rank polynomials of fence posets are unimodal, Discrete Math. 346 (2023), no. 2, Paper No. 113218, 20 pp.
T. Lundström and L. Saud Maia Leite, Order polytopes of crown posets, European J. Combin. 133 (2026), Paper No. 104304, 24 pp., doi:10.1016/j.ejc.2025.104304.
S. Morier-Genoud and V. Ovsienko, $q$ -deformed rationals and $q$ -continued fractions, Forum Math. Sigma 8 (2020), Paper No. e13, 55 pp.
T. K. Petersen and Y. Zhuang, Zig-zag Eulerian polynomials, European J. Combin. 124 (2025), Paper No. 104073, 30 pp., doi:10.1016/j.ejc.2024.104073.
R. P. Stanley, Two poset polytopes, Discrete Comput. Geom. 1 (1986), no. 1, 9–23.
R. P. Stanley, A survey of alternating permutations, in Combinatorics and Graphs, Contemp. Math., vol. 531, Amer. Math. Soc., Providence, RI, 2010, pp. 165–196.
R. P. Stanley, Ordered structures and partitions, Mem. Amer. Math. Soc., no. 119, Amer. Math. Soc., Providence, RI, 1972.
R. P. Stanley, Enumerative Combinatorics, Volume 1, second edition, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 2012.