|
%I #16 Apr 19 2021 07:26:08
%S 1,1,2,4,7,13,27,54,109,219,460,962,1986,4044,8516,18058,37801,77701,
%T 164300,350336,738945,1530521,3250659,6962248,14735660,30625898,
%U 65206770,140040538,297712980,622136512,1328716192,2861101350,6086238317,12716525621,27172910036
%N Number of (binary) max-heaps on 2n elements from the set {0,1} containing n 0's and n 1's.
%C Also the number of (binary) min-heaps on 2n elements from the set {0,1} containing n 0's and n 1's.
%H Alois P. Heinz, <a href="/A309050/b309050.txt">Table of n, a(n) for n = 0..3000</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Heap.html">Heap</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F a(n) = A309049(2n,n).
%e a(0) = 1: ().
%e a(1) = 1: 10.
%e a(2) = 2: 1010, 1100.
%e a(3) = 4: 101001, 110010, 110100, 111000.
%e a(4) = 7: 10100110, 11010001, 11011000, 11100010, 11100100, 11101000, 11110000.
%e a(5) = 13: 1101000110, 1101100001, 1101100010, 1101100100, 1110011000, 1110100001, 1110101000, 1110110000, 1111000010, 1111000100, 1111001000, 1111010000, 1111100000.
%p b:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> expand(
%p x^n+b(f)*b(n-1-f)))(min(g-1, n-g/2)))(2^ilog2(n)))
%p end:
%p a:= n-> coeff(b(2*n), x, n):
%p seq(a(n), n=0..40);
%t 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)]];
%t a[n_] := Coefficient[b[2n], x, n];
%t a /@ Range[0, 40] (* _Jean-François Alcover_, Apr 19 2021, after _Alois P. Heinz_ *)
%Y Cf. A056971, A309049.
%K nonn
%O 0,3
%A _Alois P. Heinz_, Jul 09 2019
|
