A389255 Triangle read by rows: T(n,k) = number of heapable permutations of length n with exactly k decreasing runs.

1, 0, 1, 0, 1, 1, 0, 0, 4, 1, 0, 0, 5, 11, 1, 0, 0, 3, 41, 26, 1, 0, 0, 3, 86, 212, 57, 1, 0, 0, 0, 151, 964, 890, 120, 1, 0, 0, 0, 237, 3267, 7416, 3327, 247, 1, 0, 0, 0, 284, 9585, 43501, 46465, 11583, 502, 1, 0, 0, 0, 387, 24780, 209088, 436600, 256330, 38510, 1013, 1

Offset

1,9

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 decreasing run in a permutation is a maximal contiguous subsequence that is strictly decreasing. For example, in the permutation (3,1,4,2) the decreasing runs are (3,1) and (4,2).

Links

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

Manolopoulos Panagiotis, Python program.

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.

Formula

A389232(n) = Sum_{k..n} k*T(n,k).

Example

Triangle begins:
  1;
  0, 1;
  0, 1, 1;
  0, 0, 4,   1;
  0, 0, 5,  11,    1;
  0, 0, 3,  41,   26,     1;
  0, 0, 3,  86,  212,    57,     1;
  0, 0, 0, 151,  964,   890,   120,     1;
  0, 0, 0, 237, 3267,  7416,  3327,   247,   1;
  0, 0, 0, 284, 9585, 43501, 46465, 11583, 502, 1;
  ...

Crossrefs

Cf. A336282 (row sums).

Cf. A389232 (total number of decreasing runs in heapable permutations).

Sequence in context: A126217 A334702 A345300 * A085992 A117411 A161739

Adjacent sequences: A389252 A389253 A389254 * A389256 A389257 A389258

Keyword

nonn,tabl

Author

Manolopoulos Panagiotis, Sep 27 2025

Extensions

More terms from Sean A. Irvine, Oct 06 2025

Status

approved