login
A373451
Number T(n,k) of (binary) heaps of length n whose element set equals [k]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
10
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, 0, 1, 79, 1241, 8039, 27456, 54900, 66730, 48650, 19600, 3360
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
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap
FORMULA
T(n,k) = Sum_{j=0..k} binomial(k,j) * (-1)^j * A373449(n,k-j).
Sum_{k=0..n} (-1)^k * T(n,n-k) = A019590(n+1).
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
Columns k=0-2 give A000007, A057427, A091980(n+1)-2.
Row sums give A373452.
Row maxima give A373608.
Main diagonal gives A056971.
First lower diagonal gives A373496.
T(2n,n) gives A373500.
Antidiagonal sums give A373632.
Antidiagonal maxima give A373897.
Sequence in context: A008783 A139144 A360866 * A081576 A330785 A292717
KEYWORD
nonn,tabl,changed
AUTHOR
Alois P. Heinz, Jun 05 2024
STATUS
approved