OFFSET
0,3
COMMENTS
Also the number of (binary) min-heaps on 2n elements from the set {0,1} containing n 0's and n 1's.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..3000
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap
FORMULA
a(n) = A309049(2n,n).
EXAMPLE
a(0) = 1: ().
a(1) = 1: 10.
a(2) = 2: 1010, 1100.
a(3) = 4: 101001, 110010, 110100, 111000.
a(4) = 7: 10100110, 11010001, 11011000, 11100010, 11100100, 11101000, 11110000.
a(5) = 13: 1101000110, 1101100001, 1101100010, 1101100100, 1110011000, 1110100001, 1110101000, 1110110000, 1111000010, 1111000100, 1111001000, 1111010000, 1111100000.
MAPLE
b:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> expand(
x^n+b(f)*b(n-1-f)))(min(g-1, n-g/2)))(2^ilog2(n)))
end:
a:= n-> coeff(b(2*n), x, n):
seq(a(n), n=0..40);
MATHEMATICA
b[n_] := b[n] = If[n == 0, 1, Function[g, Function[f, Expand[x^n + b[f]*b[n - 1 - f]]][Min[g - 1, n - g/2]]][2^(Length@IntegerDigits[n, 2] - 1)]];
a[n_] := Coefficient[b[2n], x, n];
a /@ Range[0, 40] (* Jean-François Alcover, Apr 19 2021, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jul 09 2019
STATUS
approved