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

Author

Alois P. Heinz, Jun 05 2024

Keywords

• nonn

Comments

These heaps may contain repeated elements.

Examples

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

Links

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

Crossrefs

Main diagonal of A373449.

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

Cf. A007318, A373451.

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:
a:= n-> b(n$2):
seq(a(n), n=0..21);

Formula

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

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