Unranking S-avoiding permutations with two forbidden offsets

@misc{andre2026unranking,
  title = {{Unranking $S$-avoiding permutations with two forbidden offsets}},
  author = {Antônio Augusto André},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.23958},
  eprint = {2610.23958},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.23958},
}

TY  - UNPB
TI  - Unranking S-avoiding permutations with two forbidden offsets
AU  - Antônio Augusto André
PY  - 2026
DA  - 2026/10/09
PB  - arXiv
DO  - 10.48550/arxiv.2610.23958
UR  - https://arxiv.org/abs/2610.23958
AB  - Given a finite family of combinatorial objects with a total order, ranking asks for the position of a given object, and unranking asks for the object occupying a given position. Both provide algorithmic access to families too large to enumerate. Kagey gave a polynomial-time algorithm for several position-restricted families and left open the case of {−1,1}-avoiding permutations. We show that when |S| = 2, the graph of forbidden squares is $2$-regular, a disjoint union of cycles, and that fixing a prefix leaves only paths and untouched cycles. This yields polynomial-time prefix counting, ranking and unranking for every two-element set of offsets, covering {−1,1}. The same structure gives a short proof that the number of {−1,1}-avoiding permutations equals the n-th ménage number for odd n and exceeds it by $2$ for even n, proving a conjecture recorded in the OEIS entry A354152.
ER  -