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

1, 1, 1, 2, 5, 14, 3, 42, 18, 11, 132, 82, 84, 27, 22, 11, 1, 429, 339, 456, 256, 243, 143, 124, 61, 43, 28, 4, 1430, 1341, 2158, 1638, 1766, 1227, 1321, 931, 749, 610, 466, 295, 198, 166, 131, 28, 21, 15, 4, 4862, 5187, 9511, 8837, 10588, 8516, 9954, 8164

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

Links

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

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
    5
   14,   3
   42,  18,  11
  132,  82,  84,  27,  22,  11,   1
  429, 339, 456, 256, 243, 143, 124, 61, 43, 28, 4

Crossrefs

Cf. A336282 (heapable permutations), A391776 (triangle 231 patterns), A391697 (total 213 patterns), A391777 (total 231 patterns).

Sequence in context: A279176 A279876 A329494 * A016737 A279253 A279958

Adjacent sequences: A391968 A391969 A391970 * A391972 A391973 A391974

Keyword

nonn,tabf

Author

Manolopoulos Panagiotis, Dec 24 2025

Extensions

Offset corrected and more terms from Sean A. Irvine, Jan 26 2026

Status

approved