A373450 Number of (binary) heaps of length n whose element set is a subset of [n].

1, 1, 3, 14, 65, 448, 3136, 32028, 251922, 2891801, 30684797, 464651863, 5434037232, 92246217970, 1379368317328, 29135744093948, 414052904722966, 8546218817446727, 152935671938144301, 3857215760145872627, 70913916905782150177, 1881992311219764068420

Offset

0,3

Comments

These heaps may contain repeated elements.

Links

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

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

Formula

a(n) = A373449(n,n).

a(n) = Sum_{k=0..n} binomial(n,k)*A373451(n,k).

Example

a(0) = 1: the empty heap.
a(1) = 1: 1.
a(2) = 3: 11, 21, 22.
a(3) = 14: 111, 211, 212, 221, 222, 311, 312, 313, 321, 322, 323, 331, 332, 333.
(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-> b(n$2):
seq(a(n), n=0..21);

Crossrefs

Main diagonal of A373449.

Cf. A056971 (distinct elements), A373452 (gap-free element sets including 1).

Cf. A007318, A373451.

Sequence in context: A034275 A240008 A151322 * A351068 A345683 A002320

Adjacent sequences: A373447 A373448 A373449 * A373451 A373452 A373453

Keyword

nonn

Author

Alois P. Heinz, Jun 05 2024

Status

approved