OFFSET
1,3
COMMENTS
A run is a maximal consecutive subsequence of increasing values; two adjacent runs are non-overlapping if the least value in the first run exceeds the greatest value in the second.
Permutations all of whose adjacent runs overlap are in the image of the pop-stack sorting operation (see A307030 and references).
FORMULA
a(n) = (n-1)*n! - (n/3-1/2)*floor(e*n!) + (n/6-1/2), for all n > 1.
Asymptotically, the expected number of non-overlapping adjacent pairs of runs an n-permutation is (1-e/3)*n + (e/2-1).
EXAMPLE
a(3) = 4: one non-overlapping pair of adjacent runs in both 231 and 312, and two non-overlapping pairs in 321; the pairs of adjacent runs in 132 and 213 overlap.
MATHEMATICA
Table[If[n==1, 1, (n-1)n!-(n/3-1/2)Floor[E n!]+(n/6-1/2)], {n, 20}]
CROSSREFS
KEYWORD
nonn
AUTHOR
David Bevan, Sep 27 2019
STATUS
approved
