Skip to content
Preprint

Unranking $S$-avoiding permutations with two forbidden offsets

Oct 2026 · 0 citations · 7 references
Mathematics Computer Science

Abstract

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\'enage number for odd $n$ and exceeds it by $2$ for even $n$, proving a conjecture recorded in the OEIS entry A354152.

View source

Similar papers

Preprint Oct 2026

Enumeration Complexity of Permutation Classes

We study classes of permutations that are defined by avoidance of forbidden patterns. For each fixed finite set $B$ of forbidden patterns, we study the \emph{avoider enumeration problem}: given an integer $n$, output all $B$-avoiding permutations of length $n$. Avoider enumeration is output-polynomial for every fixed $...

M. Bodirsky, M. Elsheikh · 0 citations
Preprint Nov 2026

The isolation number of uniform hypertrees

An isolating set of a hypergraph $H$ is a vertex set whose closed neighbourhood intersects every edge of $H$. The isolation number $\iota(H)$ is the minimum cardinality of such a set. Let $r\ge3$, and let $T$ be an $r$-uniform hypergraph whose incidence graph is a tree. We prove that, if $T$ has order $n$ and at least...

Min-Hui Li, Shu-Min Zhang, Jun-Hao Qu · 0 citations
Preprint Oct 2026

A uniform double-factorial construction for consecutive-pattern packings

For every overlap $m\geq 3$ and every pattern length $K\geq 2m+1$, we construct an explicit permutation $p\in\mathfrak{S}_K$ such that the number of permutations containing $j$ prescribed occurrences of $p$, with successive starts separated by $K-m$, is $(2j-1)!!$ for every $j\geq 1$. Additional occurrences are permitt...

Z. Nagy · 0 citations
Preprint Oct 2026

On a conjecture concerning two-stack sortable permutations

The two-stack sortable permutations of length $n$ are known to be equinumerous with permutations of length $n$ avoiding the dashed patterns $3\text{-}1\text{-}4\text{-}2$ and $2\text{-}41\text{-}3$. In this paper, we confirm an intriguing conjecture posed by Claesson, Kitaev, and Steingr\'imsson, which asserts that the...

Yong-Zhou Wen, Sherry H. F. Yan · 0 citations
Preprint Nov 2026

Full-Cover and Non-Overlapping Uni-domination in Graphs: Bounds and Complexity

A vertex is uni-dominated by a set $S \subseteq V(G)$ if exactly one vertex of $S$ lies in its closed neighborhood, and the uni-domination number $\mathrm{ud}^*(G)$ is the largest number of vertices a single set can uni-dominate. The graphs admitting an efficient dominating set are those with $\mathrm{ud}^*(G) = n$. He...

F. Foucaud, Y. Gérard, C. Laforest et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.