A389991 Total number of descents in all heapable permutations of length n.

0, 0, 1, 4, 21, 117, 751, 5396, 43402, 386696, 3790252, 40578094, 471609679, 5917541371, 79770698784, 1150250318291

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.

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

The number of descents is the count of such indices.

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*A389487(n,k+1).

Example

For n=4, the heapable permutations are:
  (1,2,3,4): no descents  0.
  (1,3,2,4): descent at (3,2)  1.
  (1,2,4,3): descent at (4,3)  1.
  (1,4,2,3): descent at (4,2)  1.
  (1,3,4,2): descent at (4,2)  1.
So the total number of descents across all 5 heapable permutations of length 4 is: 0+1+1+1+1=4.

Crossrefs

Cf. A336282, A386382, A389256, A389487, A389792.

Sequence in context: A212419 A020048 A318365 * A093426 A182435 A046090

Adjacent sequences: A389988 A389989 A389990 * A389992 A389993 A389994

Keyword

nonn,more

Author

Manolopoulos Panagiotis, Oct 21 2025

Extensions

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

Status

approved