A391777 - OEIS

%I #14 Jan 07 2026 14:21:43

%S 0,0,0,0,1,11,107,1038,10522,113302,1302812,16015199,210235874,

%T 2941323511,43751523889,690175187973

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

%C 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.

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

%H Benjamin Chen, Michael Cho, Mario Tutuncu-Macias, and Tony Tzolov, <a href="https://doi.org/10.1016/j.dam.2023.01.025">Efficient methods of calculating the number of heapable permutations</a>, Discrete Applied Mathematics Volume 331, 31 May 2023, Pages 126-137.

%H Manolopoulos Panagiotis, <a href="/A391777/a391777.py.txt">Python Program</a>

%e For n=4 the heapable permutations are:

%e   (1,2,3,4): no 231 patterns.

%e   (1,3,2,4): no 231 patterns.

%e   (1,2,4,3): no 231 patterns.

%e   (1,3,4,2): (3,4,2) => 1 231 pattern.

%e   (1,4,2,3): no 231 patterns.

%e So among the 5 heapable permutations of length 4:

%e   4 permutation have 0 231 patterns,

%e   1 permutation has 1 231 pattern,

%e   for a total of 1 132 patterns.

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

%K nonn,more

%O 0,6

%A _Manolopoulos Panagiotis_, Dec 19 2025

%E a(11)-a(15) from _Sean A. Irvine_, Jan 05 2026