On 132-Avoiding Permutations with an Adjacency Constraint
Pith reviewed 2026-05-08 11:20 UTC · model grok-4.3
The pith
Adjacency bounds on 132-avoiding permutations restrict the largest entry to the first m positions or the last one.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that the adjacency condition forces the largest element n to occupy only positions in {1, 2, …, m} ∪ {n}. For m=2 this position restriction partitions the class into a small number of families, each satisfying a linear recurrence. The system of recurrences admits a rational generating function whose dominant pole determines the exact exponential growth rate α ≈ 1.4656 for the sequence A_n^{(2)}.
What carries the argument
The position restriction on the maximum element n, which collapses the possible arrangements and permits a complete case-by-case recursive decomposition of every permitted permutation.
If this is right
- The count A_n^{(2)} obeys a linear recurrence with constant coefficients for all n.
- The ordinary generating function for A_n^{(2)} is rational.
- The sequence grows asymptotically as C α^n where α is the reciprocal of the dominant pole and equals approximately 1.4656.
- For each fixed m the same structural collapse is expected to produce linear recurrences and rational generating functions.
Where Pith is reading between the lines
- The same position restriction on the largest entry may apply when the adjacency bound is paired with other classical patterns such as 123 or 231.
- The growth constants for successive m should form an increasing sequence that approaches the Catalan growth rate 4.
- Under a suitable encoding of the permutations the adjacency condition turns the 132-avoiding class into a regular language recognizable by a finite automaton.
Load-bearing premise
The adjacency bound truly confines every permitted permutation to those positions for n, and the resulting cases cover the entire class without gaps or overlaps.
What would settle it
The discovery of even one 132-avoiding permutation with consecutive differences at most 2 in which n occupies position 3 would refute the claimed position restriction.
read the original abstract
We study permutations in $S_n$ that simultaneously avoid the pattern $132$ and satisfy the adjacency bound $|\pi_{i+1} - \pi_i| \leq m$ for all $i$, denoting their number by $A_n^{(m)}$. This combination of a global pattern restriction and a local bounded-difference condition produces a strong structural collapse: whereas unrestricted $132$-avoiding permutations are counted by the Catalan numbers with exponential growth rate $4$, the adjacency constraint forces the maximum element $n$ to occupy only positions in $\{1, 2, \ldots, m\} \cup \{n\}$. We give a complete solution for $m = 2$ by partitioning the class according to the position of the maximum element. This yields explicit recurrences and a rational generating function, from which we derive asymptotic growth of the form $A_n^{(2)} \sim C \alpha^n$ with $\alpha \approx 1.4656$. We conjecture that for each fixed $m$, the class admits a finite-state structural decomposition leading to linear recurrences with constant coefficients and rational generating functions, with growth constants increasing to $4$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript studies permutations in S_n that avoid the pattern 132 while satisfying the local adjacency constraint |π_{i+1} - π_i| ≤ m for all i, with A_n^{(m)} denoting their number. It shows that this combination forces the maximum element n to lie only in positions {1, …, m} ∪ {n}. For the case m=2 the authors partition the class according to the position of n, obtain explicit recurrences for the resulting auxiliary sequences, derive a rational generating function, and extract the asymptotic A_n^{(2)} ∼ C α^n with α ≈ 1.4656. They conjecture that for each fixed m the class admits a finite-state decomposition yielding linear recurrences and rational generating functions whose growth constants increase to 4.
Significance. If the derivation is correct, the work supplies a concrete, fully explicit enumeration for a hybrid pattern-avoidance class whose growth rate is markedly smaller than the Catalan growth rate 4. The position-based case analysis produces a rational generating function, which is a verifiable combinatorial strength, and the conjecture points to a possible general structural theory for adjacency-constrained 132-avoiders.
minor comments (3)
- [The section deriving the recurrences for m=2] The explicit system of recurrences obtained from the three admissible positions of n should be displayed as numbered equations or in a compact table so that the linear recurrence for A_n^{(2)} and the characteristic equation for α can be read off directly.
- [The asymptotic analysis paragraph] The approximate constant α ≈ 1.4656 should be accompanied by either its minimal polynomial or at least five decimal places obtained from the dominant root of the characteristic equation.
- [The partitioning argument] A brief verification that the three position cases are exhaustive and disjoint (including the base cases n=1,2) would strengthen the claim that the recurrences count exactly A_n^{(2)}.
Simulated Author's Rebuttal
We thank the referee for the positive assessment and recommendation of minor revision. The report correctly summarizes the structural collapse on the position of n, the explicit solution for m=2, and the conjecture for general m. No specific major comments appear under the MAJOR COMMENTS heading, so there are no individual points requiring rebuttal or targeted revision.
Circularity Check
No significant circularity; derivation is self-contained combinatorial enumeration
full rationale
The paper first establishes the admissible positions for the maximum element n by combining the standard left/right decomposition of 132-avoiding permutations (left block is an interval of largest values, right block the smallest) with the local adjacency bound |π_{i+1}-π_i|≤m; when 1<k<n the right-maximum would violate the bound, forcing n into {1..m}∪{n}. For m=2 this yields three cases. The paper then defines auxiliary counting sequences for each case (permutations whose maximum is forced to the first or last position, etc.) and writes the junction conditions as linear recurrences relating these sequences to A_n^{(2)}. The system is closed, finite-state, and solved directly for a rational generating function and the growth constant α≈1.4656. No parameter is fitted to data, no quantity is defined in terms of itself, no self-citation supplies a load-bearing uniqueness theorem, and the recurrences are not obtained by renaming a known result. The entire chain is therefore an independent structural argument.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math A permutation is a bijection from [n] to [n].
- standard math A permutation avoids 132 if it contains no subsequence order-isomorphic to 132.
Forward citations
Cited by 1 Pith paper
-
Finite-state enumeration of adjacency-constrained 132-avoiding permutations
Develops a finite-state decomposition to prove that the generating function for adjacency-constrained 132-avoiding permutations is rational for each fixed m and analyzes its asymptotics.
Reference graph
Works this paper leans on
-
[1]
Michael H. Albert and M. D. Atkinson. Simple permutations and pattern restricted permutations.Discrete Mathematics, 300(1–3):1–15, 2005
work page 2005
-
[2]
Mikl´ os B´ ona.Combinatorics of Permutations. CRC Press, 2 edition, 2012
work page 2012
-
[3]
Fan Chung, Anders Claesson, Mark Dukes, and Ronald L. Graham. De- scent polynomials for permutations with bounded drop size.European Journal of Combinatorics, 31(7):1853–1867, 2010
work page 2010
-
[4]
Rodica Simion and Frank W. Schmidt. Restricted permutations.Euro- pean Journal of Combinatorics, 6(4):383–406, 1985
work page 1985
-
[5]
Richard P. Stanley.Catalan Numbers. Cambridge University Press, 2015
work page 2015
-
[6]
Vincent Vatter. Permutation classes. In Mikl´ os B´ ona, editor,Handbook of Enumerative Combinatorics, pages 753–833. CRC Press, 2015. 27
work page 2015
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.