login
A376963
Number of (binary) heaps of length n whose element set equals {1,2,3,4}.
2
3, 23, 92, 386, 1004, 3128, 8039, 24725, 56825, 159665, 383447, 1113059, 2366723, 6191435, 14145653, 39253721, 84455981, 223305485, 513899477, 1435302869, 2999680197, 7717870961, 17422727232, 47809866678, 102098766668, 268024219452, 613622726480, 1705588304448
OFFSET
4,1
LINKS
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap
EXAMPLE
a(4) = 3: 4231, 4312, 4321.
a(5) = 23: 42311, 42312, 42321, 43112, 43121, 43122, 43123, 43132, 43211, 43212, 43213, 43221, 43231, 43312, 43321, 43412, 43421, 44123, 44132, 44213, 44231, 44312, 44321.
(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-> (k-> add(binomial(k, j)*(-1)^j*b(n, k-j), j=0..k))(4):
seq(a(n), n=4..35);
CROSSREFS
Column k=4 of A373451.
Sequence in context: A196339 A196318 A213846 * A301580 A112459 A197303
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Oct 10 2024
STATUS
approved