login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A056971 Number of (binary) heaps on n elements. 51
1, 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, 19200, 79200, 506880, 2745600, 21964800, 108108000, 820019200, 5227622400, 48881664000, 319258368000, 3143467008000, 25540669440000, 299677188096000, 2261626278912000, 25732281217843200, 241240136417280000 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

A sequence {a_i}_{i=1..N} forms a (binary) heap if it satisfies a_i<a_{2i} and a_i<a_{2i+1} for 1<=i<=(N-1)/2.

Proof of recurrence: a_1 must take the greatest of the n values. Deleting a_1 gives 2 heaps of size b+r1, b+r2. - Sascha Kurz, Mar 24 2002

Note that A132862(n)*a(n) = n!. - Alois P. Heinz, Nov 22 2007

LINKS

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

Sean Cleary, M Fischer, RC Griffiths, R Sainudiin, Some distributions on finite rooted binary trees, UCDMS Research Report NO. UCDMS2015/2, School of Mathematics and Statistics, University of Canterbury, Christchurch, NZ, 2015.

D. Levin, L. Pudwell, M. Riehl, A. Sandberg, Pattern Avoidance on k-ary Heaps, Slides of Talk, 2014.

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

EXAMPLE

There is 1 heap if n is in {0,1,2}, 2 heaps for n=3, 3 heaps for n=4 and so on.

MAPLE

a[0] := 1: a[1] := 1:

for n from 2 to 50 do

h := ilog2(n+1)-1:

b := 2^h-1: r := n-1-2*b: r1 := r-floor(r/2^h)*(r-2^h): r2 := r-r1:

a[n] := binomial(n-1, b+r1)*a[b+r1]*a[b+r2]:end do:

q := seq(a[j], j=0..50);

# second Maple program:

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

      binomial(n-1, f)*a(n-1-f))(min(g-1, n-g/2)))(2^ilog2(n)))

    end:

seq(a(n), n=0..28);  # Alois P. Heinz, Feb 14 2019

MATHEMATICA

a[0] = 1; a[1] = 1; For[n = 2, n <= 50, n++, h = Floor[Log[2, n + 1]] - 1; b = 2^h - 1; r = n - 1 - 2*b; r1 = r - Floor[r/2^h]*(r - 2^h); r2 = r - r1; a[n] = Binomial[n - 1, b + r1]*a[b + r1]*a[b + r2]]; Table[a[n], {n, 0, 26}] (* Jean-Fran├žois Alcover, Oct 22 2012, translated from Maple program *)

CROSSREFS

Cf. A053644, A056972, A132862.

Column k=2 of A273693.

Column k=0 of A306343 and of A306393.

Sequence in context: A073268 A073190 A066051 * A108125 A175490 A118854

Adjacent sequences:  A056968 A056969 A056970 * A056972 A056973 A056974

KEYWORD

nonn,changed

AUTHOR

Eric W. Weisstein

EXTENSIONS

More terms from Sascha Kurz, Mar 24 2002

Offset and some terms corrected by Alois P. Heinz, Nov 21 2007

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 February 20 19:35 EST 2019. Contains 320345 sequences. (Running on oeis4.)