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
Alois P. Heinz, Rows n = 0..200, flattened
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap
FORMULA
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]];
T /@ Range[0, 14] // Flatten (* Jean-François Alcover, Oct 04 2019, after Alois P. Heinz *)
CROSSREFS
Columns k=0-10 give: A000012, A110654, A114220 (for n>0), A326504, A326505, A326506, A326507, A326508, A326509, A326510, A326511.
Row sums give A091980(n+1).
T(2n,n) gives A309050.
Rows reversed converge to A000108.
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Jul 09 2019
STATUS
approved