A373897 Number of (binary) heaps of length n-k whose element set equals [k], where k is chosen so as to maximize this number.

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

Alois P. Heinz, Table of n, a(n) for n = 0..711

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

Adjacent sequences: A373894 A373895 A373896 * A373898 A373899 A373900

Keyword

nonn

Author

Alois P. Heinz, Jun 21 2024

Status

approved