login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A309051 Total number of 0's in all (binary) max-heaps on n elements from the set {0,1}. 3
0, 1, 3, 7, 13, 24, 42, 77, 122, 206, 332, 578, 889, 1484, 2338, 4019, 5960, 9685, 14887, 25134, 37225, 60704, 92919, 156646, 227302, 364551, 550329, 917822, 1337358, 2158150, 3258779, 5441757, 7800755, 12412461, 18546566, 30708486, 44327782, 71090442 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Also the total number of 1'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..5632

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

FORMULA

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

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

EXAMPLE

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

MAPLE

b:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> expand(

      x^n+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[x^n + 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. A056971, A091980, A309049, A309052.

Sequence in context: A156209 A076276 A296558 * A056764 A026103 A328652

Adjacent sequences:  A309048 A309049 A309050 * A309052 A309053 A309054

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Jul 09 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 17 17:21 EDT 2021. Contains 348065 sequences. (Running on oeis4.)