login
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, 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).
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
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, May 12 2007
STATUS
approved