A129712 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and starting with exactly k 10's (0<=k<=floor(n/2)). A Fibonacci binary word is a binary word having no 00 subword.

1, 2, 2, 1, 4, 1, 6, 1, 1, 10, 2, 1, 16, 3, 1, 1, 26, 5, 2, 1, 42, 8, 3, 1, 1, 68, 13, 5, 2, 1, 110, 21, 8, 3, 1, 1, 178, 34, 13, 5, 2, 1, 288, 55, 21, 8, 3, 1, 1, 466, 89, 34, 13, 5, 2, 1, 754, 144, 55, 21, 8, 3, 1, 1, 1220, 233, 89, 34, 13, 5, 2, 1, 1974, 377, 144, 55, 21, 8, 3, 1, 1

Offset: 0

Author

Emeric Deutsch, May 12 2007

Keywords

• nonn
• tabf

Comments

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

Examples

			T(7,2)=2 because we have 1010110 and 1010111.
Triangle starts:
1;
2;
2,1;
4,1;
6,1,1;
10,2,1;
16,3,1,1;
26,5,2,1;
		

Crossrefs

Cf. A000045, A052952.

Programs

Maple

with(combinat): T:=proc(n,k) if k=0 and n=0 then 1 elif k=0 then 2*fibonacci(n) elif n=2*k or n=2*k+1 then 1 elif n>2*k+1 then fibonacci(n-2*k) else 0 fi end: for n from 0 to 18 do seq(T(n,k),k=0..floor(n/2)) od;

Formula

T(0,0)=1, T(n,0)=2F(n) for n>=1, T(2k,k)=T(2k+1,k)=1 for k>=1, T(n,k)=F(n-2k) for 1<=k<(n-1)/2. G.f.=G(t,z)=(1+z-z^2-t*z^3)/[(1-z-z^2)(1-t*z^2)].