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.

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

Author

Emeric Deutsch, May 13 2007

Keywords

• nonn
• easy

Examples

			a(4)=7 because from the 8 Fibonacci binary words of length 4 only 0110 does not qualify.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..5560
• Michael A. Allen, Combinations without specified separations and restricted-overlap tiling with combs, arXiv:2210.08167 [math.CO], 2022.
• Index entries for linear recurrences with constant coefficients, signature (1,1,-1,1).

Crossrefs

Cf. A130136.

Programs

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

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

a(n) = A124280(n)+A124280(n-1)+A124280(n-3). - R. J. Mathar, Mar 14 2025