A164397 Number of binary strings of length n with no substrings equal to 0001 or 0111.

1, 2, 4, 8, 14, 24, 41, 68, 112, 184, 300, 488, 793, 1286, 2084, 3376, 5466, 8848, 14321, 23176, 37504, 60688, 98200, 158896, 257105, 416010, 673124, 1089144, 1762278, 2851432, 4613721, 7465164, 12078896, 19544072, 31622980, 51167064, 82790057, 133957134

Offset: 0

Author

R. H. Hardin, Aug 14 2009

Keywords

• nonn
• easy

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..2000 (first 500 terms from R. H. Hardin)
• Index entries for linear recurrences with constant coefficients, signature (2,0,0,-2,0,1).

Crossrefs

Cf. A178982.

Programs

Magma

I:=[14,24,41,68,112,184]; [n le 6 select I[n] else 2*Self(n-1)-2*Self(n-4)+Self(n-6): n in [1..40]]; // Vincenzo Librandi, Sep 19 2017

Mathematica

LinearRecurrence[{2,0,0,-2,0,1},{14,24,41,68,112,184},40] (* Harvey P. Dale, Jan 23 2012 *)
CoefficientList[Series[-1 (14 - 4 x - 7 x^2 - 14 x^3 + 4 x^4 + 8 x^5) / ((1 + x + x^2) (x^2 + x - 1) (x - 1)^2), {x, 0, 33}], x] (* Vincenzo Librandi, Sep 19 2017 *)

PARI

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

Formula

G.f.: -1/((x^2+x+1)*(x^2+x-1)*(x-1)^2). - R. J. Mathar, Nov 30 2011

Extensions

Edited by Alois P. Heinz, Oct 27 2017