A327833 Number of non-overlapping pairs of adjacent runs in permutations of [n].

1, 1, 4, 18, 100, 665, 5124, 44772, 437016, 4710915, 55568480, 711802894, 9838192572, 145921265581, 2311617527660, 38950657146120, 695562375445104, 13121344429311687, 260728755911619336, 5443039353326333330, 119101575356825879860, 2725785134463572716689

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

Links

Table of n, a(n) for n=1..22.

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

Sequence in context: A371723 A215522 A201826 * A350267 A064852 A229286

Adjacent sequences: A327830 A327831 A327832 * A327834 A327835 A327836

Keyword

nonn

Author

David Bevan, Sep 27 2019

Status

approved