A164317 Number of binary strings of length n with no substrings equal to 000, 010, or 111.
1, 2, 4, 5, 6, 7, 9, 11, 13, 16, 20, 24, 29, 36, 44, 53, 65, 80, 97, 118, 145, 177, 215, 263, 322, 392, 478, 585, 714, 870, 1063, 1299, 1584, 1933, 2362, 2883, 3517, 4295, 5245, 6400, 7812, 9540, 11645, 14212, 17352, 21185, 25857, 31564, 38537, 47042, 57421
Offset: 0
Examples
All solutions for N=8 00110110 00110011 10110110 10110011 10011001 10011011 01100110 01101100 01101101 11001100 11001101 11011001 11011011
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..5000 (first 500 terms from R. H. Hardin)
- Lukas Fleischer and Jeffrey Shallit, Words With Few Palindromes, Revisited, arXiv:1911.12464 [cs.FL], 2019.
- 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.
- N. H. Bong, C. Dalfó, M. A. Fiol, and D. Závacká, Some inner metric parameters of a digraph: iterated line digraphs and integer sequences, Bol. Soc. Mat. Mex. 31 (2025), 13.
- Index entries for linear recurrences with constant coefficients, signature (0,0,1,1).
Programs
-
Mathematica
CoefficientList[Series[-(x^2 + x + 1) (x^3 + 2 x^2 + x + 1)/(x^4 + x^3 - 1), {x, 0, 50}], x] (* Michael De Vlieger, Feb 17 2020 *)
Formula
G.f.: -(x^2+x+1)*(x^3+2*x^2+x+1)/(x^4+x^3-1). - R. J. Mathar, Nov 28 2011
Extensions
Edited by Alois P. Heinz, Oct 11 2017