A373632 Number of (binary) heaps where n is the sum of their length and the size of the element set [k].

1, 0, 1, 1, 2, 4, 8, 17, 41, 103, 282, 792, 2239, 6680, 21143, 70647, 245357, 871255, 3202552, 12334046, 49635128, 205403510, 856780528, 3601169551, 15507530896, 69267381313, 320345619798, 1518428936730, 7345400773513, 36469929240960, 186875135258481

Offset: 0

Author

Alois P. Heinz, Jun 11 2024

Keywords

• nonn

Comments

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

Examples

			a(0) = 1: the empty heap.
a(2) = 1: 1.
a(3) = 1: 11.
a(4) = 2: 111, 21.
a(5) = 4: 1111, 211, 212, 221.
a(6) = 8: 11111, 2111, 2121, 2211, 2212, 2221, 312, 321.
a(7) = 17: 111111, 21111, 21211, 22111, 22112, 22121, 22122, 22211, 22212, 22221, 3121, 3211, 3212, 3221, 3231, 3312, 3321.
(The examples use max-heaps.)
		

Links

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

Crossrefs

Antidiagonal sums of 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:
T:= (n, k)-> add(binomial(k, j)*(-1)^j*b(n, k-j), j=0..k):
a:= n-> add(T(n-j, j), j=0..n/2):
seq(a(n), n=0..30);

Formula

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