A129719 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and having k 0's in odd positions (0 <= k <= ceiling(n/2)). A Fibonacci binary word is a binary word having no 00 subword.

1, 1, 1, 2, 1, 2, 2, 1, 4, 3, 1, 4, 5, 3, 1, 8, 8, 4, 1, 8, 12, 9, 4, 1, 16, 20, 13, 5, 1, 16, 28, 25, 14, 5, 1, 32, 48, 38, 19, 6, 1, 32, 64, 66, 44, 20, 6, 1, 64, 112, 104, 63, 26, 7, 1, 64, 144, 168, 129, 70, 27, 7, 1, 128, 256, 272, 192, 96, 34, 8, 1, 128, 320, 416, 360, 225, 104, 35

Offset: 0

Author

Emeric Deutsch, May 13 2007

Keywords

• nonn
• tabf

Comments

Row n has 1+ceiling(n/2) terms.

Examples

			T(6,2)=4 because we have 110101, 011101, 010110 and 010111.
Triangle starts:
  1;
  1, 1;
  2, 1;
  2, 2, 1;
  4, 3, 1;
  4, 5, 3, 1;
  8, 8, 4, 1;
		

Crossrefs

Cf. A000045, A129720, A129721.

Programs

Maple

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

Formula

G.f.: G(t,z) = (1+z)(1+tz-tz^2)/(1-(2+t)z^2+tz^4). The trivariate generating function H(t,s,z), where t marks number of 0's in odd position and s marks number of 0's in even position, is given by H(t,s,z) = (1+(1+t)z-tsz^3)/(1-(1+t+s)z^2+tsz^4).

Row sums are the Fibonacci numbers (A000045).

T(2n,k) = T(2n-1,k) + T(2n-2,k) (n >= 1).

T(2n,k) = A129721(2n,k).

Sum_{k=0..ceiling(n/2)} k*T(n,k) = A129720(n).