login
A373897
Number of (binary) heaps of length n-k whose element set equals [k], where k is chosen so as to maximize this number.
2
1, 0, 1, 1, 1, 3, 5, 9, 23, 55, 147, 386, 1004, 3128, 8113, 27456, 111574, 321433, 1150885, 4888981, 17841912, 80566518, 332583340, 1188065665, 5473922425, 21725492503, 99894124075, 548452369329, 2185136109838, 11339193480666, 59140581278157, 288137011157366
OFFSET
0,6
COMMENTS
These heaps may contain repeated elements. Their element sets are gap-free and contain 1 (if nonempty).
LINKS
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap
FORMULA
a(n) = max({ A373451(n-j,j) : 0 <= j <= floor(n/2) }).
EXAMPLE
a(6) = 5: 2111, 2121, 2211, 2212, 2221 (with k=2).
a(7) = 9: 21111, 21211, 22111, 22112, 22121, 22122, 22211, 22212, 22221 (with k=2).
a(8) = 23: 31211, 32111, 32112, 32121, 32122, 32211, 32212, 32221, 32311, 32312, 32321, 33112, 33121, 33122, 33123, 33132, 33211, 33212, 33213, 33221, 33231, 33312, 33321 (with k=3).
(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-> max(seq(T(n-j, j), j=0..n/2)):
seq(a(n), n=0..31);
CROSSREFS
Antidiagonal maxima of A373451.
Cf. A373632.
Sequence in context: A146275 A089636 A241398 * A262483 A083366 A006722
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jun 21 2024
STATUS
approved