A056971 Number of (binary) heaps on n elements.
1, 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, 19200, 79200, 506880, 2745600, 21964800, 108108000, 820019200, 5227622400, 48881664000, 319258368000, 3143467008000, 25540669440000, 299677188096000, 2261626278912000, 25732281217843200, 241240136417280000
Offset: 0
A133385 Number of permutations of n elements divided by the number of (binary) heaps on n+1 elements.
1, 1, 1, 2, 3, 6, 9, 24, 45, 108, 189, 504, 945, 2268, 3969, 12096, 25515, 68040, 130977, 381024, 773955, 2000376, 3750705, 11430720, 24111675, 64297800, 123773265, 360067680, 731387475, 1890355320, 3544416225, 11522165760, 25823603925, 72913705200, 148156598205
Offset: 0
Keywords
Comments
In a min-heap on (n+1) distinct elements only n elements can change places, since the first element is determined to be the minimum. a(n) gives the number of all possibilities divided by the number of legal possibilities to do this.
Is this the sequence mentioned on page 360 of Motzkin (1948)? - N. J. A. Sloane, Jul 04 2015
Examples
a(4) = 3 because 3 = 24/8 and there are 4! = 24 permutations on 4 elements and 8 min-heaps on 5 elements, namely (0,1,2,3,4), (0,1,2,4,3), (0,1,3,2,4), (0,1,3,4,2), (0,1,4,2,3), (0,1,4,3,2), (0,2,1,3,4), and (0,2,1,4,3). In every (min-) heap, the element at position i has to be larger than the element at position floor(i/2) for all i=2..n. The minimum is always found at position 1.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..2450
- T. Motzkin, The hypersurface cross ratio, Bull. Amer. Math. Soc., 51 (1945), 976-984.
- T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360.
- Eric Weisstein's World of Mathematics, Heap
- Wikipedia, Binary heap
Programs
-
Maple
h:= proc(n) option remember; `if`(n=0, 1, (b-> (f-> h(f)*n*h(n-1-f))(min(b-1, n-b/2)))(2^ilog2(n))) end: a:= n-> h(n+1)/(n+1): seq(a(n), n=0..50); -
Mathematica
aa[n_] := aa[n] = Module[{b, nl}, If[n<2, 1, b = 2^Floor[Log[2, n]]; nl = Min[b-1, n-b/2]; n*aa[nl]*aa[n-1-nl]]]; a[n_] := aa[n+1]/(n+1); Table[a[i], {i, 0, 50}] (* Jean-François Alcover, Mar 05 2014, after Alois P. Heinz *)
A386912 The base-2 logarithm of this sequence equals the Q statistic value of the greedy-from-the-bottom tree with n leaves, which is the minimal Q statistic value for n.
1, 2, 6, 16, 60, 192, 672, 2048, 8640, 30720, 118272, 393216, 1597440, 5505024, 20643840, 67108864, 300810240, 1132462080, 4602200064, 16106127360, 68702699520, 248034361344, 972407439360, 3298534883328, 14495514624000, 53601191854080
Offset: 1
Keywords
Examples
a(1)=1, because a(1)=Product(i=2..1)=1 (empty product). a(2)=2, because q(2,2)=1, so a(2)=2^q(2,2)=2^1=2. a(3)=6, because q(3,2)=1 and q(3,3)=1, so a(3)=2^q(3,2)*3^q(3,3)=2^1*3^1=6.
Links
- Alois P. Heinz, Table of n, a(n) for n = 1..1666 (first 300 terms from Mareike Fischer)
- Sean Cleary, Mareike Fischer, and Katherine St. John, The GFB Tree and Tree Imbalance Indices, arXiv:2502.12854 [q-bio.PE], 2025.
Crossrefs
Cf. A132862.
Programs
-
Maple
a:= proc(n) option remember; `if`(n<2, 1, (b-> (f-> a(f)*n*a(n-f))(min(b, n-b/2)))(2^ilog2(n-1))) end: seq(a(n), n=1..26); # Alois P. Heinz, Aug 18 2025 -
Mathematica
q[n_, i_] := Module[{factor, ki}, factor = FactorInteger[i]; ki = Ceiling[Log2[i]]; If[(i == 1 || i == n), Return[n/i], If[(Length[factor] == 1 && factor[[1]][[1]] == 2), If[(Mod[n, i] == 0 || Mod[n, i] >= 2^(ki - 1)), Return[Floor[n/i]], Return[Floor[n/i] - 1]], If[Mod[n - i, 2^(ki - 1)] == 0, Return[1], Return[0]]]; ]]; a[n_] := Product[i^q[n, i], {i, 2, n}]; alist = {}; For[n = 1, n <= 300, n++, AppendTo[alist, a[n]]]; Print[alist] (* Alternative, after Alois P. Heinz: *) A386912[n_] := A386912[n] = If[n == 1, 1, n*A386912[#]*A386912[n - #]] & [Min[#, n - #/2] & [2^(BitLength[n - 1] - 1)]]; Array[A386912, 30] (* Paolo Xausa, Aug 19 2025 *) -
Python
from functools import lru_cache @lru_cache(maxsize=None) def a(n: int) -> int: if n < 2: return 1 b = 1 << ((n - 1).bit_length() - 1) f = min(b, n - b // 2) return a(f) * n * a(n - f) print([a(n) for n in range(1, 27)]) # after Alois P. Heinz, Peter Luschny, Aug 19 2025
Formula
a(n) = Product_{i=2..n} i^q(n,i), with k(i)=ceiling(log_2(i)) and q(n,i)=floor(n/i) if (i=2^(k(i)) and ((n mod i)=0 or (n mod i)>=2^(k(i)-1))), and q(n,i)=floor(n/i)-1 if (i=2^(k(i)) and (0 < (n mod i)< 2^(k(i)-1))) and q(n,i)=1 if (i!=2^(k(i)) and ( (n-i) mod 2^(k(i)-1)) =0 ) and q(n,i)=0 if (i!=2^(k(i)) and ( (n-i) mod 2^(k(i)-1)) >0 ).
a(n) = Product_{i=0..k(n)-1} (2^(k(n)-i))^(2^i) if d(n)=2^(k(n)-1). Else, a(n) = Product_{i=0..k(n)-2} (2^(k(n)-i-1))^(2^i) * 2^d(n) * Product_{i=1..k(n)-1} ( 2^floor(d(n)/(2^i)) * ((2^i + (d(n)-2^i*(floor(d(n)/(2^i))))) / (2^i) )^(ceiling(d(n)/2^i)-floor(d(n)/(2^i))) if d(n) < 2^(k(n)-1), with k(n)=ceiling(log_2(n)) and d(n)=n-2^(k(n)-1).
a(n) = n*a(f)*a(n-f) with f = min(b,n-b/2) and b = 2^floor(log_2(n-1)) for n>1, a(1) = 1. - Alois P. Heinz, Aug 18 2025
Comments
Examples
There is 1 heap if n is in {0,1,2}, 2 heaps for n=3, 3 heaps for n=4 and so on. a(5) = 8 (min-heaps): 12345, 12354, 12435, 12453, 12534, 12543, 13245, 13254.Links
Crossrefs
Programs
Maple
a[0] := 1: a[1] := 1: for n from 2 to 50 do h := ilog2(n+1)-1: b := 2^h-1: r := n-1-2*b: r1 := r-floor(r/2^h)*(r-2^h): r2 := r-r1: a[n] := binomial(n-1, b+r1)*a[b+r1]*a[b+r2]:end do: q := seq(a[j], j=0..50); # second Maple program: a:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> a(f)* binomial(n-1, f)*a(n-1-f))(min(g-1, n-g/2)))(2^ilog2(n))) end: seq(a(n), n=0..28); # Alois P. Heinz, Feb 14 2019Mathematica
a[0] = 1; a[1] = 1; For[n = 2, n <= 50, n++, h = Floor[Log[2, n + 1]] - 1; b = 2^h - 1; r = n - 1 - 2*b; r1 = r - Floor[r/2^h]*(r - 2^h); r2 = r - r1; a[n] = Binomial[n - 1, b + r1]*a[b + r1]*a[b + r2]]; Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Oct 22 2012, translated from Maple program *)Python
Formula
Extensions