login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A164464 Number of binary strings of length n with no substrings equal to 0001, 0100, or 0111. 1
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 24 21:50 EDT 2021. Contains 345433 sequences. (Running on oeis4.)