login
A329824
Number of length-n binary words having no palindromes of length > 5 as contiguous subwords.
1
2, 4, 8, 16, 32, 56, 84, 120, 164, 226, 312, 428, 584, 802, 1096, 1500, 2056, 2816, 3852, 5280, 7228, 9892, 13548, 18554, 25396, 34788, 47636, 65212, 89296, 122278, 167404, 229252, 313932, 429830, 588556, 805910, 1103420, 1510924, 2068960, 2832944, 3879100
OFFSET
1,1
COMMENTS
a(n) is asymptotically equal to c*alpha^n, where alpha = 1.36927381628918060784... is the positive real zero of the equation X^10-3X^4-2X^3-2X^2-2X-1, and c = 9.8315779... .
LINKS
G. Fici and L. Q. Zamboni, On the least number of palindromes contained in an infinite word, Theor. Comput. Sci. 481 (2013) 1-8.
Lukas Fleischer, Jeffrey Shallit, Words With Few Palindromes, Revisited, arxiv preprint arXiv:1911.12464 [cs.FL], November 27 2019.
FORMULA
a(n) = 3a(n-6) + 2a(n-7) + 2a(n-8) + 2a(n-9) + a(n-10) for n >= 20.
G.f.: 2*x*(1 + x)*(1 + x + x^2)*(1 + 2*x^2 + 3*x^3 + 6*x^4 + 8*x^5 + 8*x^6 + 14*x^7 + 12*x^8 + 15*x^9 + 11*x^10 + 8*x^11 + 5*x^12 + 4*x^13 + 2*x^15) / (1 - 3*x^6 - 2*x^7 - 2*x^8 - 2*x^9 - x^10). - Colin Barker, Nov 22 2019
EXAMPLE
For n=6 the 8 strings NOT enumerated are 000000, 001100, 010010, 011110, and their binary complements.
MATHEMATICA
Rest@ CoefficientList[Series[2 x (1 + x) (1 + x + x^2) (1 + 2 x^2 + 3 x^3 + 6 x^4 + 8 x^5 + 8 x^6 + 14 x^7 + 12 x^8 + 15 x^9 + 11 x^10 + 8 x^11 + 5 x^12 + 4 x^13 + 2 x^15)/(1 - 3 x^6 - 2 x^7 - 2 x^8 - 2 x^9 - x^10), {x, 0, 41}], x] (* Michael De Vlieger, Nov 22 2019 *)
PROG
(PARI) Vec(2*x*(1 + x)*(1 + x + x^2)*(1 + 2*x^2 + 3*x^3 + 6*x^4 + 8*x^5 + 8*x^6 + 14*x^7 + 12*x^8 + 15*x^9 + 11*x^10 + 8*x^11 + 5*x^12 + 4*x^13 + 2*x^15) / (1 - 3*x^6 - 2*x^7 - 2*x^8 - 2*x^9 - x^10) + O(x^40)) \\ Colin Barker, Nov 22 2019
CROSSREFS
Sequence in context: A374733 A231388 A330012 * A229614 A230216 A326081
KEYWORD
nonn,easy
AUTHOR
Jeffrey Shallit, Nov 22 2019
STATUS
approved