A390273 Total sum of the heights of the trees associated with all heapable permutations of length n.

1, 2, 5, 16, 61, 285, 1575, 9998, 72238, 588204, 5323411, 53023072, 576878913, 6814288143, 86908145888

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 height of a binary tree is the maximum length of a path from the root to a leaf.

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), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3).
Their tree heights are 4, 3, 3, 3, 3, respectively.
Thus the total sum of heights is 16.

Crossrefs

Cf. A336282, A389282, A390146, A389993.

Sequence in context: A007976 A058259 A361920 * A368318 A391523 A369400

Adjacent sequences: A390270 A390271 A390272 * A390274 A390275 A390276

Keyword

nonn,more

Author

Manolopoulos Panagiotis, Oct 31 2025

Extensions

a(11)-a(15) from Sean A. Irvine, Nov 05 2025

Status

approved