OFFSET
1,8
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 increasing run in a permutation is a maximal contiguous subsequence that is increasing.
For example, in the permutation (3,1,4,2) the increasing runs are (3), (1,4), and (2).
LINKS
Sean A. Irvine, Table of n, a(n) for n = 1..120 (rows 1..15 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 file
FORMULA
A389256(n) = Sum_{k..n} k*T(n,k).
EXAMPLE
Triangle begins:
1;
1, 0;
1, 1, 0;
1, 4, 0, 0;
1, 11, 5, 0, 0;
1, 26, 41, 3, 0, 0;
1, 57, 212, 86, 3, 0, 0;
1, 120, 890, 964, 151, 0, 0, 0;
1, 247, 3327, 7416, 3267, 237, 0, 0, 0;
1, 502, 11583, 46465, 43501, 9585, 284, 0, 0, 0;
...
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Manolopoulos Panagiotis, Oct 06 2025
EXTENSIONS
More terms from Sean A. Irvine, Oct 12 2025
STATUS
approved
