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

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

Author

Alois P. Heinz, Jun 10 2024

Keywords

• nonn

Comments

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

Examples

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

Links

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

Crossrefs

Row maxima of A373451.

Cf. A002869.

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, k), k=0..n)):
seq(a(n), n=0..24);

Formula

a(n) = max({ A373451(n,k) : 0 <= k <= n }).