A373500 Number of (binary) heaps of length 2n whose element set equals [n].

1, 1, 5, 55, 1004, 27456, 1077657, 59699950, 3944644671, 319905929418, 32390662046661, 4181039787994506, 602128996908467070, 102537208988632300118, 20497804459093071390108, 4978144718604701947160364, 1232227300264551117529973052, 335016989869301170468736520008

Offset

0,3

Comments

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

Links

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

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

Formula

a(n) = A373451(2n,n).

Example

a(0) = 1: the empty heap.
a(1) = 1: 11.
a(2) = 5: 2111, 2121, 2211, 2212, 2221.
a(3) = 55: 312111, 312112, 313112, 321111, ..., 333221, 333231, 333312, 333321.
a(4) = 1004: 41311121, 41311211, 41311221, 41311231, ... 44444213, 44444231, 44444312, 44444321.
(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:
a:= n-> add(binomial(n, j)*(-1)^j*b(2*n, n-j), j=0..n):
seq(a(n), n=0..17);

Crossrefs

Cf. A056971, A373451.

Sequence in context: A266481 A371316 A006150 * A140049 A300589 A130031

Adjacent sequences: A373497 A373498 A373499 * A373501 A373502 A373503

Keyword

nonn

Author

Alois P. Heinz, Jun 06 2024

Status

approved