A307030 Number of permutations of [n] with overlapping adjacent runs.

1, 1, 3, 11, 49, 263, 1653, 11877, 95991, 862047, 8516221, 91782159, 1071601285, 13473914281, 181517350571, 2608383775171, 39824825088809, 643813226048935, 10986188094959045, 197337931571468445, 3721889002400665951, 73539326922210382215, 1519081379788242418149, 32743555520207058219615, 735189675389014372317381

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

Cf. A001855, A008292.

Row sums of A309993.

Sequence in context: A357836 A356291 A001339 * A335788 A012316 A261600

Adjacent sequences: A307027 A307028 A307029 * A307031 A307032 A307033

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