A164398 Number of binary strings of length n with no substrings equal to 0001 or 1000.

14, 25, 45, 82, 150, 275, 505, 928, 1706, 3137, 5769, 10610, 19514, 35891, 66013, 121416, 223318, 410745, 755477, 1389538, 2555758, 4700771, 8646065, 15902592, 29249426, 53798081, 98950097, 181997602, 334745778, 615693475, 1132436853

Offset

4,1

Links

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

W. Kuszmaul, Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations, arXiv preprint arXiv:1509.08216 [cs.DM], 2015.

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

Formula

G.f.: -x^4*(-14+3*x+5*x^2+8*x^3) / ( (x-1)*(x^3+x^2+x-1) ). - R. J. Mathar, Nov 28 2011

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

a(n) = 2*a(n-1)-a(n-4). - Wesley Ivan Hurt, Apr 26 2021

Mathematica

LinearRecurrence[{2, 0, 0, -1}, {14, 25, 45, 82}, 50] (* G. C. Greubel, Sep 18 2017 *)

Prog

(PARI) x='x+O('x^50); Vec(-x^4*(-14+3*x+5*x^2+8*x^3)/((x-1)*(x^3+x^2+x-1) )) \\ G. C. Greubel, Sep 18 2017

Crossrefs

Sequence in context: A032608 A341171 A164403 * A174519 A079505 A039604

Adjacent sequences: A164395 A164396 A164397 * A164399 A164400 A164401

Keyword

nonn

Author

R. H. Hardin, Aug 14 2009

Status

approved