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

Author

Alois P. Heinz, Jun 21 2024

Keywords

• nonn

Comments

These heaps may contain repeated elements. Their element sets are gap-free and contain 1 (if nonempty).

Examples

			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.)
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..711
• Eric Weisstein's World of Mathematics, Heap
• Wikipedia, Binary heap

Crossrefs

Antidiagonal maxima of A373451.

Cf. A373632.

Programs

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);

Formula

a(n) = max({ A373451(n-j,j) : 0 <= j <= floor(n/2) }).