A132862 Number of permutations divided by the number of (binary) heaps on n elements.

1, 1, 2, 3, 8, 15, 36, 63, 192, 405, 1080, 2079, 6048, 12285, 31752, 59535, 193536, 433755, 1224720, 2488563, 7620480, 16253055, 44008272, 86266215, 274337280, 602791875, 1671742800, 3341878155, 10081895040, 21210236775, 56710659600, 109876902975, 368709304320

Offset: 0

Author

Alois P. Heinz, Nov 18 2007

Keywords

• nonn

Comments

a(n) is an integer multiple of n for all n>=1.

a(n) gives the number of complete binary trees on the n numbers from 1 to n (under the same definition of complete used for heaps) with the property that, at each node of the tree, each left descendant is less than each right descendant. For instance, for n=5, there are 15 such trees, determined by a choice of any value at the root and any of the three smallest remaining values as its left child. a(n) can be computed from an unlabeled complete tree on n nodes as the product of the numbers of descendants of each node (including the node itself). - David Eppstein, Mar 18 2016

a(n-1) gives 2 to the power of the minimal value of the s-shape statistic of rooted binary trees with n leaves. - Mareike Fischer, Aug 08 2025

Examples

			a(4) = 8 because 8 = 24/3 and there are 24 permutations on 4 elements, 3 of which are heaps, namely (1,2,3,4), (1,2,4,3) and (1,3,2,4). In every (min-) heap, the element at position i has to be larger than an element at position floor(i/2) for all i=2..n.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..2442
• Olivier Bodini, Antoine Genitrini, Bernhard Gittenberger, Isabella Larcher, and Mehdi Naima, Compaction for two models of logarithmic-depth trees: Analysis and Experiments, arXiv:2005.12997 [math.CO], 2020.
• Sean Cleary, Mareike Fischer, and Katherine St. John, The GFB Tree and Tree Imbalance Indices, arXiv:2502.12854 [q-bio.PE], 2025. See pp. 14, 16.
• Eric Weisstein's World of Mathematics, Heap
• Wikipedia, Binary heap

Crossrefs

Cf. A000142, A029837, A053644, A056971, A133385, A386912.

Programs

Maple

a:= proc(n) option remember; `if`(n=0, 1, (b-> (f->
      a(f)*n*a(n-1-f))(min(b-1, n-b/2)))(2^ilog2(n)))
    end:
seq(a(n), n=0..50);

Mathematica

a[n_] := a[n] = Module[{b, nl}, If[n<2, 1, b = 2^Floor[Log[2, n]]; nl = Min[b-1, n-b/2]; n*a[nl]*a[n-1-nl]]]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Mar 05 2014, after Alois P. Heinz *)

Formula

a(n) = n * a(f) * a(n-1-f) with f = min(b-1,n-b/2) and b = 2^floor(log_2(n)) for n>0, a(0) = 1.

a(n) = A000142(n)/A056971(n).

From Mareike Fischer, Aug 08 2025: (Start)

a(n-1) = Product_{i=2..n} (i-1)^q(n,i), with

q(n,i) = floor(n/i) if i=2^(k(i)) and ((n mod i)=0 or (n mod i) >= 2^(k(i)-1)),

= floor(n/i)-1 if i=2^(k(i)) and (0 < (n mod i) < 2^(k(i)-1)),

= 1 if (i != 2^(k(i)) and ( (n-i) mod 2^(k(i)-1)) = 0 ),

= 0 if (i != 2^(k(i)) and ( (n-i) mod 2^(k(i)-1)) > 0 ) and

k(n) = ceiling(log_2(n)) = A029837(n).

Or also, a(n-1) = Product_{i=0..k(n)-1} (2^(k(n)-i)-1)^(2^i) if d(n)=2^(k(n)-1). Else, a(n-1) = (Product_{i=0..k(n)-2} (2^(k(n)-i-1)-1)^(2^i)) * Product_{i=1..k(n)-1} ( ((2^(i+1)-1)/(2^i-1))^floor(d(n)/(2^i)) * ( ( 2^i + (d(n)-2^i*floor(d(n)/(2^i)))-1 ) / (2^i-1) )^(ceiling(d(n)/(2^i))-floor(d(n)/(2^i)))) if d(n) < 2^(k(n)-1), with k(n)=ceiling(log_2(n))= A029837(n) and d(n)=n-2^(k(n)-1). (End)