|
|
A277751
|
|
Number T(n,k) of binary words of length n containing exactly k (possibly overlapping) occurrences of the subword 01101; triangle T(n,k), n>=0, k=0..max(0,floor((n-2)/3)), read by rows.
|
|
5
|
|
|
1, 2, 4, 8, 16, 31, 1, 60, 4, 116, 12, 225, 30, 1, 436, 72, 4, 845, 166, 13, 1637, 375, 35, 1, 3172, 828, 92, 4, 6146, 1802, 230, 14, 11909, 3872, 562, 40, 1, 23075, 8243, 1333, 113, 4, 44711, 17404, 3106, 300, 15, 86633, 36501, 7114, 778, 45, 1, 167863, 76104
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
FORMULA
|
G.f. of column k=0: (x+1)*(x^2-x+1)/(x^5-2*x^4+x^3-2*x+1); g.f. of column k>0: x^5*(x^3*(x-1)^2)^(k-1)/(x^5+x^4-x^3+2*x-1)^(k+1).
Sum_{k>=0} k * T(n,k) = A001787(n-4) for n > 3.
|
|
EXAMPLE
|
Triangle T(n,k) begins:
: 1;
: 2;
: 4;
: 8;
: 16;
: 31, 1;
: 60, 4;
: 116, 12;
: 225, 30, 1;
: 436, 72, 4;
: 845, 166, 13;
: 1637, 375, 35, 1;
: 3172, 828, 92, 4;
|
|
MAPLE
|
b:= proc(n, t) option remember; expand(
`if`(n=0, 1, b(n-1, [2, 2, 2, 5, 2][t])+
`if`(t=5, x, 1)* b(n-1, [1, 3, 4, 1, 3][t])))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 1)):
seq(T(n), n=0..20);
# second Maple program:
gf:= k-> `if`(k=0, (x+1)*(x^2-x+1), x^5*(x^3*(x-1)^2)^(k-1))
/(x^5-2*x^4+x^3-2*x+1)^(k+1):
T:= (n, k)-> coeff(series(gf(k), x, n+1), x, n):
seq(seq(T(n, k), k=0..max(0, floor((n-2)/3))), n=0..20);
|
|
MATHEMATICA
|
b[n_, t_] := b[n, t] = Expand[
If[n==0, 1, b[n-1, {2, 2, 2, 5, 2}[[t]]] +
If[t==5, x, 1]* b[n-1, {1, 3, 4, 1, 3}[[t]]]]];
T[n_] := CoefficientList[b[n, 1], x];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|