A329023 Number of length-n ternary words having at most 5 palindromic subwords (including the empty word).

1, 3, 9, 27, 81, 42, 54, 66, 78, 96, 120, 144, 174, 216, 264, 318, 390, 480, 582, 708, 870, 1062, 1290, 1578, 1932, 2352, 2868, 3510, 4284, 5220, 6378, 7794, 9504, 11598, 14172, 17298, 21102, 25770, 31470, 38400, 46872, 57240, 69870, 85272, 104112, 127110, 155142

Offset: 0

Author

Jeffrey Shallit, Nov 02 2019

Keywords

• nonn
• easy
• changed

Examples

			For n=6 the examples are 001200, 001201, 010210, 011201, 012001, 012010, 012011, 012012, 012201 under permutation of the letters.
		

Links

• Colin Barker, Table of n, a(n) for n = 0..1000 [a(0)=1 prepended by Georg Fischer, 03 Dec 2019]
• G. Fici and L. Q. Zamboni, On the least number of palindromes contained in an infinite word, arXiv:1301.3376 [cs.DM], 2013.
• G. Fici and L. Q. Zamboni, On the least number of palindromes contained in an infinite word, Theoret. Comput. Sci. 481 (2013), 1-8.
• Lukas Fleischer and 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,1,1).

Crossrefs

Cf. A164317(n).

Programs

Mathematica

LinearRecurrence[{0, 0, 1, 1}, {1, 3, 9, 27, 81, 42, 54, 66, 78}, 50] (* Paolo Xausa, Aug 26 2025 *)

PARI

Vec((1 + 3*x + 9*x^2 + 26*x^3 + 77*x^4 + 30*x^5 + 18*x^6 - 42*x^7 - 45*x^8) / (1 - x^3 - x^4) + O(x^47)) \\ Colin Barker, Nov 02 2019; adapted to a(0)=1 by Georg Fischer, Dec 03 2019

Formula

a(n) = a(n-3) + a(n-4) for n >= 9.

a(n) = 6*A164317(n) for n >= 5.

G.f.: (1 + 3*x + 9*x^2 + 26*x^3 + 77*x^4 + 30*x^5 + 18*x^6 - 42*x^7 - 45*x^8) / (1 - x^3 - x^4). - Colin Barker, Nov 02 2019

Extensions

a(0) = 1 prepended by Jeffrey Shallit, Dec 02 2019