|
|
A309049
|
|
Number T(n,k) of (binary) max-heaps on n elements from the set {0,1} containing exactly k 0's; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
|
|
18
|
|
|
1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 3, 3, 2, 1, 1, 1, 3, 4, 4, 2, 1, 1, 1, 4, 6, 6, 5, 2, 1, 1, 1, 4, 7, 8, 7, 5, 2, 1, 1, 1, 5, 10, 12, 11, 8, 5, 2, 1, 1, 1, 5, 11, 16, 17, 13, 9, 5, 2, 1, 1, 1, 6, 15, 23, 27, 24, 16, 10, 5, 2, 1, 1, 1, 6, 16, 27, 34, 34, 27, 18, 11, 5, 2, 1, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,8
|
|
COMMENTS
|
Also the number T(n,k) of (binary) min-heaps on n elements from the set {0,1} containing exactly k 1's.
The sequence of column k satisfies a linear recurrence with constant coefficients of order A063915(k).
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Heap
|
|
FORMULA
|
Sum_{k=0..n} k * T(n,k) = A309051(n).
Sum_{k=0..n} (n-k) * T(n,k) = A309052(n).
Sum_{k=0..2^n-1} T(2^n-1,k) = A003095(n+1).
Sum_{k=0..2^n-1} (2^n-1-k) * T(2^n-1,k) = A024358(n).
Sum_{k=0..n} (T(n,k) - T(n-1,k)) = A168542(n).
|
|
EXAMPLE
|
T(6,0) = 1: 111111.
T(6,1) = 3: 111011, 111101, 111110.
T(6,2) = 4: 110110, 111001, 111010, 111100.
T(6,3) = 4: 101001, 110010, 110100, 111000.
T(6,4) = 2: 101000, 110000.
T(6,5) = 1: 100000.
T(6,6) = 1: 000000.
T(7,4) = T(7,7-3) = A000108(3) = 5: 1010001, 1010010, 1100100, 1101000, 1110000.
Triangle T(n,k) begins:
1;
1, 1;
1, 1, 1;
1, 2, 1, 1;
1, 2, 2, 1, 1;
1, 3, 3, 2, 1, 1;
1, 3, 4, 4, 2, 1, 1;
1, 4, 6, 6, 5, 2, 1, 1;
1, 4, 7, 8, 7, 5, 2, 1, 1;
1, 5, 10, 12, 11, 8, 5, 2, 1, 1;
1, 5, 11, 16, 17, 13, 9, 5, 2, 1, 1;
1, 6, 15, 23, 27, 24, 16, 10, 5, 2, 1, 1;
1, 6, 16, 27, 34, 34, 27, 18, 11, 5, 2, 1, 1;
...
|
|
MAPLE
|
b:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> expand(
x^n+b(f)*b(n-1-f)))(min(g-1, n-g/2)))(2^ilog2(n)))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n)):
seq(T(n), n=0..14);
|
|
MATHEMATICA
|
b[n_] := b[n] = If[n == 0, 1, Function[g, Function[f, Expand[x^n + b[f]*b[n - 1 - f]]][Min[g - 1, n - g/2]]][2^Floor[Log[2, n]]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n]];
|
|
CROSSREFS
|
Columns k=0-10 give: A000012, A110654, A114220 (for n>0), A326504, A326505, A326506, A326507, A326508, A326509, A326510, A326511.
Cf. A000225, A000295, A003095, A024358, A056971, A063915, A137560, A168542, A202019, A309051, A309052.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|