login
A376962
Number of (binary) heaps of length n whose element set equals {1,2,3}.
2
2, 7, 23, 55, 147, 281, 633, 1241, 2849, 5187, 11195, 21369, 47933, 83821, 174245, 324571, 712247, 1263211, 2660843, 4999291, 11056139, 19236203, 39793055, 73882568, 161646306, 286178632, 601791336, 1129403320, 2495184864, 4326802772, 8921711316, 16528692452
OFFSET
3,1
LINKS
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap
EXAMPLE
a(4) = 7: 3121, 3211, 3212, 3221, 3231, 3312, 3321.
a(5) = 23: 31211, 32111, 32112, 32121, 32122, 32211, 32212, 32221, 32311, 32312, 32321, 33112, 33121, 33122, 33123, 33132, 33211, 33212, 33213, 33221, 33231, 33312, 33321.
(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))(3):
seq(a(n), n=3..35);
CROSSREFS
Column k=3 of A373451.
Sequence in context: A121963 A041159 A210109 * A034546 A281584 A230315
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Oct 10 2024
STATUS
approved