A391508 Triangle read by rows: T(n,k) = number of heapable permutations of length n with exactly k 213 patterns.

1, 1, 1, 2, 4, 1, 10, 3, 4, 25, 12, 14, 10, 10, 69, 38, 59, 38, 63, 26, 40, 20, 6, 192, 133, 202, 179, 259, 175, 244, 183, 180, 122, 127, 68, 49, 9, 4, 562, 437, 743, 670, 1086, 798, 1273, 1047, 1133, 948, 1213, 871, 934, 665, 615, 528, 436, 223, 188, 66, 41, 14

Offset

0,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 213-pattern in a heapable permutation p=(p(1),p(2),...,p(n)) is a triad of indices x<y<z where p(x)<p(y)<p(z).

Links

Sean A. Irvine, Table of n, a(n) for n = 0..536

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

Sum_{k >= 0} k*T(n,k) = A391697(n).

Example

Triangle begins:
    1
    1
    1
    2
    4,   1
   10,   3,   4
   25,  12,  14,  10,  10
   69,  38,  59,  38,  63,  26,  40,  20,   6
  192, 133, 202, 179, 259, 175, 244, 183, 180, 122, 127, 68, 49, 9, 4

Crossrefs

Cf. A336282 (row sums), A387705 (triangle of 132 patterns), A390832 (triangle of 123 patterns), A391697.

Sequence in context: A208936 A373756 A102405 * A363575 A271206 A391776

Adjacent sequences: A391505 A391506 A391507 * A391509 A391510 A391511

Keyword

nonn,tabf

Author

Manolopoulos Panagiotis, Dec 11 2025

Extensions

More terms from Sean A. Irvine, Dec 17 2025

Status

approved