A164317 Number of binary strings of length n with no substrings equal to 000, 010, or 111.

1, 2, 4, 5, 6, 7, 9, 11, 13, 16, 20, 24, 29, 36, 44, 53, 65, 80, 97, 118, 145, 177, 215, 263, 322, 392, 478, 585, 714, 870, 1063, 1299, 1584, 1933, 2362, 2883, 3517, 4295, 5245, 6400, 7812, 9540, 11645, 14212, 17352, 21185, 25857, 31564, 38537, 47042, 57421

Offset

0,2

Links

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

Lukas Fleischer, Jeffrey Shallit, Words With Few Palindromes, Revisited, arXiv:1911.12464 [cs.FL], 2019.

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

Formula

G.f.: -(x^2+x+1)*(x^3+2*x^2+x+1)/(x^4+x^3-1). - R. J. Mathar, Nov 28 2011

Example

All solutions for N=8
00110110 00110011 10110110 10110011 10011001 10011011 01100110 01101100
01101101 11001100 11001101 11011001 11011011

Mathematica

CoefficientList[Series[-(x^2 + x + 1) (x^3 + 2 x^2 + x + 1)/(x^4 + x^3 - 1), {x, 0, 50}], x] (* Michael De Vlieger, Feb 17 2020 *)

Crossrefs

Sequence in context: A026426 A026480 A126424 * A138620 A260820 A248554

Adjacent sequences: A164314 A164315 A164316 * A164318 A164319 A164320

Keyword

nonn,easy

Author

R. H. Hardin, Aug 12 2009

Extensions

Edited by Alois P. Heinz, Oct 11 2017

Status

approved