|
| |
|
|
A056971
|
|
Number of heaps on n elements.
|
|
23
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 0,4
|
|
|
COMMENTS
| 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
|
|
|
LINKS
| Alois P. Heinz, Table of n, a(n) for n = 0..100
Eric Weisstein's World of Mathematics, 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); [Corrected Maple program from Alois P. Heinz, Nov 22 2007]
|
|
|
CROSSREFS
| Cf. A056972, A132862.
Sequence in context: A073268 A073190 A066051 * A108125 A175490 A118854
Adjacent sequences: A056968 A056969 A056970 * A056972 A056973 A056974
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Eric Weisstein (eric(AT)weisstein.com)
|
|
|
EXTENSIONS
| 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
|
| |
|
|
