A389496 Triangle T(n,k) read by rows: T(n,k) is the number of heapable permutations of length n whose major index is k.

1, 1, 0, 1, 0, 1, 0, 1, 0, 2, 2, 0, 0, 0, 1, 0, 3, 5, 3, 0, 3, 2, 0, 0, 0, 1, 0, 4, 9, 9, 4, 8, 15, 13, 5, 0, 3, 0, 0, 0, 0, 1, 0, 5, 14, 19, 14, 20, 41, 61, 55, 31, 20, 22, 29, 19, 5, 0, 3, 0, 0, 0, 0, 1, 0, 6, 20, 34, 34, 44, 90, 164, 213, 199, 159, 140, 190, 236, 221, 146, 78, 50, 41, 41, 19, 0, 0, 0, 0, 0, 0, 0

Offset

1,10

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 major index of a permutation p = (p1, p2, ..., pn) is the sum of the positions i (1 <= i <= n-1) where a descent occurs, that is, where pi > pi+1. Formally: maj(p) = Sum { i : pi > pi+1 }.

In other words, the major index is obtained by adding all indices i for which the element pi is greater than the next element pi+1.

Links

Sean A. Irvine, Table of n, a(n) for n = 1..575 (rows 1..15 flattened, rows 1..10 from Manolopoulos Panagiotis)

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, 0;
  1, 0, 1, 0;
  1, 0, 2, 2, 0, 0, 0;
  1, 0, 3, 5, 3, 0, 3, 2, 0, 0, 0;
  1, 0, 4, 9, 9, 4, 8, 15, 13, 5, 0, 3, 0, 0, 0, 0;
  1, 0, 5, 14, 19, 14, 20, 41, 61, 55, 31, 20, 22, 29, 19, 5, 0, 3, 0, 0, 0, 0;
  ..

Crossrefs

Cf. A336282 (number of heapable permutations of length n), A386382 (total runs in heapable permutations), A388139 (total number of fixed points).

Sequence in context: A292946 A196078 A287086 * A180823 A049800 A281082

Adjacent sequences: A389493 A389494 A389495 * A389497 A389498 A389499

Keyword

nonn,tabf

Author

Manolopoulos Panagiotis, Oct 07 2025

Status

approved