A164495 Number of binary strings of length n with no substrings equal to 0010 0101 or 1011.

13, 22, 37, 62, 105, 178, 301, 508, 857, 1446, 2441, 4122, 6961, 11754, 19845, 33504, 56565, 95502, 161245, 272246, 459657, 776074, 1310301, 2212276, 3735153, 6306350, 10647505, 17977010, 30351969, 51245554, 86521797, 146081400, 246640477

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

Formula

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

a(4)=13, a(5)=22, a(6)=37, a(7)=62, a(8)=105, a(9)=178, a(n)=2*a(n-1)- a(n-2)+ a(n-4)+a(n-6). - Harvey P. Dale, Mar 07 2015

Mathematica

LinearRecurrence[{2, -1, 0, 1, 0, 1}, {13, 22, 37, 62, 105, 178}, 40] (* Harvey P. Dale, Mar 07 2015 *)

Crossrefs

Sequence in context: A164435 A164425 A164501 * A164427 A164456 A164410

Adjacent sequences: A164492 A164493 A164494 * A164496 A164497 A164498

Keyword

nonn,easy

Author

R. H. Hardin, Aug 14 2009

Status

approved