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.

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,8

Comments

These heaps may contain repeated elements.

Links

Alois P. Heinz, Antidiagonals n = 0..200, flattened

Eric Weisstein's World of Mathematics, Heap

Wikipedia, Binary heap

Formula

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

Example

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

Maple

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

Mathematica

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

Crossrefs

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.

Sequence in context: A339649 A349841 A339779 * A373424 A277504 A167763

Adjacent sequences: A373446 A373447 A373448 * A373450 A373451 A373452

Keyword

nonn,tabl

Author

Alois P. Heinz, Jun 05 2024

Status

approved