cp's OEIS Frontend

A309051 Total number of 0's in all (binary) max-heaps on n elements from the set {0,1}.

%I A309051 #23 Feb 16 2025 08:33:55
%S A309051 0,1,3,7,13,24,42,77,122,206,332,578,889,1484,2338,4019,5960,9685,
%T A309051 14887,25134,37225,60704,92919,156646,227302,364551,550329,917822,
%U A309051 1337358,2158150,3258779,5441757,7800755,12412461,18546566,30708486,44327782,71090442
%N A309051 Total number of 0's in all (binary) max-heaps on n elements from the set {0,1}.
%C A309051 Also the total number of 1's in all (binary) min-heaps on n elements from the set {0,1}.
%H A309051 Alois P. Heinz, <a href="/A309051/b309051.txt">Table of n, a(n) for n = 0..5632</a>
%H A309051 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A309051 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A309051 a(n) = Sum_{k=0..n} k * A309049(n,k).
%F A309051 a(n) = n * A091980(n+1) - A309052(n).
%e A309051 a(4) = 13 = 4+3+2+2+1+1+0, the total number of 0's in 0000, 1000, 1010, 1100, 1101, 1110, 1111.
%p A309051 b:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> expand(
%p A309051       x^n+b(f)*b(n-1-f)))(min(g-1, n-g/2)))(2^ilog2(n)))
%p A309051     end:
%p A309051 a:= n-> subs(x=1, diff(b(n), x)):
%p A309051 seq(a(n), n=0..40);
%t A309051 b[n_][x_] := b[n][x] = If[n == 0, 1, Function[g, Function[f, Expand[x^n + b[f][x] b[n - 1 - f][x]]][Min[g - 1, n - g/2]]][2^(Length[IntegerDigits[ n, 2]] - 1)]];
%t A309051 a[n_] := b[n]'[1];
%t A309051 a /@ Range[0, 40] (* _Jean-François Alcover_, Apr 22 2021, after _Alois P. Heinz_ *)
%Y A309051 Cf. A056971, A091980, A309049, A309052.
%K A309051 nonn
%O A309051 0,3
%A A309051 _Alois P. Heinz_, Jul 09 2019