OFFSET
1,3
COMMENTS
The one-line notation of any permutation p has a unique factorization into runs p = B1,B2,...,Bk, where each Bi is a run (a sequence of increasing values), and the first element of B(i+1) is smaller than the last element of Bi. If the permutation p is such that each pair of adjacent runs Bi, B(i+1) have an overlapping range, that is the intervals [min(Bi),max(Bi)] and [min(B(i+1)),max(B(i+1))] have a nonempty intersection, then we say that p has overlapping runs.
a(n) is also the number of permutations of size n transformed by a pop-stack sorting (see Links below).
LINKS
Bjarki Ágúst Guðmundsson, Table of n, a(n) for n = 1..450
Andrei Asinowski, Cyril Banderier, Sara Billey, Benjamin Hackl and Svante Linusson, Pop-stack sorting and its image: Permutations with overlapping runs (2019), preprint.
Anders Claesson, Bjarki Ágúst Guðmundsson and Jay Pantone, Counting pop-stacked permutations in polynomial time, arXiv:1908.08910 [math.CO], 2019.
Colin Defant and Nathan Williams, Semidistrim Lattices, arXiv:2111.08122 [math.CO], 2021.
EXAMPLE
For n = 3 the a(3) = 3 permutations with overlapping runs are 123, 132, 213.
CROSSREFS
KEYWORD
nonn
AUTHOR
Cyril Banderier, Mar 20 2019
EXTENSIONS
Added more terms (from the Claesson/Guðmundsson/Pantone reference), Joerg Arndt, Aug 26 2019
Definition corrected by Bjarki Ágúst Guðmundsson, Aug 26 2019
STATUS
approved