Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

A nonterminal prefix-only permutation

Abstract

Let p be a permutation of size n at least three in D whose proper nontrivial intervals are all prefixes and whose final entry is not the minimum. For some h at least one, either n = 2h and p = P(h), or n = 2h + 1 and p is the first-entry inflation of P(h) by 21.

Theorem 1.1 (A nonterminal prefix-only permutation).

Lean statement: D5/S3/Combinatorics/PopStack/PopStackPrefixShape.prefix_nonterminal

Proof. Machine-checked in Lean as D5/S3/Combinatorics/PopStack/PopStackPrefixShape.prefix_nonterminal (✓ std3). ∎

Source. Repository-derived.

Acknowledgement. Lapo Cioni, Luca Ferrari, Rebecca Smith (2025). Sorting permutations using a pop stack with a bypass. DOI: 10.1016/j.disc.2025.114964. URL: https://arxiv.org/abs/2503.08285v1.

Commentary.

Let p be a permutation of size n at least three in D whose proper nontrivial intervals are all prefixes and whose final entry is not the minimum. For some h at least one, either n = 2h and p = P(h), or n = 2h + 1 and p is the first-entry inflation of P(h) by 21.

References