A388138 Total number of inversions in all heapable permutations of length n.

0, 0, 1, 6, 40, 275, 2093, 17450, 159847, 1599562, 17408959, 205030403, 2600927708, 35384797064, 514235496879, 7954125038292

Offset

1,4

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.

An inversion in a permutation p of length n is a pair of indices (i,j) with i<j such that p(i)>p(j).

The total number of inversions is the number of such pairs.

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 (2023), 126-137.

Manolopoulos Panagiotis, Python program

Example

For n=4, the heapable permutations are:
  (1,2,3,4): no inversions  0.
  (1,3,2,4): pair (2,3)  1 inversion.
  (1,2,4,3): pair (3,4)  1 inversion.
  (1,4,2,3): pairs (2,3),(2,4)  2 inversions.
  (1,3,4,2): pairs (2,4),(3,4)  2 inversions.
So the total number of inversions across all 5 heapable permutations of length 4 is: 0+1+1+2+2=6.

Crossrefs

Cf. A336282 (number of heapable permutations of length n), A387977 (triangle of inversions), A387955 (sum of major indices).

Sequence in context: A123357 A081016 A390456 * A083426 A122471 A178397

Adjacent sequences: A388135 A388136 A388137 * A388139 A388140 A388141

Keyword

nonn,more

Author

Manolopoulos Panagiotis, Oct 14 2025

Extensions

a(11)-a(16) from Sean A. Irvine, Oct 21 2025

Status

approved