A164459 Number of binary strings of length n with no substrings equal to 0001 0011 or 1100.

13, 21, 35, 58, 96, 159, 264, 439, 730, 1215, 2023, 3369, 5612, 9349, 15576, 25952, 43241, 72050, 120054, 200043, 333329, 555423, 925499, 1542157, 2569695, 4281884, 7134907, 11888905, 19810501, 33010271, 55005074, 91655056, 152724992

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,0,0,-2,1,-1,1).

Formula

G.f.: -x^4*(13-5*x-7*x^2-12*x^3+6*x^4-4*x^5+8*x^6) / ( (x^5+x^4+2*x^3+x^2-1)*(x-1)^2 ). - R. J. Mathar, Jan 19 2011

a(n) = 2*a(n-1)-2*a(n-4)+a(n-5)-a(n-6)+a(n-7). [Harvey P. Dale, May 06 2011]

Mathematica

LinearRecurrence[{2, 0, 0, -2, 1, -1, 1}, {13, 21, 35, 58, 96, 159, 264}, 40] (*Harvey P. Dale, May 06 2011 *)

Crossrefs

Sequence in context: A034292 A163113 A164496 * A164453 A164465 A164471

Adjacent sequences: A164456 A164457 A164458 * A164460 A164461 A164462

Keyword

nonn,easy

Author

R. H. Hardin, Aug 14 2009

Status

approved