0,4

A sequence {a_i}_{i=1}^N forms a (binary) heap if is 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 (sascha.kurz(AT)uni-bayreuth.de), Mar 24 2002

Note that A132862(n)*a(n) = n!. - Alois P. Heinz (heinz(AT)hs-heilbronn.de), Nov 22 2007

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

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

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

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

for n from 2 to 50 do

h := floor(simplify(log(n+1)/log(2)))-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); [Corrected Maple prgram from Alois P. Heinz (heinz(AT)hs-heilbronn.de), Nov 22 2007]

Cf. A056972, A132862.

Sequence in context: A073268 A073190 A066051 this_sequence A108125 A118854 A137652

Adjacent sequences: A056968 A056969 A056970 this_sequence A056972 A056973 A056974

nonn

Eric Weisstein (eric(AT)weisstein.com)

More terms from Sascha Kurz (sascha.kurz(AT)uni-bayreuth.de), Mar 24 2002

Offset corrected by Alois P. Heinz (heinz(AT)hs-heilbronn.de), Nov 21 2007

Sequence corrected by Alois P. Heinz (heinz(AT)hs-heilbronn.de), Nov 22 2007