A164437 Number of binary strings of length n with no substrings equal to 0000, 0101, or 1111.

1, 2, 4, 8, 13, 22, 37, 62, 104, 174, 292, 490, 821, 1376, 2308, 3870, 6487, 10876, 18237, 30576, 51261, 85946, 144102, 241600, 405064, 679140, 1138659, 1909078, 3200774, 5366466, 8997477, 15085240, 25292069, 42404978, 71096617, 119201278, 199854120, 335077546

Offset

0,2

Links

Alois P. Heinz, Table of n, a(n) for n = 0..2000 (terms n=4..500 from R. H. Hardin)

Index entries for linear recurrences with constant coefficients, signature (0,0,2,3,2,1).

Formula

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

Crossrefs

Sequence in context: A164441 A338761 A023600 * A164428 A164507 A164414

Adjacent sequences: A164434 A164435 A164436 * A164438 A164439 A164440

Keyword

nonn,easy

Author

R. H. Hardin, Aug 14 2009

Extensions

a(0)-a(3) from Alois P. Heinz, Jun 11 2021

Status

approved