|
|
A056972
|
|
Number of (binary) heaps on n levels (i.e., of 2^n - 1 elements).
|
|
6
|
|
|
|
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<=(N-1)/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, leaf-labeled, 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
a(n+1) is also the number of random walk labelings of the perfect binary tree of height n, that begin at the root. - Sela Fried, Aug 02 2023
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Heap
|
|
FORMULA
|
a(n) = binomial(2^n-2, 2^(n-1)-1)*a(n-1)^2. - Robert Israel, Aug 18 2015, from the Mathematica program
a(n) = (2^n-1)!/Product_{k=1..n} (2^k-1)^(2^(n-k)). - Robert Israel, Aug 18 2015, from the Maple program
|
|
EXAMPLE
|
There is 1 heap on 2^0-1=0 elements, 1 heap on 2^1-1=1 element and there are 2 heaps on 2^2-1=3 elements and so on.
|
|
MAPLE
|
a:= n-> (2^n-1)!/mul((2^k-1)^(2^(n-k)), k=1..n):
|
|
MATHEMATICA
|
s[1] := 1; s[l_] := s[l] := Binomial[2^l-2, 2^(l-1)-1]s[l-1]^2; Table[s[l], {l, 10}]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|