

A056972


Number of (binary) heaps on n levels (i.e., of 2^n  1 elements).


5




OFFSET

0,3


COMMENTS

A sequence {a_i}_{i=1..N} forms a (binary) heap if it satisfies a_i<a_{2i} and a_i<a_{2i+1} for 1<=i<=(N1)/2.
a(n) is also the number of knockout tournament seedings that satisfy the increasing competitive intensity property.  Alexander Karpov, Aug 18 2015
a(n) is the number of coalescence sequences, or labeled histories, for a binary, leaflabeled, rooted tree topology with 2^n leaves (Rosenberg 2006, Theorem 3.3 for a completely symmetric tree with 2^n leaves, dividing by Theorem 3.2 for 2^n leaves).  Noah A Rosenberg, Feb 12 2019


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..9
Alexander Karpov, A theory of knockout tournament seedings, Heidelberg University, AWI Discussion Paper Series, No. 600.
Noah A. Rosenberg, The Mean and Variance of the Numbers of rPronged Nodes and rCaterpillars in YuleGenerated Genealogical Trees, Ann. Combinator. 10 (2006), 129146.
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap


FORMULA

a(n) = A056971(A000225(n)).
a(n) = A195581(2^n1,n).
a(n) = binomial(2^n2, 2^(n1)1)*a(n1)^2.  Robert Israel, Aug 18 2015, from the Mathematica program
a(n) = (2^n1)!/Product_{k=1..n} (2^k1)^(2^(nk)).  Robert Israel, Aug 18 2015, from the Maple program


EXAMPLE

There is 1 heap on 2^01=0 elements, 1 heap on 2^11=1 element and there are 2 heaps on 2^21=3 elements and so on.


MAPLE

a:= n> (2^n1)!/mul((2^k1)^(2^(nk)), k=1..n):
seq(a(i), i=0..6); # Alois P. Heinz, Nov 22 2007


MATHEMATICA

s[1] := 1; s[l_] := s[l] := Binomial[2^l2, 2^(l1)1]s[l1]^2; Table[s[l], {l, 10}]


CROSSREFS

Cf. A000225, A056971, A195581.
Column k=2 of A273712.
Sequence in context: A156932 A291331 A293290 * A051391 A041799 A187858
Adjacent sequences: A056969 A056970 A056971 * A056973 A056974 A056975


KEYWORD

nonn


AUTHOR

Eric W. Weisstein


STATUS

approved



