123-Avoiding permutations with an adjacency constraint
Abstract
We study permutations π∈ Sn that avoid $123$ while satisfying the adjacency constraint lvert πi+1−πirvert ≤ m for some m∈ℤ+. We first show that every admissible permutation is localized within vertical distance m of the reverse diagonal, revealing a strong global restriction imposed by the interaction between pattern avoidance and bounded adjacency. For every fixed m, we then construct an exact finite-state description of the family, with precisely 2m+1−m−1 realizable states. This yields an explicit transfer-matrix enumeration and, in particular, a rational generating function for every fixed m; consequently, the enumeration sequence satisfies an eventual constant-coefficient linear recurrence. We further identify the exponential growth rate with the spectral radius ρm of the corresponding transfer matrix and show that ρm<4, is nondecreasing in m, and converges to the Catalan growth constant $4$ as m→∞. Finally, we show that the bounded-adjacency constraint breaks the ordinary length-three Wilf equivalence, and we develop algorithmic and graph-theoretic interpretations of the family, including a correspondence with constrained Hamiltonian paths in powers of the path graph.
Related
- Constructing Cospectral Hypergraphs Using Adjacency Preserving Permutations
- Inversion-descent enumerators of underline321-avoiding permutations
- Avoiding patterns with three distinct letters in Canon permutations
- Descent Tops and Pinnacles on 2143- and 3421-Avoiding Permutations
- Shuffle automata and the growth of 1324-avoiding permutations
BibTeX
@misc{nadler2026123avoiding,
title = {{123-Avoiding permutations with an adjacency constraint}},
author = {Nathaniel Nadler},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02526},
eprint = {2610.02526},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02526},
}
RIS
TY - UNPB
TI - 123-Avoiding permutations with an adjacency constraint
AU - Nathaniel Nadler
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02526
UR - https://arxiv.org/abs/2610.02526
AB - We study permutations π∈ S_n that avoid $123$ while satisfying the adjacency constraint lvert π_i+1−π_irvert ≤ m for some m∈ℤ^+. We first show that every admissible permutation is localized within vertical distance m of the reverse diagonal, revealing a strong global restriction imposed by the interaction between pattern avoidance and bounded adjacency. For every fixed m, we then construct an exact finite-state description of the family, with precisely 2^m+1−m−1 realizable states. This yields an explicit transfer-matrix enumeration and, in particular, a rational generating function for every fixed m; consequently, the enumeration sequence satisfies an eventual constant-coefficient linear recurrence. We further identify the exponential growth rate with the spectral radius ρ_m of the corresponding transfer matrix and show that ρ_m<4, is nondecreasing in m, and converges to the Catalan growth constant $4$ as m→∞. Finally, we show that the bounded-adjacency constraint breaks the ordinary length-three Wilf equivalence, and we develop algorithmic and graph-theoretic interpretations of the family, including a correspondence with constrained Hamiltonian paths in powers of the path graph.
ER -