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

0, 1, 3, 8, 15, 31, 54, 105, 166, 298, 478, 863, 1307, 2247, 3500, 6136, 9032, 15084, 23039, 39599, 57955, 96019, 145627, 248223, 357650, 583274, 875459, 1476754, 2131618, 3476550, 5210521, 8766473, 12498445, 20138409, 29952394, 50020414, 71658602, 115850282

Offset

0,3

Comments

Also the total number of 0's in all (binary) min-heaps on n elements from the set {0,1}.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..5631

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

Formula

a(n) = Sum_{k=0..n} (n-k) * A309049(n,k).

a(n) = n * A091980(n+1) - A309051(n).

a(2^n-1) = A024358(n).

Example

a(4) = 15 = 0+1+2+2+3+3+4, the total number of 1's in 0000, 1000, 1010, 1100, 1101, 1110, 1111.

Maple

b:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> expand(
      1+x*b(f)*b(n-1-f)))(min(g-1, n-g/2)))(2^ilog2(n)))
    end:
a:= n-> subs(x=1, diff(b(n), x)):
seq(a(n), n=0..40);

Mathematica

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)]];
a[n_] := b[n]'[1];
a /@ Range[0, 40] (* Jean-François Alcover, Apr 22 2021, after Alois P. Heinz *)

Crossrefs

Cf. A024358, A056971, A091980, A309049, A309051.

Sequence in context: A068038 A196087 A295735 * A328858 A277224 A090741

Adjacent sequences: A309049 A309050 A309051 * A309053 A309054 A309055

Keyword

nonn

Author

Alois P. Heinz, Jul 09 2019

Status

approved