pith. sign in

arxiv: 2604.10779 · v2 · submitted 2026-04-12 · 🧮 math.CO

Polynomial Time Enumeration of t-Stack-Sortable Permutations Ending in Their Least Entry

Jerry Zhang This is my paper

Pith reviewed 2026-05-10 15:37 UTC · model grok-4.3

classification 🧮 math.CO
keywords stack-sortingt-stack-sortable permutationsstack-sorting tableauxpolynomial-time enumerationWest's stack-sorting mappermutations ending with least entrycombinatorial objectsenumeration algorithms
0
0 comments X

The pith

Stack-sorting tableaux enable the first polynomial-time algorithm for counting t-stack-sortable permutations ending with their least entry.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper focuses on permutations in S_n' that end with 0, their smallest number. It introduces the stack-sorting tableau T_π as a new object to model how West's stack-sorting map acts on these permutations. This modeling supports a polynomial-time procedure to count how many such permutations are t-stack-sortable. The work also links the sorting behavior in this restricted set to the full symmetric group S_n. Readers interested in combinatorial enumeration would find this useful because it solves an open counting problem for a natural subclass of permutations.

Core claim

For each permutation π in S_n', the stack-sorting tableau T_π is introduced as a combinatorial object that accurately represents the action of the stack-sorting map s. This object is the foundation for a polynomial-time algorithm that counts the t-stack-sortable permutations within S_n'. Additionally, a precise relationship is established between the behavior of s on S_n' and on the standard set S_n of permutations.

What carries the argument

The stack-sorting tableau T_π, a new combinatorial object that models the stack-sorting process for permutations ending in their least entry, allowing structural analysis for counting purposes.

If this is right

  • The number of t-stack-sortable permutations in S_n' can be determined in time polynomial in n.
  • The action of the stack-sorting map s on S_n' can be related directly to its action on S_n.
  • Enumeration problems for stack-sortable permutations gain an efficient method when restricted to those ending with their minimum entry.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This approach could potentially be adapted to count t-stack-sortable permutations without the ending restriction by building on the relationship to S_n.
  • Similar tableau constructions might apply to other sorting maps or permutation classes in combinatorics.
  • Polynomial-time counting may reveal asymptotic behaviors or generating functions for these objects.

Load-bearing premise

The stack-sorting tableau T_π must correctly encode the sequence of operations under the stack-sorting map so that its properties directly yield the count without exponential search.

What would settle it

A counterexample would be a specific permutation in S_n' where the tableau construction fails to match the actual number of applications of s needed to sort it, or where the proposed counting algorithm produces an incorrect total for small n that can be verified by brute force.

Figures

Figures reproduced from arXiv: 2604.10779 by Jerry Zhang.

Figure 1
Figure 1. Figure 1: West’s stack-sorting map applied on π = 1324. For all t ∈ N, a permutation π is t-stack-sortable if and only if ⟨π⟩ ≤ t. The set of all t￾stack-sortable permutations in Sn is denoted by Wt(n). In 1968, Knuth showed that |W1(n)| was given by the nth Catalan number Cn. Theorem 1.1 (Knuth [4]). For all n ∈ N, |W1(n)| = Cn = 1 n + 1 2n n  . An explicit formula for |W2(n)| was conjectured by West and proved b… view at source ↗
read the original abstract

We study the behavior of West's stack-sorting map $s$ on permutations whose last entry is also their least. Let $S_{n}':=\{\pi0\mid \pi\in S_n\}$ where $\pi0$ denotes the concatenation of $\pi$ and $0$. For each permutation $\pi\in S_n'$, we introduce a new combinatorial object known as the stack-sorting tableau $T_{\pi}$, which ultimately serves as the key ingredient in the first polynomial time algorithm for counting the number of $t$-stack-sortable permutations in $S_n'$. We then establish a precise relationship between the behavior of $s$ on $S_{n}'$ and on $S_{n}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper introduces the stack-sorting tableau T_π for permutations π in S_n' (those ending in their least entry 0), defined by an explicit insertion procedure recording the sequence of operations under West's stack-sorting map s. It gives a recursive decomposition of these tableaux indexed by the number of applications of s, derives a dynamic-programming recurrence whose state space is polynomial in n for each fixed t, and proves by induction on n a bijection between the t-stack-sortable elements of S_n' and certain restricted tableaux. The relationship between the action of s on S_n' and on S_n is used only to transfer the resulting counts.

