cp's OEIS Frontend

A164413 Number of binary strings of length n with no substrings equal to 0000, 0001 or 1001.

%I A164413 #29 Oct 27 2017 17:54:50
%S A164413 1,2,4,8,13,22,36,58,94,152,246,398,644,1042,1686,2728,4414,7142,
%T A164413 11556,18698,30254,48952,79206,128158,207364,335522,542886,878408,
%U A164413 1421294,2299702,3720996,6020698,9741694,15762392,25504086,41266478,66770564,108037042
%N A164413 Number of binary strings of length n with no substrings equal to 0000, 0001 or 1001.
%C A164413 Essentially the same as A022112. - _R. J. Mathar_, Nov 30 2011
%H A164413 David A. Corneth, <a href="/A164413/b164413.txt">Table of n, a(n) for n = 0..1999</a> (terms n = 4..500 from R. H. Hardin)
%H A164413 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,1).
%F A164413 From _Colin Barker_, Oct 27 2017: (Start)
%F A164413 G.f.: -(x^2+1)*(x^2-x+1)*(x+1)^2/(x^2+x-1).
%F A164413 a(n) = 2*(((1 - sqrt(5))/2)^n + ((1 + sqrt(5))/2)^n) for n>4.
%F A164413 a(n) = a(n-1) + a(n-2) for n>6.
%F A164413 (End)
%o A164413 (PARI) Vec(-(x^2+1)*(x^2-x+1)*(x+1)^2/(x^2+x-1) + O(x^50)) \\ _Colin Barker_, Oct 27 2017
%o A164413 (PARI) first(n) = {my(start = [1, 2, 4, 8, 13, 22, 36]); if(n <= 7, return(vector(n+1, i, start[i]))); res = concat(start, vector(n-7)); for(i=8, n,
%o A164413 res[i] = res[i-1] + res[i-2]); res} \\ _David A. Corneth_, Oct 27 2017
%K A164413 nonn,easy
%O A164413 0,2
%A A164413 _R. H. Hardin_, Aug 14 2009