login
A130137
Number of Fibonacci binary words of length n having no 0110 subword. A Fibonacci binary word is a binary word having no 00 subword.
5
1, 2, 3, 5, 7, 11, 16, 25, 37, 57, 85, 130, 195, 297, 447, 679, 1024, 1553, 2345, 3553, 5369, 8130, 12291, 18605, 28135, 42579, 64400, 97449, 147405, 223033, 337389, 510466, 772227, 1168337, 1767487, 2674063, 4045440, 6120353, 9259217, 14008193
OFFSET
0,2
FORMULA
G.f.: (1+z+z^3)/(1-z-z^2+z^3-z^4).
a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-4); a(0)=1, a(1)=2, a(2)=3, a(3)=5.
a(n) = A130136(n,0).
EXAMPLE
a(4)=7 because from the 8 Fibonacci binary words of length 4 only 0110 does not qualify.
MAPLE
a[0]:=1: a[1]:=2: a[2]:=3: a[3]:=5: for n from 4 to 45 do a[n]:=a[n-1]+a[n-2]-a[n-3]+a[n-4] od: seq(a[n], n=0..45);
MATHEMATICA
LinearRecurrence[{1, 1, -1, 1}, {1, 2, 3, 5}, 40] (* Jean-François Alcover, Aug 25 2021 *)
CROSSREFS
Cf. A130136.
Sequence in context: A271485 A018057 A355907 * A218022 A374151 A091980
KEYWORD
nonn,easy
AUTHOR
Emeric Deutsch, May 13 2007
STATUS
approved