Significance. If the claimed bijection and recurrence hold, the work supplies the first polynomial-time algorithm (for fixed t) to enumerate t-stack-sortable permutations ending in their minimal entry. The new tableau object and its inductive decomposition provide a concrete combinatorial tool for analyzing iterated stack-sorting, and the explicit transfer of counts from S_n strengthens the connection to the existing literature on stack-sortable permutations.

minor comments (3)
  1. The abstract states that the algorithm runs in polynomial time, but the introduction and complexity analysis should explicitly note that the degree of the polynomial depends on t (as is standard for fixed-t enumeration results) and give the precise dependence on t arising from the DP state space.
  2. Definition of the stack-sorting tableau T_π: an illustrative example showing the insertion procedure for a small permutation (e.g., n=4 or 5) would improve readability and help verify that the recording of stack operations matches the claimed recursive decomposition.
  3. In the inductive proof of the bijection, the base case n=1 (or the smallest n for each t) should be stated explicitly and checked before proceeding to the inductive step.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and for recommending minor revision. No major comments were raised.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The manuscript defines the stack-sorting tableau T_π by an explicit insertion procedure that records stack operations on permutations ending in 0. It then proves a bijection to t-stack-sortable elements of S_n' by induction on n and supplies a dynamic-programming recurrence whose state space is polynomial in n for each fixed t. The relationship to the ordinary stack-sorting map s on S_n is invoked only to transfer the final count, not to establish the algorithm or the bijection. No equation or definition reduces to a prior fitted parameter, self-citation, or ansatz smuggled from the authors' own prior work; the central claims rest on independent combinatorial constructions and induction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 1 invented entities

Only the abstract is available, so the ledger reflects the single explicitly mentioned new object with no free parameters or axioms described.

invented entities (1)
  • stack-sorting tableau T_π no independent evidence
    purpose: key ingredient for the polynomial-time counting algorithm of t-stack-sortable permutations in S_n'
    New combinatorial object introduced in the abstract to enable the claimed enumeration result.

pith-pipeline@v0.9.0 · 5411 in / 1132 out tokens · 74426 ms · 2026-05-10T15:37:29.788366+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

6 extracted references · 6 canonical work pages

  1. [1]

    O. Chen, M. Luo, and J. Zhang. A disproof of two conjectures on stack-sorting maps for words. Annals of Combinatorics , 2025

    work page 2025

  2. [2]

    C. Defant. Counting 3-stack-sortable permutations. Journal of Combinatorial Theory, Series A , 172, 2020

    work page 2020

  3. [3]

    The on-line encyclopedia of integer sequences, 2026

    OEIS Foundation Inc. The on-line encyclopedia of integer sequences, 2026. Sequence A001006

    work page 2026

  4. [4]

    D. Knuth. The Art of Computer Programming, Vol. 1: Fundamental Algorithms . Addison-Wesley, 1968

    work page 1968

  5. [5]

    J. West. Permutations with restricted subsequences and stack-sortable permutations. Ph.D. Thesis, 1990

    work page 1990

  6. [6]

    Zeilberger

    D. Zeilberger. A proof of Julian West’s conjecture that the number of two-stack-sortable permutations of length n is 2(3n)!/((n + 1)!(2n + 1)!). Discrete Mathematics, 102:85–93, 1992. J. Zhang, South Pasadena High School, South Pasadena, CA, 91030 Email address : jerrylezhang@gmail.com

    work page 1992