A164464 - OEIS

%I #20 Sep 08 2022 08:45:47

%S 13,20,31,47,70,104,154,227,334,491,721,1058,1552,2276,3337,4892,7171,

%T 10511,15406,22580,33094,48503,71086,104183,152689,223778,327964,

%U 480656,704437,1032404,1513063,2217503,3249910,4762976,6980482,10230395

%N Number of binary strings of length n with no substrings equal to 0001, 0100, or 0111.

%H R. H. Hardin, <a href="/A164464/b164464.txt">Table of n, a(n) for n = 4..500</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,1,-1).

%F G.f.: x^4*(13 - 6*x + 4*x^2 - 8*x^3)/( (1-x)*(1-x-x^3) ). - _R. J. Mathar_, Jan 19 2011

%F a(n) = a(n-1) + a(n-3) + 3 for n>6. - _Greg Dresden_, Feb 09 2020

%F a(n) = b(n+2) + b(n+1) + 2*b(n) - 3, where b(n) = A000930(n). - _G. C. Greubel_, Feb 09 2020

%p m:=40; S:=series(x^4*(13-6*x+4*x^2-8*x^3)/((1-x)*(1-x-x^3)), x, m+1): seq(coeff(S, x, j), j=4..m); # _G. C. Greubel_, Feb 09 2020

%t LinearRecurrence[{2,-1,1,-1}, {13,20,31,47}, 40] (* _G. C. Greubel_, Feb 09 2020 *)

%o (PARI) Vec( x^4*(13-6*x+4*x^2-8*x^3)/((1-x)*(1-x-x^3)) +O('x^40) ) \\ _G. C. Greubel_, Feb 09 2020

%o (Magma) R<x>:=PowerSeriesRing(Integers(), 40); Coefficients(R!( x^4*(13-6*x+4*x^2-8*x^3)/((1-x)*(1-x-x^3)) )); // _G. C. Greubel_, Feb 09 2020

%o (Sage)

%o def A164464_list(prec):

%o     P.<x> = PowerSeriesRing(ZZ, prec)

%o     return P( x^4*(13-6*x+4*x^2-8*x^3)/((1-x)*(1-x-x^3)) ).list()

%o a=A164464_list(40); a[4:] # _G. C. Greubel_, Feb 09 2020

%o (GAP) a:=[13,20,31,47];; for n in [5..40] do a[n]:=2*a[n-1]-a[n-2]+a[n-3] -a[n-4]; od; a; # _G. C. Greubel_, Feb 09 2020

%Y Cf. A000930.

%K nonn

%O 4,1

%A _R. H. Hardin_, Aug 14 2009