|
|
A327833
|
|
Number of non-overlapping pairs of adjacent runs in permutations of [n].
|
|
0
|
|
|
1, 1, 4, 18, 100, 665, 5124, 44772, 437016, 4710915, 55568480, 711802894, 9838192572, 145921265581, 2311617527660, 38950657146120, 695562375445104, 13121344429311687, 260728755911619336, 5443039353326333330, 119101575356825879860, 2725785134463572716689
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|