A373452 Number of (binary) heaps of length n whose element set equals [k] (for some k <= n).

1, 1, 2, 6, 16, 64, 252, 1460, 6256, 39760, 230056, 1920152, 12154416, 113087888, 916563592, 10586707896, 80444848064, 898922718272, 8634371968224, 117894609062176, 1160052513737280, 16638593775310528, 200744153681516384, 3415784055462112160, 38542918215425934624

Offset

0,3

Comments

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

Links

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

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

Example

a(0) = 1: the empty heap.
a(1) = 1: 1.
a(2) = 2: 11, 21.
a(3) = 6: 111, 211, 212, 221, 312, 321.
a(4) = 16: 1111, 2111, 2121, 2211, 2212, 2221, 3121, 3211, 3212, 3221, 3231, 3312, 3321, 4231, 4312, 4321.
(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(add(binomial(k, j)*(-1)^j*b(n, k-j), j=0..k), k=0..n):
seq(a(n), n=0..24);

Mathematica

b[n_, k_] := b[n, k] = If[n == 0, 1, Function[g, Function[f, Sum[b[f, j]*b[n - 1 - f, j], {j, 1, k}]][Min[g - 1, n - g/2]]][2^(Length@IntegerDigits[n, 2] - 1)]];
T[n_, k_] := Sum[Binomial[k, j]*(-1)^j*b[n, k - j], {j, 0, k}];
a[n_] := Sum[T[n, k], {k, 0, n}];
Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Sep 24 2024, after Alois P. Heinz *)

Crossrefs

Row sums of A373451.

Cf. A000670, A056971 (distinct elements), A373450.

Sequence in context: A173994 A363587 A150032 * A283420 A121749 A009386

Adjacent sequences: A373449 A373450 A373451 * A373453 A373454 A373455

Keyword

nonn

Author

Alois P. Heinz, Jun 05 2024

Status

approved