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,2

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

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 A091980 A274113

Adjacent sequences: A130134 A130135 A130136 * A130138 A130139 A130140

Keyword

nonn,easy

Author

Emeric Deutsch, May 13 2007

Status

approved