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!)
A309050 Number of (binary) max-heaps on 2n elements from the set {0,1} containing n 0's and n 1's. 2
1, 1, 2, 4, 7, 13, 27, 54, 109, 219, 460, 962, 1986, 4044, 8516, 18058, 37801, 77701, 164300, 350336, 738945, 1530521, 3250659, 6962248, 14735660, 30625898, 65206770, 140040538, 297712980, 622136512, 1328716192, 2861101350, 6086238317, 12716525621, 27172910036 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Also the number of (binary) min-heaps on 2n elements from the set {0,1} containing n 0's and n 1's.

LINKS

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

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

FORMULA

a(n) = A309049(2n,n).

EXAMPLE

a(0) = 1: ().

a(1) = 1: 10.

a(2) = 2: 1010, 1100.

a(3) = 4: 101001, 110010, 110100, 111000.

a(4) = 7: 10100110, 11010001, 11011000, 11100010, 11100100, 11101000, 11110000.

a(5) = 13: 1101000110, 1101100001, 1101100010, 1101100100, 1110011000, 1110100001, 1110101000, 1110110000, 1111000010, 1111000100, 1111001000, 1111010000, 1111100000.

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-> coeff(b(2*n), x, n):

seq(a(n), n=0..40);

MATHEMATICA

b[n_] := b[n] = If[n == 0, 1, Function[g, Function[f, Expand[x^n + b[f]*b[n - 1 - f]]][Min[g - 1, n - g/2]]][2^(Length@IntegerDigits[n, 2] - 1)]];

a[n_] := Coefficient[b[2n], x, n];

a /@ Range[0, 40] (* Jean-Fran├žois Alcover, Apr 19 2021, after Alois P. Heinz *)

CROSSREFS

Cf. A056971, A309049.

Sequence in context: A025246 A256942 A112740 * A265580 A136408 A317718

Adjacent sequences:  A309047 A309048 A309049 * A309051 A309052 A309053

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 September 24 15:40 EDT 2021. Contains 347643 sequences. (Running on oeis4.)