%I #17 Jul 13 2020 21:30:12
%S 2,4,8,16,32,56,84,120,164,226,312,428,584,802,1096,1500,2056,2816,
%T 3852,5280,7228,9892,13548,18554,25396,34788,47636,65212,89296,122278,
%U 167404,229252,313932,429830,588556,805910,1103420,1510924,2068960,2832944,3879100
%N Number of length-n binary words having no palindromes of length > 5 as contiguous subwords.
%C 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... .
%H Colin Barker, <a href="/A329824/b329824.txt">Table of n, a(n) for n = 1..1000</a>
%H G. Fici and L. Q. Zamboni, <a href="https://doi.org/10.1016/j.tcs.2013.02.013">On the least number of palindromes contained in an infinite word</a>, Theor. Comput. Sci. 481 (2013) 1-8.
%H Lukas Fleischer, Jeffrey Shallit, <a href="https://arxiv.org/abs/1911.12464">Words With Few Palindromes, Revisited</a>, arxiv preprint arXiv:1911.12464 [cs.FL], November 27 2019.
%H <a href="/index/Rec#order_10">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,0,0,0,3,2,2,2,1).
%F a(n) = 3a(n-6) + 2a(n-7) + 2a(n-8) + 2a(n-9) + a(n-10) for n >= 20.
%F 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
%e For n=6 the 8 strings NOT enumerated are 000000, 001100, 010010, 011110, and their binary complements.
%t 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 *)
%o (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
%K nonn,easy
%O 1,1
%A _Jeffrey Shallit_, Nov 22 2019