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

Author

R. H. Hardin, Aug 14 2009

Keywords

• nonn

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).

Programs

Mathematica

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

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

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