|
%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
|
