A164443 Number of binary strings of length n with no substrings equal to 0000, 0111 or 1110.

1, 2, 4, 8, 13, 22, 37, 64, 110, 190, 329, 570, 988, 1713, 2971, 5153, 8938, 15504, 26894, 46652, 80926, 140381, 243517, 422426, 732778, 1271143, 2205040, 3825063, 6635303, 11510202, 19966647, 34635969, 60082715, 104224965, 180798144, 313628975, 544049468

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

Formula

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

Crossrefs

Sequence in context: A164507 A164414 A164411 * A074467 A018066 A164509

Adjacent sequences: A164440 A164441 A164442 * A164444 A164445 A164446

Keyword

nonn,easy

Author

R. H. Hardin, Aug 14 2009

Extensions

a(0)-a(3) prepended by Alois P. Heinz, Apr 03 2024

Status

approved