cp's OEIS Frontend

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

%I A307030 #63 Nov 18 2021 11:27:57
%S A307030 1,1,3,11,49,263,1653,11877,95991,862047,8516221,91782159,1071601285,
%T A307030 13473914281,181517350571,2608383775171,39824825088809,
%U A307030 643813226048935,10986188094959045,197337931571468445,3721889002400665951,73539326922210382215,1519081379788242418149,32743555520207058219615,735189675389014372317381
%N A307030 Number of permutations of [n] with overlapping adjacent runs.
%C A307030 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.
%C A307030 a(n) is also the number of permutations of size n transformed by a pop-stack sorting (see Links below).
%H A307030 Bjarki Ágúst Guðmundsson, <a href="/A307030/b307030.txt">Table of n, a(n) for n = 1..450</a>
%H A307030 Andrei Asinowski, Cyril Banderier, Sara Billey, Benjamin Hackl and Svante Linusson, <a href="https://lipn.fr/~cb/Papers/popstack.pdf">Pop-stack sorting and its image: Permutations with overlapping runs</a> (2019), preprint.
%H A307030 Anders Claesson, Bjarki Ágúst Guðmundsson and Jay Pantone, <a href="https://arxiv.org/abs/1908.08910">Counting pop-stacked permutations in polynomial time</a>, arXiv:1908.08910 [math.CO], 2019.
%H A307030 Colin Defant and Nathan Williams, <a href="https://arxiv.org/abs/2111.08122">Semidistrim Lattices</a>, arXiv:2111.08122 [math.CO], 2021.
%e A307030 For n = 3 the a(3) = 3 permutations with overlapping runs are 123, 132, 213.
%Y A307030 Cf. A001855, A008292.
%Y A307030 Row sums of A309993.
%K A307030 nonn
%O A307030 1,3
%A A307030 _Cyril Banderier_, Mar 20 2019
%E A307030 Added more terms (from the Claesson/Guðmundsson/Pantone reference), _Joerg Arndt_, Aug 26 2019
%E A307030 Definition corrected by _Bjarki Ágúst Guðmundsson_, Aug 26 2019