A391697 Total number of 213 patterns in all heapable permutations of length n.

0, 0, 0, 0, 1, 11, 110, 1080, 11047, 119531, 1378337, 16965766, 222795401, 3116148625, 46318941935, 729946419128

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 213-pattern in a heapable permutation p=(p1,p2..pn) is a triad of indices i<j<k where pj<pi<pk.

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>=1} k*A391508(n,k). - Andrew Howroyd, Dec 17 2025

Example

For n=4 the heapable permutations are:
  (1,2,3,4): 0 213 patterns.
  (1,3,2,4): (3,2,4) => 1 213 pattern.
  (1,2,4,3): 0 213 patterns.
  (1,3,4,2): 0 213 patterns.
  (1,4,2,3): 0 213 patterns.

Crossrefs

Cf. A336282 (heapable permutations), A391508 (triangle of 213 patterns), A391181, A390832.

Sequence in context: A190944 A115822 A162760 * A190871 A097784 A352574

Adjacent sequences: A391694 A391695 A391696 * A391698 A391699 A391700

Keyword

nonn,more

Author

Manolopoulos Panagiotis, Dec 17 2025

Extensions

a(11)-a(15) from Sean A. Irvine, Dec 22 2025

a(0)=0 inserted by Sean A. Irvine, Jan 26 2026

Status

approved