A389488 Total sum of the lengths of the first runs in heapable permutations of length n.

1, 2, 5, 14, 50, 215, 1109, 6671, 46073, 359674, 3136435, 30242591, 319737694, 3679836643, 45817548623, 613853225509

Offset

1,2

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.

The first run (or initial increasing segment) of a permutation is the maximal prefix that is strictly increasing: p1 < p2 < ... < pk.

The length of the first run is k.

Links

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

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), (1,3,2,4), (1,2,4,3), (1,4,2,3), (1,3,4,2).
Lengths of first runs:
  (1,2,3,4): run 1,2,3,4 length 4.
  (1,3,2,4): run 1,3 length 2.
  (1,2,4,3): run 1,2,4 length 3.
  (1,4,2,3): run 1,4 length 2.
  (1,3,4,2): run 1,3,4 length 3.
So among the 5 heapable permutations of length 4:
  1 permutation has first run of length 4,
  2 permutations have first run of length 3,
  2 permutations have first run of length 2,
for a total of 14.

Crossrefs

Cf. A336282 (number of heapable permutations of length n), A386382 (total number of runs in heapable permutations).

Sequence in context: A022562 A341360 A320954 * A322725 A339832 A245883

Adjacent sequences: A389485 A389486 A389487 * A389489 A389490 A389491

Keyword

nonn,more

Author

Manolopoulos Panagiotis, Oct 06 2025

Extensions

a(12)-a(15) from Sean A. Irvine, Oct 12 2025

a(16) from Sean A. Irvine, Oct 13 2025

Status

approved