A389792 Total number of ascents in all heapable permutations of length n.

0, 1, 3, 11, 47, 238, 1403, 9486, 72558, 620593, 5876838, 61097194, 692282393, 8495691645, 112301871248, 1591322008894

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.

An ascent in a permutation p is an index i with 1<=i<=n-1 such that p(i)<p(i+1).

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

Formula

a(n) = Sum_{k=1..n-1} k*A389255(n,k+1).

Example

For n=4, the heapable permutations are:
  (1,2,3,4): ascents at positions (1,2),(2,3),(3,4)  3 ascents.
  (1,3,2,4): ascents at (1,3),(2,4)  2 ascents.
  (1,2,4,3): ascents at (1,2),(2,4)  2 ascents.
  (1,4,2,3): ascents at (1,4),(2,3)  2 ascents.
  (1,3,4,2): ascents at (1,3),(3,4)  2 ascents.
So the total number of ascents across all 5 heapable permutations of length 4 is: 3+2+2+2+2 = 11.

Crossrefs

Cf. A336282, A386382, A389232, A389255, A389991.

Sequence in context: A051296 A030832 A030865 * A030902 A030925 A020543

Adjacent sequences: A389789 A389790 A389791 * A389793 A389794 A389795

Keyword

nonn,more

Author

Manolopoulos Panagiotis, Oct 15 2025

Extensions

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

Status

approved