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

Comments

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

Links

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

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

Example

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;

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

Crossrefs

Cf. A000045, A129720, A129721.

Sequence in context: A035436 A242210 A035369 * A062602 A123148 A173410

Adjacent sequences: A129716 A129717 A129718 * A129720 A129721 A129722

Keyword

nonn,tabf

Author

Emeric Deutsch, May 13 2007

Status

approved