A129708 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and having k 010 subwords (n>=0, 0<=k<=floor((n-1)/2)). A Fibonacci binary word is a binary word having no 00 subword.

1, 2, 3, 4, 1, 6, 2, 9, 3, 1, 13, 6, 2, 19, 11, 3, 1, 28, 18, 7, 2, 41, 30, 14, 3, 1, 60, 50, 24, 8, 2, 88, 81, 43, 17, 3, 1, 129, 130, 77, 30, 9, 2, 189, 208, 132, 57, 20, 3, 1, 277, 330, 224, 108, 36, 10, 2, 406, 520, 379, 193, 72, 23, 3, 1, 595, 816, 633, 342, 143, 42, 11, 2, 872

Offset

0,2

Comments

Row n has floor((n+1)/2) terms (n>=1). Row sums are the Fibonacci numbers (A000045). T(n,0)=A000930(n+2). Sum(k*T(n,k), k>=0)=A001629(n-1).

Links

G. C. Greubel, Table of n, a(n) for the first 100 rows, flattened

Formula

G.f.: G(t,z) = (1+z+z^2-tz^2)/(1-z-tz^2+tz^3-z^3). Row generating polynomials P[n] are given by P[n](t)=Q[n](t,1), where Q[0]=1, Q[1]=1+x, Q[n](t,x)=Q[n-1](t,1)+xQ[n-2](t,t) for n>=2.

Example

T(7,2)=3 because we have 1101010, 1010101 and 0101011.
Triangle starts:
1;
2;
3;
4,1;
6,2;
9,3,1;
13,6,2;
19,11,3,1;

Maple

Q[0]:=1: Q[1]:=1+x: for n from 2 to 30 do Q[n]:=expand(subs(x=1, Q[n-1])+x*subs(x=t, Q[n-2])) od: for n from 0 to 18 do P[n]:=subs(x=1, Q[n]) od; 1; for n from 1 to 18 do seq(coeff(P[n], t, j), j=0..floor((n-1)/2)) od; # yields sequence in triangular form

Mathematica

Flatten[CoefficientList[CoefficientList[Series[(1 + z + z^2 - t*z^2)/(1 - z - t*z^2 + t*z^3 - z^3), {z, 0, 20}, {t, 0, 20}], z], t]] (* G. C. Greubel, May 02 2017 *)

Crossrefs

Cf. A000045, A000930, A001629.

Sequence in context: A071439 A100941 A082119 * A071518 A330342 A065338

Adjacent sequences: A129705 A129706 A129707 * A129709 A129710 A129711

Keyword

nonn,tabf

Author

Emeric Deutsch, May 12 2007

Status

approved