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
Colin Barker, Table of n, a(n) for n = 1..1000
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.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,3,2,2,2,1).
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
KEYWORD
nonn,easy
AUTHOR
Jeffrey Shallit, Nov 22 2019
STATUS
approved