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

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

Alois P. Heinz, Table of n, a(n) for n = 0..1000

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

Cf. A000142, A053644, A056971, A133385.

Sequence in context: A166920 A242510 A080206 * A055543 A308433 A049957

Adjacent sequences: A132859 A132860 A132861 * A132863 A132864 A132865

Keyword

nonn

Author

Alois P. Heinz, Nov 18 2007

Status

approved