A164315 Number of binary strings of length n with no substrings equal to 000 or 011.

1, 2, 4, 6, 9, 13, 18, 25, 34, 46, 62, 83, 111, 148, 197, 262, 348, 462, 613, 813, 1078, 1429, 1894, 2510, 3326, 4407, 5839, 7736, 10249, 13578, 17988, 23830, 31569, 41821, 55402, 73393, 97226, 128798, 170622, 226027, 299423, 396652, 525453, 696078, 922108

Offset

0,2

Links

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

Dominika Závacká, Cristina Dalfó, and Miquel Angel Fiol, Integer sequences from k-iterated line digraphs, CEUR: Proc. 24th Conf. Info. Tech. - Appl. and Theory (ITAT 2024) Vol 3792, 156-161. See p. 161, Table 2.

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

Formula

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

Example

All solutions for N=6
001001 001010 010010 010100 010101 100100 100101 101001 101010 110010
110100 110101 111001 111010 111100 111101 111110 111111

Mathematica

CoefficientList[Series[(x^2 + x + 1)/((x - 1) (x^3 + x^2 - 1)), {x, 0, 44}], x] (* Michael De Vlieger, Oct 11 2017 *)

Crossrefs

Cf. A171861 (essentially the same sequence).

Sequence in context: A088575 A177189 A026906 * A171861 A376876 A039900

Adjacent sequences: A164312 A164313 A164314 * A164316 A164317 A164318

Keyword

nonn,easy

Author

R. H. Hardin, Aug 12 2009

Extensions

Edited by Alois P. Heinz, Oct 11 2017

Status

approved