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,2

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).

Links

Table of n, a(n) for n=0..80.

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)].

Example

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;

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;

Crossrefs

Cf. A000045, A052952.

Sequence in context: A116633 A263232 A134666 * A051720 A022693 A174498

Adjacent sequences: A129709 A129710 A129711 * A129713 A129714 A129715

Keyword

nonn,tabf

Author

Emeric Deutsch, May 12 2007

Status

approved