A129718 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and having k runs of 1's (n >= 0, 0 <= k <= floor((n+1)/2)). A Fibonacci binary word is a binary word having no 00 subword. A run of 1's is a maximal subword of the form 11..1.

1, 1, 1, 0, 3, 0, 4, 1, 0, 4, 4, 0, 4, 8, 1, 0, 4, 12, 5, 0, 4, 16, 13, 1, 0, 4, 20, 25, 6, 0, 4, 24, 41, 19, 1, 0, 4, 28, 61, 44, 7, 0, 4, 32, 85, 85, 26, 1, 0, 4, 36, 113, 146, 70, 8, 0, 4, 40, 145, 231, 155, 34, 1, 0, 4, 44, 181, 344, 301, 104, 9, 0, 4, 48, 221, 489, 532, 259, 43, 1

Offset

0,5

Comments

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

Row sums are the Fibonacci numbers (A000045).

T(n,k) = A129717(n,k-1) (since in each word the number of runs of 1's = 1 + the number of 101's).

Sum_{k=0..floor((n+1)/2)} k*T(n,k) = A055244(n) (n >= 1).

Links

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

Formula

G.f. = G(t,z) = (1+z)(1-z+tz)/(1-z-tz^2).

T(n,k) = binomial(n-k,k-1) + 2*binomial(n-k-1,k-1) + binomial(n-k-2,k-1) for n >= 4 and 0 <= k < floor((n+1)/2).

Example

T(6,3)=5 because we have 110101, 101101, 101010, 101011 and 010101.
Triangle starts:
  1;
  1,  1;
  0,  3;
  0,  4,  1;
  0,  4,  4;
  0,  4,  8,  1;
  0,  4, 12,  5;

Maple

G:=(1+z)*(1-z+t*z)/(1-z-t*z^2): Gser:=simplify(series(G, z=0, 21)): for n from 0 to 18 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, A129717, A055244.

Sequence in context: A060034 A308216 A035544 * A127375 A238573 A346965

Adjacent sequences: A129715 A129716 A129717 * A129719 A129720 A129721

Keyword

nonn,tabf

Author

Emeric Deutsch, May 12 2007

Status

approved