A330132 Number of length-n ternary words containing no even palindromes of length > 0 and no odd palindromes of length > 3.

1, 3, 6, 12, 24, 36, 54, 78, 114, 168, 246, 360, 528, 774, 1134, 1662, 2436, 3570, 5232, 7668, 11238, 16470, 24138, 35376, 51846, 75984, 111360, 163206, 239190, 350550, 513756, 752946, 1103496, 1617252, 2370198, 3473694, 5090946, 7461144, 10934838, 16025784

Offset

0,2

Links

Colin Barker, Table of n, a(n) for n = 0..1000

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 (1,0,1).

Formula

a(n) = a(n - 1) + a(n - 3) for n >= 7. Furthermore, a(n) ~ C*alpha^n, where C ~ 5.37711043 and alpha ~ 1.465571231876768 is the largest real zero of X^3 - X^2 - 1.

a(n) = 6*A000930(n - 1) for n >= 5.

G.f.: (1 + 2*x + 3*x^2 + 5*x^3 + 9*x^4 + 6*x^5 + 6*x^6) / (1 - x - x^3). - Colin Barker, Dec 02 2019

Mathematica

LinearRecurrence[{1, 0, 1}, {1, 3, 6, 12, 24, 36, 54}, 40] (* Harvey P. Dale, Dec 16 2021 *)

Prog

(PARI) Vec((1 + 2*x + 3*x^2 + 5*x^3 + 9*x^4 + 6*x^5 + 6*x^6) / (1 - x - x^3) + O(x^40)) \\ Colin Barker, Dec 02 2019

Crossrefs

Cf. A000930.

Sequence in context: A038620 A250300 A363692 * A039695 A079079 A283839

Adjacent sequences: A330129 A330130 A330131 * A330133 A330134 A330135

Keyword

nonn,easy

Author

Jeffrey Shallit, Dec 02 2019

Status

approved