A329824 Number of length-n binary words having no palindromes of length > 5 as contiguous subwords.

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

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

Sequence in context: A374733 A231388 A330012 * A229614 A230216 A326081

Adjacent sequences: A329821 A329822 A329823 * A329825 A329826 A329827

Keyword

nonn,easy

Author

Jeffrey Shallit, Nov 22 2019

Status

approved