A373449 -id:A373449 - cp's OEIS frontend

A373451 Number T(n,k) of (binary) heaps of length n whose element set equals [k]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 1, 3, 2, 0, 1, 5, 7, 3, 0, 1, 9, 23, 23, 8, 0, 1, 14, 55, 92, 70, 20, 0, 1, 24, 147, 386, 502, 320, 80, 0, 1, 34, 281, 1004, 1861, 1880, 985, 210, 0, 1, 54, 633, 3128, 8113, 12008, 10237, 4690, 896, 0, 1, 79, 1241, 8039, 27456, 54900, 66730, 48650, 19600, 3360

Offset: 0

Alois P. Heinz, Jun 05 2024

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

T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k<=n. T(n,k) = 0 for k>n.

			T(4,1) = 1: 1111.
T(4,2) = 5: 2111, 2121, 2211, 2212, 2221.
T(4,3) = 7: 3121, 3211, 3212, 3221, 3231, 3312, 3321.
T(4,4) = 3: 4231, 4312, 4321.
(The examples use max-heaps.)
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,  1;
  0, 1,  3,   2;
  0, 1,  5,   7,    3;
  0, 1,  9,  23,   23,    8;
  0, 1, 14,  55,   92,   70,    20;
  0, 1, 24, 147,  386,  502,   320,    80;
  0, 1, 34, 281, 1004, 1861,  1880,   985,  210;
  0, 1, 54, 633, 3128, 8113, 12008, 10237, 4690, 896;
  ...

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

Columns k=0-4 give A000007, A057427, A091980(n+1)-2, A376962, A376963.
Row sums give A373452.
Row maxima give A373608.
Main diagonal gives A056971.
First lower diagonal gives A373496.
T(2n,n) gives A373500.
Antidiagonal sums give A373632.
Antidiagonal maxima give A373897.
Cf. A019590, A373449.

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):
seq(seq(T(n, k), k=0..n), n=0..12);

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}];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Sep 20 2024, after Alois P. Heinz *)

T(n,k) = Sum_{j=0..k} binomial(k,j) * (-1)^j * A373449(n,k-j).

Sum_{k=0..n} (-1)^k * T(n,n-k) = A019590(n+1).

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

Original entry on oeis.org

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

Offset: 0

Alois P. Heinz, Jun 05 2024

nonn

These heaps may contain repeated elements.

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

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

Main diagonal of A373449.
Cf. A056971 (distinct elements), A373452 (gap-free element sets including 1).
Cf. A007318, A373451.

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

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

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

cp's OEIS Frontend

A373451 Number T(n,k) of (binary) heaps of length n whose element set equals [k]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula