login
A164398
Number of binary strings of length n with no substrings equal to 0001 or 1000.
2
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
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
KEYWORD
nonn
AUTHOR
R. H. Hardin, Aug 14 2009
STATUS
approved