cp's OEIS Frontend

A309050 Number of (binary) max-heaps on 2n elements from the set {0,1} containing n 0's and n 1's.

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