login
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.
3
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
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
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Jun 05 2024
STATUS
approved