A164482 Number of binary strings of length n with no substrings equal to 0001, 0110, or 1110.

1, 2, 4, 8, 13, 20, 29, 41, 57, 78, 106, 143, 192, 257, 343, 457, 608, 808, 1073, 1424, 1889, 2505, 3321, 4402, 5834, 7731, 10244, 13573, 17983, 23825, 31564, 41816, 55397, 73388, 97221, 128793, 170617, 226022, 299418, 396647, 525448, 696073, 922103, 1221529

Offset

0,2

Links

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

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

Formula

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

a(n) = A000931(n+13) - 8 for n >= 2. - Greg Dresden, May 18 2020

Crossrefs

Sequence in context: A056133 A172131 A173721 * A359850 A349216 A247587

Adjacent sequences: A164479 A164480 A164481 * A164483 A164484 A164485

Keyword

nonn

Author

R. H. Hardin, Aug 14 2009

Extensions

Edited by Alois P. Heinz, Oct 19 2018

Status

approved