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

13, 20, 31, 47, 70, 104, 154, 227, 334, 491, 721, 1058, 1552, 2276, 3337, 4892, 7171, 10511, 15406, 22580, 33094, 48503, 71086, 104183, 152689, 223778, 327964, 480656, 704437, 1032404, 1513063, 2217503, 3249910, 4762976, 6980482, 10230395

Offset

4,1

Links

R. H. Hardin, Table of n, a(n) for n = 4..500

Index entries for linear recurrences with constant coefficients, signature (2,-1,1,-1).

Formula

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

a(n) = a(n-1) + a(n-3) + 3 for n>6. - Greg Dresden, Feb 09 2020

a(n) = b(n+2) + b(n+1) + 2*b(n) - 3, where b(n) = A000930(n). - G. C. Greubel, Feb 09 2020

Maple

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

Mathematica

LinearRecurrence[{2, -1, 1, -1}, {13, 20, 31, 47}, 40] (* G. C. Greubel, Feb 09 2020 *)

Prog

(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
(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
(Sage)
def A164464_list(prec):
    P.<x> = PowerSeriesRing(ZZ, prec)
    return P( x^4*(13-6*x+4*x^2-8*x^3)/((1-x)*(1-x-x^3)) ).list()
a=A164464_list(40); a[4:] # G. C. Greubel, Feb 09 2020
(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

Crossrefs

Cf. A000930.

Sequence in context: A164483 A164468 A164489 * A164467 A164505 A164484

Adjacent sequences: A164461 A164462 A164463 * A164465 A164466 A164467

Keyword

nonn

Author

R. H. Hardin, Aug 14 2009

Status

approved