cp's OEIS Frontend

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.

%I A130137 #19 Mar 14 2025 12:33:51
%S A130137 1,2,3,5,7,11,16,25,37,57,85,130,195,297,447,679,1024,1553,2345,3553,
%T A130137 5369,8130,12291,18605,28135,42579,64400,97449,147405,223033,337389,
%U A130137 510466,772227,1168337,1767487,2674063,4045440,6120353,9259217,14008193
%N 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.
%H A130137 Michael De Vlieger, <a href="/A130137/b130137.txt">Table of n, a(n) for n = 0..5560</a>
%H A130137 Michael A. Allen, <a href="https://arxiv.org/abs/2210.08167">Combinations without specified separations and restricted-overlap tiling with combs</a>, arXiv:2210.08167 [math.CO], 2022.
%H A130137 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,-1,1).
%F A130137 G.f.: (1+z+z^3)/(1-z-z^2+z^3-z^4).
%F A130137 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.
%F A130137 a(n) = A130136(n,0).
%F A130137 a(n) = A124280(n)+A124280(n-1)+A124280(n-3). - _R. J. Mathar_, Mar 14 2025
%e A130137 a(4)=7 because from the 8 Fibonacci binary words of length 4 only 0110 does not qualify.
%p A130137 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);
%t A130137 LinearRecurrence[{1, 1, -1, 1}, {1, 2, 3, 5}, 40] (* _Jean-François Alcover_, Aug 25 2021 *)
%Y A130137 Cf. A130136.
%K A130137 nonn,easy
%O A130137 0,2
%A A130137 _Emeric Deutsch_, May 13 2007