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
Examples
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;
Programs
-
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
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).
Comments