OFFSET
0,3
COMMENTS
These heaps contain repeated elements and their element sets are gap-free and contain 1 (if nonempty).
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..254
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap
FORMULA
a(n) = A373451(2n,n).
EXAMPLE
a(0) = 1: the empty heap.
a(1) = 1: 11.
a(2) = 5: 2111, 2121, 2211, 2212, 2221.
a(3) = 55: 312111, 312112, 313112, 321111, ..., 333221, 333231, 333312, 333321.
a(4) = 1004: 41311121, 41311211, 41311221, 41311231, ... 44444213, 44444231, 44444312, 44444321.
(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:
a:= n-> add(binomial(n, j)*(-1)^j*b(2*n, n-j), j=0..n):
seq(a(n), n=0..17);
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jun 06 2024
STATUS
approved