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