cp's OEIS Frontend

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

%I A309052 #30 Feb 16 2025 08:33:55
%S A309052 0,1,3,8,15,31,54,105,166,298,478,863,1307,2247,3500,6136,9032,15084,
%T A309052 23039,39599,57955,96019,145627,248223,357650,583274,875459,1476754,
%U A309052 2131618,3476550,5210521,8766473,12498445,20138409,29952394,50020414,71658602,115850282
%N A309052 Total number of 1's in all (binary) max-heaps on n elements from the set {0,1}.
%C A309052 Also the total number of 0's in all (binary) min-heaps on n elements from the set {0,1}.
%H A309052 Alois P. Heinz, <a href="/A309052/b309052.txt">Table of n, a(n) for n = 0..5631</a>
%H A309052 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A309052 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A309052 a(n) = Sum_{k=0..n} (n-k) * A309049(n,k).
%F A309052 a(n) = n * A091980(n+1) - A309051(n).
%F A309052 a(2^n-1) = A024358(n).
%e A309052 a(4) = 15 = 0+1+2+2+3+3+4, the total number of 1's in 0000, 1000, 1010, 1100, 1101, 1110, 1111.
%p A309052 b:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> expand(
%p A309052       1+x*b(f)*b(n-1-f)))(min(g-1, n-g/2)))(2^ilog2(n)))
%p A309052     end:
%p A309052 a:= n-> subs(x=1, diff(b(n), x)):
%p A309052 seq(a(n), n=0..40);
%t A309052 b[n_][x_] := b[n][x] = If[n == 0, 1, Function[g, Function[f, Expand[1 + x b[f][x] b[n - 1 - f][x]]][Min[g - 1, n - g/2]]][2^(Length[IntegerDigits[ n, 2]] - 1)]];
%t A309052 a[n_] := b[n]'[1];
%t A309052 a /@ Range[0, 40] (* _Jean-François Alcover_, Apr 22 2021, after _Alois P. Heinz_ *)
%Y A309052 Cf. A024358, A056971, A091980, A309049, A309051.
%K A309052 nonn
%O A309052 0,3
%A A309052 _Alois P. Heinz_, Jul 09 2019