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
Examples
All solutions for n=6: 101100 101101 101110 101111 011011 011100 011101 011110 011111 111011 110110 110111 111100 111101 111110 111111.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..2000 (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,0,1).
Programs
-
Mathematica
LinearRecurrence[{1, 0, 1}, {1, 2, 4}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 15 2012, edited by Greg Dresden, Jul 02 2021 *)
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
Extensions
Edited by Alois P. Heinz, Oct 11 2017