|
%I #22 Apr 22 2021 05:25:08
%S 0,1,3,7,13,24,42,77,122,206,332,578,889,1484,2338,4019,5960,9685,
%T 14887,25134,37225,60704,92919,156646,227302,364551,550329,917822,
%U 1337358,2158150,3258779,5441757,7800755,12412461,18546566,30708486,44327782,71090442
%N Total number of 0's in all (binary) max-heaps on n elements from the set {0,1}.
%C Also the total number of 1's in all (binary) min-heaps on n elements from the set {0,1}.
%H Alois P. Heinz, <a href="/A309051/b309051.txt">Table of n, a(n) for n = 0..5632</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) = Sum_{k=0..n} k * A309049(n,k).
%F a(n) = n * A091980(n+1) - A309052(n).
%e 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 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-> subs(x=1, diff(b(n), x)):
%p seq(a(n), n=0..40);
%t 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 a[n_] := b[n]'[1];
%t a /@ Range[0, 40] (* _Jean-François Alcover_, Apr 22 2021, after _Alois P. Heinz_ *)
%Y Cf. A056971, A091980, A309049, A309052.
%K nonn
%O 0,3
%A _Alois P. Heinz_, Jul 09 2019
|
