A390368 Triangle read by rows: number of permutations of length n that require exactly k removals from the beginning to become heapable.

1, 1, 1, 2, 2, 2, 5, 6, 6, 7, 17, 20, 24, 27, 32, 71, 85, 100, 132, 151, 181, 359, 426, 510, 650, 872, 1009, 1214, 2126, 2513, 2982, 3825, 4950, 6714, 7801, 9409, 14495, 17008, 20104, 25347, 32980, 43125, 58740, 68431, 82650, 111921, 130455, 153072, 190988

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.

For a permutation p=(p(1),...,p(n)), define m(p) = the minimum number of initial elements that must be removed so that the truncated permutation is heapable.

This sequence gives the distribution of m(p) over all n! permutations of length n.

Links

Sean A. Irvine, Table of n, a(n) for n = 1..78 (rows 1..12 flattened)

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

Triangle begins:
  1
  1, 1
  2, 2, 2
  5, 6, 6, 7
  17, 20, 24, 27, 32
  71, 85, 100, 132, 151, 181
  359, 426, 510, 650, 872, 1009, 1214
  2126, 2513, 2982, 3825, 4950, 6714, 7801, 9409

Crossrefs

Cf. A336282 (number of heapable permutations), A389282 (sum of longest decreasing runs), A390146 (triangle of longest decreasing runs), A389993 (triangle of consecutive pairs).

Sequence in context: A136347 A279515 A260338 * A023569 A263373 A145876

Adjacent sequences: A390365 A390366 A390367 * A390369 A390370 A390371

Keyword

nonn,tabl

Author

Manolopoulos Panagiotis, Nov 03 2025

Extensions

More terms from Sean A. Irvine, Nov 09 2025

Status

approved