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

1, 2, 2, 1, 3, 2, 5, 2, 1, 8, 3, 2, 13, 5, 2, 1, 21, 8, 3, 2, 34, 13, 5, 2, 1, 55, 21, 8, 3, 2, 89, 34, 13, 5, 2, 1, 144, 55, 21, 8, 3, 2, 233, 89, 34, 13, 5, 2, 1, 377, 144, 55, 21, 8, 3, 2, 610, 233, 89, 34, 13, 5, 2, 1, 987, 377, 144, 55, 21, 8, 3, 2, 1597, 610, 233, 89, 34, 13, 5, 2, 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)=F(n+1)-1=A000071(n+1).

Links

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

Formula

T(n,k)=F(n-2k+1) if 2k+1<n, where F(j) are the Fibonacci numbers (F(0)=0, F(1)=1); T(2k+1,k)=2; T(n,k)=0 if 2k>n. G.f.=G(t,z)=(1+z)(1-z^2)/[(1-z-z^2)(1-tz^2)].

Example

T(7,2)=3 because we have 0101110, 0101111 and 0101101.
Triangle starts:
1;
2;
2,1;
3,2;
5,2,1;
8,3,2;
13,5,2,1;

Maple

with(combinat): T:=proc(n, k) if n=2*k+1 then 2 elif n<2*k then 0 else fibonacci(n-2*k+1) fi end: for n from 0 to 18 do seq(T(n, k), k=0..floor(n/2)) od; # yields sequence in triangular form

Crossrefs

Cf. A000045, A000071.

Sequence in context: A367292 A323479 A276427 * A030454 A262985 A296786

Adjacent sequences: A129708 A129709 A129710 * A129712 A129713 A129714

Keyword

nonn,tabf

Author

Emeric Deutsch, May 12 2007

Status

approved