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

Author

R. H. Hardin, Aug 12 2009

Keywords

• nonn
• easy

Examples

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

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).

Crossrefs

Cf. A171861 (essentially the same sequence).

Programs

Mathematica

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

Formula

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

Extensions

Edited by Alois P. Heinz, Oct 11 2017