OFFSET
0,9
COMMENTS
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.
LINKS
Alois P. Heinz, Rows n = 0..150, flattened
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap
FORMULA
EXAMPLE
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;
...
MAPLE
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);
MATHEMATICA
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 *)
CROSSREFS
KEYWORD
AUTHOR
Alois P. Heinz, Jun 05 2024
STATUS
approved