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

Author

David Bevan, Sep 27 2019

Keywords

• nonn

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

Examples

			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.
		

Programs

Mathematica

Table[If[n==1,1,(n-1)n!-(n/3-1/2)Floor[E n!]+(n/6-1/2)],{n,20}]

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