Metraipolis › archive › dc_7f01fa7be2f2

123-Avoiding permutations with an adjacency constraint — arXiv:2610.02526

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.02526
License (as archived): CC0-1.0
Archived: 2026-10-06T08:24:40.013Z
SHA-256 of the archived text: 3149fca9296ec152ef47d595f314bf642c6aa243c34fee876b562d0b576830fc
Stable URL of this page: https://metraipolis.com/documento/dc_7f01fa7be2f2

How to cite

123-Avoiding permutations with an adjacency constraint — arXiv:2610.02526 — arXiv (en), https://arxiv.org/abs/2610.02526 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7f01fa7be2f2 (Metraipolis archive dc_7f01fa7be2f2, sha256 3149fca9296ec152ef47d595f314bf642c6aa243c34fee876b562d0b576830fc)

BibTeX

@misc{dc7f01fa7be2f2,
  title = {123-Avoiding permutations with an adjacency constraint — arXiv:2610.02526},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.02526},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7f01fa7be2f2; sha256 3149fca9296ec152ef47d595f314bf642c6aa243c34fee876b562d0b576830fc},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.02526. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study permutations $\pi \in S_n$ that avoid $123$ while satisfying the adjacency constraint $\lvert \pi_{i+1}-\pi_i\rvert \le m$ for some $m\in\mathbb{Z}^{+}$. 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 $\rho_m$ of the corresponding transfer matrix and show that $\rho_m<4$, is nondecreasing in $m$, and converges to the Catalan growth constant $4$ as $m\to\infty$. 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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-05 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.02526 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T08:18:48.286Z dalla pagina https://arxiv.org/catchup/math.CO/2026-10-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).