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

13, 22, 36, 56, 89, 138, 212, 328, 501, 766, 1172, 1784, 2721, 4146, 6308, 9608, 14621, 22246, 33860, 51512, 78377, 119258, 181428, 276040, 419973, 638926, 972084, 1478904, 2249969, 3423106, 5207812, 7923080, 12054061, 18338742, 27900260

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

Formula

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

Prog

(PARI) a(n)=([0, 1, 0, 0, 0; 0, 0, 1, 0, 0; 0, 0, 0, 1, 0; 0, 0, 0, 0, 1; 2, -3, 0, 0, 2]^(n-4)*[13; 22; 36; 56; 89])[1, 1] \\ Charles R Greathouse IV, Jun 05 2026

Crossrefs

Sequence in context: A336263 A380725 A059408 * A164504 A162245 A159302

Adjacent sequences: A164452 A164453 A164454 * A164456 A164457 A164458

Keyword

nonn,easy

Author

R. H. Hardin, Aug 14 2009

Status

approved