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

Author

Alois P. Heinz, Jun 05 2024

Keywords

• nonn
• tabl

Comments

These heaps may contain repeated elements.

Examples

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

Links

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

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.

Programs

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

Formula

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