A164465 Number of binary strings of length n with no substrings equal to 0001 0100 or 1010.

13, 21, 35, 59, 99, 165, 274, 455, 756, 1256, 2086, 3464, 5752, 9551, 15859, 26333, 43724, 72600, 120546, 200156, 332341, 551822, 916250, 1521349, 2526060, 4194290, 6964232, 11563465, 19200067, 31879940, 52933699, 87891523, 145935764

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

Formula

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

Mathematica

LinearRecurrence[{2, -1, 1, 0, -1, 1, -1}, {13, 21, 35, 59, 99, 165, 274}, 40] (* Harvey P. Dale, Mar 17 2021 *)

Crossrefs

Sequence in context: A164496 A164459 A164453 * A164471 A164477 A164423

Adjacent sequences: A164462 A164463 A164464 * A164466 A164467 A164468

Keyword

nonn,easy

Author

R. H. Hardin, Aug 14 2009

Status

approved