pith. sign in

arxiv: 2605.23519 · v1 · pith:3C3XLDPTnew · submitted 2026-05-22 · 🧮 math.CO

Finite-state enumeration of adjacency-constrained 132-avoiding permutations

Teruki Mayama , Dai Akita This is my paper

Pith reviewed 2026-05-25 04:00 UTC · model grok-4.3

classification 🧮 math.CO
keywords 132-avoiding permutationsadjacency-constrained permutationsrational generating functionsfinite-state enumerationpattern-avoiding permutationsenumerative combinatoricsasymptotic enumeration
0
0 comments X

The pith

A two-sided endpoint-state decomposition with at most (m+1)^2 states shows that the generating function for adjacency-constrained 132-avoiding permutations is rational for every fixed m.

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

The authors develop a method to count 132-avoiding permutations where each consecutive pair differs by at most a fixed m. Their decomposition tracks the shortfalls of the first and last entries from n using a finite set of thresholds. This finite-state system proves that the ordinary generating function is always rational and computable via linear algebra. The same system yields recurrences, explicit formulas for small m, and growth rates that increase with m but stay below the Catalan growth rate of 4.

Core claim

The paper claims that by decomposing the permutations according to threshold bounds on the deficiencies n-π1 and n-πn, where the thresholds are 0 through m-1 or infinity, one obtains a finite automaton with at most (m+1)^2 states whose transfer matrix gives the rational generating function A^(m)(x). This decomposition is two-sided and works uniformly for all m, allowing recovery of the m=2 case, explicit computation for m=3, and asymptotic results including the existence of the growth constant from spectral radii of cyclic components.

What carries the argument

two-sided endpoint-state decomposition tracking thresholds on endpoint deficiencies n-π1 and n-πn

If this is right

  • For each fixed m the sequence satisfies an eventual constant-coefficient linear recurrence whose order is bounded by the size of the strongly connected components.
  • The growth constant is the maximum spectral radius of the two main cyclic components in the state graph for m≥2.
  • Explicit asymptotics with simple poles hold for m=2 and m=3.
  • The growth constants increase with m and approach 4 as m tends to infinity.
  • The method recovers known results for m=2 and provides new ones for m=3.

Where Pith is reading between the lines

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

  • Similar state decompositions could apply to other pattern avoidance problems with local adjacency restrictions.
  • As m increases the growth rate approaches the unrestricted 132-avoiding case, suggesting the constraint's effect diminishes asymptotically.
  • The bound on the recurrence order from the strongly connected components could be tightened with further analysis of the dependency graph.

Load-bearing premise

The proposed decomposition captures exactly the set of all adjacency-constrained 132-avoiding permutations through its state transitions.

What would settle it

Enumerating all such permutations for n up to 20 when m=3 by direct search and verifying that the counts match those generated from the 16-state transition matrix.

Figures

Figures reproduced from arXiv: 2605.23519 by Dai Akita, Teruki Mayama.

