login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A056972 Number of (binary) heaps on n levels (i.e., of 2^n - 1 elements). 5
1, 1, 2, 80, 21964800, 74836825861835980800000, 2606654998899867556195703676289609067340669424836280320000000000 (list; graph; refs; listen; history; text; internal format)
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

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 r-Pronged Nodes and r-Caterpillars in Yule-Generated Genealogical Trees, Ann. Combinator. 10 (2006), 129-146.

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

FORMULA

a(n) = A056971(A000225(n)).

a(n) = A195581(2^n-1,n).

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):

seq(a(i), i=0..6);  # Alois P. Heinz, Nov 22 2007

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 20 09:56 EDT 2019. Contains 326143 sequences. (Running on oeis4.)