Result: Efficient methods of calculating the number of heapable permutations

A permutation \(\pi \in S_n\) is called heapable if its entries can be inserted, in order, into an initially empty binary heap, resulting in a valid heap. Here, a binary heap is a rooted binary tree in which every node has at most two children, and each child's label is greater than or equal to its parent's label. Heapable permutations must begin with their minimal element. Let \(A_n\) denote the number of heapable permutations of \(\{1, 2, \ldots, n\}\). The authors establish the recurrence \(A_n \le (n-2)A_{n-1} + A_{n-2}\) with \(A_1 = A_2 = 1\), from which they derive the upper bound \(A_n \le c(n-2)!\) for a constant \(c \approx 3.83\). For a lower bound, they show that each heap of size \(n\) admits a top-down labeling that generates a valid heapable permutation by recursively inserting left subtrees before right ones, thereby constructing an injection from heaps to heapable permutations. As heaps are counted by the Euler numbers, this proves that \(A_n \ge 2(2/\pi)^{n+1}n!\). After establishing these inequalities, the paper turns to exact enumeration. A key notion is the extended signature, a word of length \(n\) over the alphabet \(\{0,1,2\}\) that records the remaining child slots after each insertion. A greedy \(O(n^{2})\) procedure computes the maximal signature of any permutation. Grouping permutations by signature yields an \(O(n^{2}3^{n})\) counting algorithm, refined to \(O(n^{3}3^{n/2})\) via a cut-off that exploits mid-prefix agreement. The extended signatures are shown to be in bijection with Motzkin paths of length \(n-1\), clarifying the combinatorial structure and enabling practical computation of \(A_n\) for moderate \(n\). Connections are drawn to increasing \(0\)-\(1\)-\(2\) trees and secretary-type selection problems, and the authors pose open questions on polynomial-time enumeration and sharp asymptotics.