A386382 Total number of runs in all heapable permutations of length n.

1, 1, 3, 11, 47, 242, 1447, 9930, 76964, 666339, 6379657, 66988527, 765926227, 9477113482, 126219959400

Offset

1,3

Comments

A permutation of [1..n] is heapable if it can be inserted, one element at a time, into a binary min-heap without violating the heap property.

A run in a permutation is a maximal contiguous subsequence that is either strictly increasing or strictly decreasing. For example, the permutation (1,3,2,4) has runs (1,3), (3,2), (2,4), hence 3 runs.

This sequence counts the total number of runs over all heapable permutations of length n.

Links

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

Benjamin Chen, Michael Cho, Mario Tutuncu-Macias, and Tony Tzolov, Efficient methods of calculating the number of heapable permutations, Discrete Applied Mathematics Volume 331, 31 May 2023, Pages 126-137.

Manolopoulos Panagiotis, Python Program

Example

For n=4, the heapable permutations are:
  (1,2,3,4): always increasing => 1 run.
  (1,3,2,4): 1->3 (up), 3->2 (down), 2->4 (up) => 3 runs.
  (1,2,4,3): 1->2 (up), 2->4 (up), 4->3 (down) => 2 runs.
  (1,4,2,3): 1->4 (up), 4->2 (down), 2->3 (up) => 3 runs.
  (1,3,4,2): 1->3 (up), 3->4 (up), 4->2 (down) => 2 runs.
So among the 5 heapable permutations of length 4:
  1 permutation has 1 run,
  2 permutations have 2 runs,
  2 permutations have 3 runs,
for a total of 11 runs.

Crossrefs

Cf. A336282 (number of heapable permutations), A388139 (total number fixed points), A388136 (total number of cycles).

Sequence in context: A020543 A111139 A167564 * A386239 A381121 A295833

Adjacent sequences: A386379 A386380 A386381 * A386383 A386384 A386385

Keyword

nonn,more

Author

Manolopoulos Panagiotis, Sep 16 2025

Extensions

a(11)-a(15) from Sean A. Irvine, Sep 26 2025

Status

approved