The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A307030 Number of permutations of [n] with overlapping adjacent runs. 3
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 (list; graph; refs; listen; history; text; internal format)



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).


Bjarki Ágúst Guðmundsson, Table of n, a(n) for n = 1..450

Andrei Asinowski, Cyril Banderier, Sara Billey, Benjamin Hackl, Svante Linusson, Pop-stack sorting and its image: Permutations with overlapping runs (2019), preprint.

Anders Claesson, Bjarki Ágúst Guðmundsson, Jay Pantone, Counting pop-stacked permutations in polynomial time, arXiv:1908.08910 [math.CO], 2019.


For n = 3 the a(3) = 3 permutations with overlapping runs are 123, 132, 213.


Cf. A001855, A008292.

Row sums of A309993.

Sequence in context: A004211 A180869 A001339 * A012316 A261600 A193319

Adjacent sequences:  A307027 A307028 A307029 * A307031 A307032 A307033




Cyril Banderier, Mar 20 2019


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



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 19 09:35 EST 2020. Contains 331048 sequences. (Running on oeis4.)