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

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 3, 3, 6, 2, 1, 1, 1, 3, 3, 9, 3, 18, 12, 10, 7, 4, 1, 1, 3, 3, 9, 6, 19, 17, 29, 30, 54, 40, 47, 28, 41, 14, 8, 7, 1, 1, 1, 1, 3, 3, 9, 6, 22, 18, 34, 35, 85, 49, 113, 108, 177, 165, 198, 189, 195, 168, 175, 111, 108, 57, 34, 44, 10

Offset

0,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.

A 132-pattern in a heapable permutation p=(p1,p2..pn) is a triad of indices i<j<k where pi<pk<pj.

Links

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

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;
  1, 1;
  1, 1, 3;
  1, 1, 3, 3, 6, 2,  1;
  1, 1, 3, 3, 9, 3, 18, 12, 10,  7,  4;
  1, 1, 3, 3, 9, 6, 19, 17, 29, 30, 54, 40, 47, 28, 41, 14,  8,  7,  1,  1;
  ...

Crossrefs

Row sums give A336282.

Cf. A390832 (triangle of 123 patterns), A391286 (sum of 123 patterns).

Sequence in context: A133116 A059959 A192812 * A125127 A051120 A114476

Adjacent sequences: A387702 A387703 A387704 * A387706 A387707 A387708

Keyword

nonn,tabf

Author

Manolopoulos Panagiotis, Dec 01 2025

Extensions

More terms from Sean A. Irvine, Dec 15 2025

Status

approved