Figure 1
Figure 1. Figure 1: Illustration of the dependency graph Γ2. The dotted red arcs are split-edges; the two arcs starting at (0,∞) are 2-split edges, and the remaining dotted arcs are 1-split edges. The solid blue arcs are append-edges. The dashed enclosures indicate the cyclic strongly connected components U2, V2, and I2, identified in Proposition 2.7 [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The finite–finite feedback component Vm. The vertices shown are the states (r, s) with 0 ≤ s < r ≤ m−1 and the states (r, m−1) with 0 ≤ r ≤ m−2. Only the arrows used in the proof of strong connectivity are drawn: solid blue arrows are append-edges, and dotted red arrows are k-split. Conversely, every vertex of Vm reaches b. First consider a vertex of the form (r, m − 1) with 0 ≤ r ≤ m−2. If r < m−2, use ap… view at source ↗
read the original abstract

For a fixed integer $m\ge 1$, let $\mathcal{A}_n^{(m)}$ be the set of permutations $\pi\in S_n$ that avoid the pattern $132$ and satisfy the adjacency bound $|\pi_{i+1}-\pi_i|\le m$ for all $i$. Here, a pattern $132$ means three indices $i<j<k$ such that $\pi_i<\pi_k<\pi_j$. A recent study initiated the enumeration of these constrained 132-avoiding permutations, treating the case $m=2$ by deriving a rational ordinary generating function and asking for finite-state decompositions, rational generating functions, and explicit rational formulas for larger fixed $m$. We introduce a two-sided endpoint-state decomposition that works uniformly for every fixed $m$. The state variables impose threshold bounds on the endpoint deficiencies $n-\pi_1$ and $n-\pi_n$, with thresholds in $\{0,1,\ldots,m-1,\infty\}$. This gives at most $(m+1)^2$ states and proves that, for every fixed $m$, the ordinary generating function $A^{(m)}(x)$ is rational and can be computed effectively by exact linear algebra. We also identify cyclic strongly connected components of the dependency graph in the finite-state system to give an explicit upper bound for the order of an eventual constant-coefficient recurrence satisfied by the sequence $a_n^{(m)}=|\mathcal{A}_n^{(m)}|$. We then recover the known case $m=2$ from this state system and work out the case $m=3$ explicitly. On the asymptotic side, we prove that the exponential growth constant exists for every $m$; for $m\ge2$ it is obtained from the spectral radii of the two cyclic components with more than one vertex in the state system. We determine the simple-pole asymptotics for $m=2$ and $m=3$, and we prove that the growth constants are nondecreasing in $m$, strictly smaller than the Catalan growth constant $4$ for every finite $m$, and converge to $4$ as $m\to\infty$.

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 / 2 minor

Summary. The manuscript introduces a two-sided endpoint-state decomposition for the class of 132-avoiding permutations with the adjacency constraint |π_{i+1}−π_i|≤m. States track threshold bounds (in {0,1,…,m−1,∞}) on the deficiencies n−π_1 and n−π_n, producing at most (m+1)^2 states. The construction is used to prove that the ordinary generating function A^{(m)}(x) is rational for each fixed m and can be obtained by exact linear algebra on the transition matrix. The paper recovers the known m=2 generating function, computes the m=3 case explicitly, extracts eventual linear recurrences from the cyclic strongly connected components of the state graph, and establishes that the exponential growth constants exist, are strictly less than 4, are nondecreasing in m, and converge to 4 as m→∞, with simple-pole asymptotics given for m=2 and m=3.

Significance. If the state decomposition is faithful, the work supplies a uniform, effective procedure that yields rational generating functions, explicit recurrences, and precise asymptotics for every fixed m. The finite-state construction, the explicit recovery of the m=2 case, the m=3 computation, the spectral-radius analysis of the two nontrivial cyclic components, and the proof that the growth constants approach the Catalan constant 4 are concrete advances in the enumeration of pattern-avoiding permutations under local constraints.

minor comments (2)
  1. [Abstract / §3] The abstract states that the state system yields 'at most (m+1)^2 states'; a brief remark in §3 or §4 confirming that all threshold pairs are reachable (or identifying any unreachable pairs) would make the bound fully explicit.
  2. [§5] The dependency graph and its cyclic strongly connected components are central to the recurrence-order bound; a small diagram or adjacency-matrix excerpt for the m=3 case would improve readability of the growth-rate argument.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of the manuscript and for the recommendation to accept.

Circularity Check

0 steps flagged

Direct combinatorial finite-state construction; no circularity

full rationale

The derivation rests on an explicit two-sided endpoint-state decomposition whose states are defined directly from threshold bounds on the endpoint deficiencies n-π1 and n-πn. The finite number of states (at most (m+1)^2) immediately yields a transition matrix whose powers enumerate the objects; rationality of the OGF is the standard consequence of a finite automaton and does not reduce to any fitted parameter or prior result by construction. Recovery of the m=2 case and explicit computation for m=3 are consistency verifications, not load-bearing inputs. No self-citation is invoked to justify the state set or the avoidance property, and the growth-rate analysis follows from the spectral radii of the explicitly constructed dependency graph. The argument is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The approach relies on standard combinatorial constructions without introducing new entities or fitted parameters.

axioms (2)
  • standard math Standard properties of 132 pattern avoidance and permutations hold.
    The enumeration is built on the established definition of pattern avoidance.
  • domain assumption The adjacency constraint can be tracked via endpoint deficiencies with the given thresholds.
    This is the core modeling choice enabling the finite-state system.

pith-pipeline@v0.9.0 · 5929 in / 1448 out tokens · 33037 ms · 2026-05-25T04:00:35.116407+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

14 extracted references · 14 canonical work pages · 1 internal anchor

  1. [1]

    Albert, Steve Linton, and Nik Ruˇ skuc

    Michael H. Albert, Steve Linton, and Nik Ruˇ skuc. The insertion encoding of permutations. Electronic Journal of Combinatorics, 12(1):Research Paper 47, 2005

    work page 2005

  2. [2]

    On uniquelyk-determined permutations.Discrete Mathematics, 308(9):1500–1507, 2008

    Sergey Avgustinovich and Sergey Kitaev. On uniquelyk-determined permutations.Discrete Mathematics, 308(9):1500–1507, 2008

    work page 2008

  3. [3]

    CRC Press, Boca Raton, 2 edition, 2012

    Mikl´ os B´ ona.Combinatorics of Permutations. CRC Press, Boca Raton, 2 edition, 2012

    work page 2012

  4. [4]

    Surprising symmetries in objects counted by Catalan numbers.Electronic Journal of Combinatorics, 19(1):P62, 2012

    Mikl´ os B´ ona. Surprising symmetries in objects counted by Catalan numbers.Electronic Journal of Combinatorics, 19(1):P62, 2012

    work page 2012

  5. [5]

    Permutation pattern avoidance and the Catalan triangle.Missouri Journal of Math- ematical Sciences, 25(1):50–60, 2013

    Derek DeSantis, Rebecca Field, Wesley Hough, Brant Jones, Rebecca Meissen, and Jacob Ziefle. Permutation pattern avoidance and the Catalan triangle.Missouri Journal of Math- ematical Sciences, 25(1):50–60, 2013

    work page 2013

  6. [6]

    Cambridge University Press, Cambridge, 2009

    Philippe Flajolet and Robert Sedgewick.Analytic Combinatorics. Cambridge University Press, Cambridge, 2009

    work page 2009

  7. [7]

    Gillespie, Kenneth G

    Maria M. Gillespie, Kenneth G. Monks, and Kenneth M. Monks. Enumerating anchored permutations with bounded gaps.Discrete Mathematics, 343(9):111957, 2020. 36

    work page 2020

  8. [8]

    Horn and Charles R

    Roger A. Horn and Charles R. Johnson.Matrix Analysis. Cambridge University Press, Cambridge, 2 edition, 2012

    work page 2012

  9. [9]

    Permutations with restricted patterns and Dyck paths.Advances in Applied Mathematics, 27:510–530, 2001

    Christian Krattenthaler. Permutations with restricted patterns and Dyck paths.Advances in Applied Mathematics, 27:510–530, 2001

    work page 2001

  10. [10]

    On 132-Avoiding Permutations with an Adjacency Constraint

    Nathaniel Nadler. On 132-avoiding permutations with an adjacency constraint, 2026. arXiv:2604.22135 [math.CO]

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  11. [11]

    Rodica Simion and Frank W. Schmidt. Restricted permutations.European Journal of Com- binatorics, 6(4):383–406, 1985

    work page 1985

  12. [12]

    Enumeration schemes for restricted permutations.Combinatorics, Probability and Computing, 17(1):137–159, 2008

    Vincent Vatter. Enumeration schemes for restricted permutations.Combinatorics, Probability and Computing, 17(1):137–159, 2008

    work page 2008

  13. [13]

    Permutation classes

    Vincent Vatter. Permutation classes. In Mikl´ os B´ ona, editor,Handbook of Enumerative Combinatorics, pages 754–833. CRC Press, Boca Raton, 2015

    work page 2015

  14. [14]

    Enumeration schemes and, more importantly, their automatic generation

    Doron Zeilberger. Enumeration schemes and, more importantly, their automatic generation. Annals of Combinatorics, 2:185–195, 1998. 37

    work page 1998