cp's OEIS Frontend

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

%I A056972 #86 Feb 24 2025 20:06:50
%S A056972 1,1,2,80,21964800,74836825861835980800000,
%T A056972 2606654998899867556195703676289609067340669424836280320000000000
%N A056972 Number of (binary) heaps on n levels (i.e., of 2^n - 1 elements).
%C A056972 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.
%C A056972 a(n) is also the number of knockout tournament seedings that satisfy the increasing competitive intensity property. - _Alexander Karpov_, Aug 18 2015
%C A056972 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
%C A056972 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
%C A056972 If a bracket of 2^n teams is specified for a single-elimination tournament, a(n) is the number of sequences in which the games of the tournament can be played in a single arena. - _Noah A Rosenberg_, Jan 01 2025
%H A056972 Alois P. Heinz, <a href="/A056972/b056972.txt">Table of n, a(n) for n = 0..9</a>
%H A056972 Emily H. Dickey and Noah A. Rosenberg, <a href="https://doi.org/10.1098/rstb.2023.0307">Labelled histories with multifurcation and simultaneity</a>, Phil. Trans. R. Soc. B 380 (2025), 20230307.
%H A056972 Sela Fried and Toufik Mansour, <a href="https://arxiv.org/abs/2308.00315">Random walk labelings of perfect trees and other graphs</a>, arXiv:2308.00315 [math.CO], 2023.
%H A056972 Alexander Karpov, <a href="http://www.uni-heidelberg.de/md/awi/forschung/dp600.pdf">A theory of knockout tournament seedings</a>, Heidelberg University, AWI Discussion Paper Series, No. 600.
%H A056972 Matthew C. King and Noah A. Rosenberg, <a href="https://doi.org/10.1080/0025570X.2023.2266389">A mathematical connection between single-elimination sports tournaments and evolutionary trees</a>, Math. Mag. 96 (2023), 484-497.
%H A056972 Egor Lappo and Noah A. Rosenberg, <a href="https://doi.org/10.1016/j.dam.2023.09.033">A lattice structure for ancestral configurations arising from the relationship between gene trees and species trees</a>, Adv. Appl. Math. 343 (2024), 65-81.
%H A056972 Noah A. Rosenberg, <a href="https://doi.org/10.1007/s00026-006-0278-6">The Mean and Variance of the Numbers of r-Pronged Nodes and r-Caterpillars in Yule-Generated Genealogical Trees</a>, Ann. Combinator. 10 (2006), 129-146.
%H A056972 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A056972 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A056972 a(n) = A056971(A000225(n)).
%F A056972 a(n) = A195581(2^n-1,n).
%F A056972 a(n) = binomial(2^n-2, 2^(n-1)-1)*a(n-1)^2. - _Robert Israel_, Aug 18 2015, from the Mathematica program
%F A056972 a(n) = (2^n-1)!/Product_{k=1..n} (2^k-1)^(2^(n-k)). - _Robert Israel_, Aug 18 2015, from the Maple program
%e A056972 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.
%p A056972 a:= n-> (2^n-1)!/mul((2^k-1)^(2^(n-k)), k=1..n):
%p A056972 seq(a(i), i=0..6);  # _Alois P. Heinz_, Nov 22 2007
%t A056972 s[1] := 1; s[l_] := s[l] := Binomial[2^l-2, 2^(l-1)-1]s[l-1]^2; Table[s[l], {l, 10}]
%o A056972 (Python)
%o A056972 from math import prod, factorial
%o A056972 def A056972(n): return factorial((1<<n)-1)//prod(((1<<k)-1)**(1<<n-k) for k in range(1,n+1)) # _Chai Wah Wu_, May 06 2024
%Y A056972 Cf. A000225, A056971, A195581.
%Y A056972 Column k=2 of A273712.
%K A056972 nonn
%O A056972 0,3
%A A056972 _Eric W. Weisstein_