A392533 Total number of 321 patterns in all heapable permutations of length n.

0, 0, 0, 0, 0, 3, 40, 480, 5513, 65051, 800679, 10384967, 142357706, 2064273113, 31644682654, 512196648751

Offset

0,6

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

Table of n, a(n) for n=0..15.

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

a(n) = Sum_{k>=0} k*A391971(n,k).

Example

For n=4 the heapable permutations are:
  (1,2,3,4): no 321 patterns.
  (1,3,2,4): no 321 patterns.
  (1,2,4,3): no 321 patterns.
  (1,3,4,2): no 321 patterns.
  (1,4,2,3): no 321 patterns.
So among the 5 heapable permutations of length 4:
  5 permutation have 0 321 patterns, for a total of 0 321 patterns.

Crossrefs

Cf. A336282 (heapable permutations), A391971 (triangle of 321 patterns), A391697 (total 213 patterns).

Sequence in context: A002700 A220639 A355373 * A337692 A331795 A005724

Adjacent sequences: A392530 A392531 A392532 * A392534 A392535 A392536

Keyword

nonn,more

Author

Manolopoulos Panagiotis, Jan 15 2026

Extensions

a(11)-a(15) from Sean A. Irvine, Jan 26 2026

Status

approved