OFFSET
0,5
COMMENTS
These heaps may contain repeated elements. Their element sets are gap-free and contain 1 (if nonempty).
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..710
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap
FORMULA
a(n) = Sum_{j=0..floor(n/2)} A373451(n-j,j).
EXAMPLE
a(0) = 1: the empty heap.
a(2) = 1: 1.
a(3) = 1: 11.
a(4) = 2: 111, 21.
a(5) = 4: 1111, 211, 212, 221.
a(6) = 8: 11111, 2111, 2121, 2211, 2212, 2221, 312, 321.
a(7) = 17: 111111, 21111, 21211, 22111, 22112, 22121, 22122, 22211, 22212, 22221, 3121, 3211, 3212, 3221, 3231, 3312, 3321.
(The examples use max-heaps.)
MAPLE
b:= proc(n, k) option remember; `if`(n=0, 1,
(g-> (f-> add(b(f, j)*b(n-1-f, j), j=1..k)
)(min(g-1, n-g/2)))(2^ilog2(n)))
end:
T:= (n, k)-> add(binomial(k, j)*(-1)^j*b(n, k-j), j=0..k):
a:= n-> add(T(n-j, j), j=0..n/2):
seq(a(n), n=0..30);
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jun 11 2024
STATUS
approved