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
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
Comments