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

1, 2, 4, 5, 7, 11, 16, 23, 34, 50, 73, 107, 157, 230, 337, 494, 724, 1061, 1555, 2279, 3340, 4895, 7174, 10514, 15409, 22583, 33097, 48506, 71089, 104186, 152692, 223781, 327967, 480659, 704440, 1032407, 1513066, 2217506, 3249913, 4762979, 6980485, 10230398

Offset

0,2

Links

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

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

Formula

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

a(n) = 4 + Sum_{i=0..n-3} a(i) for n>2. - Greg Dresden, Jul 02 2021

Example

All solutions for n=6: 101100 101101 101110 101111 011011 011100 011101 011110 011111 111011 110110 110111 111100 111101 111110 111111.

Mathematica

LinearRecurrence[{1, 0, 1}, {1, 2, 4}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 15 2012, edited by Greg Dresden, Jul 02 2021 *)

Crossrefs

Sequence in context: A050134 A010065 A344654 * A323146 A250006 A257033

Adjacent sequences: A164313 A164314 A164315 * A164317 A164318 A164319

Keyword

easy,nonn

Author

R. H. Hardin, Aug 12 2009

Extensions

Edited by Alois P. Heinz, Oct 11 2017

Status

approved