Protected tails and polynomial-time enumeration of permutations avoiding a direct sum of an increasing pattern and 231
Abstract
We give an algorithm counting the permutations that avoid a fixed pattern of the following form: the direct sum of an increasing pattern and 231. The first members of the family are 1342 and 12453. For each member the algorithm uses polynomially many operations and stored integers, with degrees that grow linearly in the length of the pattern. It comes from a recurrence that reads a permutation from left to right and records the constraints that the letters read so far impose on those still unread. This recurrence has exponentially many states, but part of each state is protected: later steps carry it along unchanged and do not depend on it, and factoring the protected part out leaves a dynamic program of polynomial size. For 12453 a translation symmetry sharpens the bounds to degree seven for the operations and degree four for the storage. We also compute the number of 12453-avoiding permutations of every length up to 150. The previously published series, due to Biers-Ariel (2019), reached length 38. We also give a sampler of uniformly random avoiders. A floating-point implementation of it, proved to be within total variation distance 3.5·10−5 of uniform for ideal random bits, draws the one million 12453-avoiding permutations of length 300 shown in a heatmap. The literal and kernel recurrences for 1342 and 12453 are verified in the Lean 4 proof assistant.
Related
- 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
- The Distribution of Double Deficiencies in Pattern-Avoiding Permutations
BibTeX
@misc{ulfarsson2026protected,
title = {{Protected tails and polynomial-time enumeration of permutations avoiding a direct sum of an increasing pattern and 231}},
author = {Henning Arnór Skeggi Úlfarsson},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.15642},
eprint = {2609.15642},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15642},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Protected tails and polynomial-time enumeration of permutations avoiding a direct sum of an increasing pattern and 231
AU - Henning Arnór Skeggi Úlfarsson
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2609.15642
UR - https://arxiv.org/abs/2609.15642
AB - We give an algorithm counting the permutations that avoid a fixed pattern of the following form: the direct sum of an increasing pattern and 231. The first members of the family are 1342 and 12453. For each member the algorithm uses polynomially many operations and stored integers, with degrees that grow linearly in the length of the pattern. It comes from a recurrence that reads a permutation from left to right and records the constraints that the letters read so far impose on those still unread. This recurrence has exponentially many states, but part of each state is protected: later steps carry it along unchanged and do not depend on it, and factoring the protected part out leaves a dynamic program of polynomial size. For 12453 a translation symmetry sharpens the bounds to degree seven for the operations and degree four for the storage. We also compute the number of 12453-avoiding permutations of every length up to 150. The previously published series, due to Biers-Ariel (2019), reached length 38. We also give a sampler of uniformly random avoiders. A floating-point implementation of it, proved to be within total variation distance 3.5·10^−5 of uniform for ideal random bits, draws the one million 12453-avoiding permutations of length 300 shown in a heatmap. The literal and kernel recurrences for 1342 and 12453 are verified in the Lean 4 proof assistant.
ER -