A391777 Total number of 231 patterns in all heapable permutations of length n.

0, 0, 0, 0, 1, 11, 107, 1038, 10522, 113302, 1302812, 16015199, 210235874, 2941323511, 43751523889, 690175187973

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

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

Example

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

Crossrefs

Cf. A336282 (heapable permutations), A391776 (triangle of 231 patterns), A390832 (triangle of 123 patterns), A391697 (total 213 patterns).

Sequence in context: A140617 A224717 A163413 * A287835 A001721 A193308

Adjacent sequences: A391774 A391775 A391776 * A391778 A391779 A391780

Keyword

nonn,more

Author

Manolopoulos Panagiotis, Dec 19 2025

Extensions

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

Status

approved