login
A132862
Number of permutations divided by the number of (binary) heaps on n elements.
3
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
OFFSET
0,3
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
LINKS
Olivier Bodini, Antoine Genitrini, Bernhard Gittenberger, Isabella Larcher, Mehdi Naima, Compaction for two models of logarithmic-depth trees: Analysis and Experiments, arXiv:2005.12997 [math.CO], 2020.
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap
FORMULA
a(n) = n * a(nl) * a(n-1-nl) with nl = min(b-1,n-b/2) and b = 2^floor(log_2(n)) for n>1, a(n) = 1 for n<2.
a(n) = A000142(n)/A056971(n).
EXAMPLE
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.
MAPLE
a:= proc(n) option remember; local b, nl;
if n<2 then 1
else b := 2^ilog2(n);
nl:= min(b-1, n-b/2);
n * a(nl) * a(n-1-nl)
fi
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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Nov 18 2007
STATUS
approved