login
A373608
Number of (binary) heaps of length n whose element set equals [k], where k is chosen so as to maximize this number.
2
1, 1, 1, 3, 7, 23, 92, 502, 1880, 12008, 66730, 516610, 3194229, 29181056, 224463264, 2481941592, 18805353654, 203330533890, 1845535279170, 25328291231632, 244141112078994, 3361871786122320, 39998248932957744, 674899378544965360, 7394457611253245344
OFFSET
0,4
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,k) : 0 <= k <= n }).
EXAMPLE
a(4) = 7: 3121, 3211, 3212, 3221, 3231, 3312, 3321 (with k=3).
a(6) = 92: 413112, 423111, 423112, 423113, 423121, 423122, 423123, ..., 443421, 444123, 444132, 444213, 444231, 444312, 444321 (with k=4).
a(7) = 502: 5141123, 5141132, 5241113, 5241123, 5241131, 5241132, 5241133, ..., 5553421, 5554123, 5554132, 5554213, 5554231, 5554312, 5554321 (with k=5).
(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, k), k=0..n)):
seq(a(n), n=0..24);
CROSSREFS
Row maxima of A373451.
Cf. A002869.
Sequence in context: A100964 A080077 A096318 * A299404 A268140 A133788
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jun 10 2024
STATUS
approved