A129709 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and having k 011 subwords (0<=k<=floor(n/3)). A Fibonacci binary word is a binary word having no 00 subword.

1, 2, 3, 4, 1, 5, 3, 6, 7, 7, 13, 1, 8, 22, 4, 9, 34, 12, 10, 50, 28, 1, 11, 70, 58, 5, 12, 95, 108, 18, 13, 125, 188, 50, 1, 14, 161, 308, 121, 6, 15, 203, 483, 261, 25, 16, 252, 728, 520, 80, 1, 17, 308, 1064, 968, 220, 7, 18, 372, 1512, 1710, 536, 33, 19, 444, 2100

Offset: 0

Author

Emeric Deutsch, May 12 2007

Keywords

• nonn
• tabf

Comments

Also number of Fibonacci binary words of length n and having k 110 subwords. Row n has 1+floor(n/3) terms. Row sums are the Fibonacci numbers (A000045). T(n,0)=n+1. Sum(k*T(n,k), k>=0)=A023610(n-3).

Examples

			T(7,2)=4 because we have 1011011,0111011,0110110 and 0110111.
Triangle starts:
1;
2;
3;
4,1;
5,3;
6,7;
7,13,1;
8,22,4;
9,34,12;
10,50,28,1;
		

Crossrefs

Cf. A000045, A023610.

Programs

Maple

G:=(1+z)/(1-z-z^2+z^3-t*z^3): Gser:=simplify(series(G,z=0,23)): for n from 0 to 20 do P[n]:=sort(coeff(Gser,z,n)) od: for n from 0 to 20 do seq(coeff(P[n],t,j),j=0..floor(n/3)) od; # yields sequence in triangular form

Formula

G.f.=G(t,z)=(1+z)/(1-z-z^2+z^3-tz^3).