A373450 -id:A373450 - cp's OEIS frontend

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

Alois P. Heinz, Jun 05 2024

nonn

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

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

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

Row sums of A373451.

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

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

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

A373449 Number A(n,k) of (binary) heaps of length n whose element set is a subset of [k]; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 4, 6, 5, 1, 0, 1, 5, 10, 14, 7, 1, 0, 1, 6, 15, 30, 25, 11, 1, 0, 1, 7, 21, 55, 65, 53, 16, 1, 0, 1, 8, 28, 91, 140, 173, 100, 26, 1, 0, 1, 9, 36, 140, 266, 448, 400, 222, 36, 1, 0, 1, 10, 45, 204, 462, 994, 1225, 1122, 386, 56, 1, 0

Offset: 0

Alois P. Heinz, Jun 05 2024

These heaps may contain repeated elements.

			A(3,1) = 1: 111.
A(3,2) = 5: 111, 211, 212, 221, 222.
A(3,3) = 14: 111, 211, 212, 221, 222, 311, 312, 313, 321, 322, 323, 331, 332, 333.
(The examples use max-heaps.)
Square array A(n,k) begins:
  1, 1,  1,   1,    1,     1,     1,     1,      1, ...
  0, 1,  2,   3,    4,     5,     6,     7,      8, ...
  0, 1,  3,   6,   10,    15,    21,    28,     36, ...
  0, 1,  5,  14,   30,    55,    91,   140,    204, ...
  0, 1,  7,  25,   65,   140,   266,   462,    750, ...
  0, 1, 11,  53,  173,   448,   994,  1974,   3606, ...
  0, 1, 16, 100,  400,  1225,  3136,  7056,  14400, ...
  0, 1, 26, 222, 1122,  4147, 12428, 32028,  73644, ...
  0, 1, 36, 386, 2336, 10036, 34242, 98922, 251922, ...

Alois P. Heinz, Antidiagonals n = 0..200, flattened
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Columns k=0-2 give: A000007, A000012, A091980(n+1).
Rows n=0-6 give: A000012, A001477, A000217, A000330, A001296, A207361, A001249(k-1).
Main diagonal gives A373450.
Cf. A373451.

A:= proc(n, k) option remember; `if`(n=0, 1,
     (g-> (f-> add(A(f, j)*A(n-1-f, j), j=1..k)
             )(min(g-1, n-g/2)))(2^ilog2(n)))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..12);

A[n_, k_] := A[n, k] = If[n == 0, 1,
   Function[g, Function[f, Sum[A[f, j]*A[n-1-f, j], {j, 1, k}]][
   Min[g-1, n-g/2]]][2^(Length[IntegerDigits[n, 2]]-1)]];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Jun 08 2024, after Alois P. Heinz *)

A(n,k) = Sum_{j=0..k} binomial(k,j) * A373451(n,k-j).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica