login
A329023
Number of length-n ternary words having at most 5 palindromic subwords (including the empty word).
1
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,2
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, Jeffrey Shallit, Words With Few Palindromes, Revisited, arxiv preprint arXiv:1911.12464 [cs.FL], November 27 2019.
FORMULA
a(n) = a(n-3) + a(n-4) for n >= 9.
Equal to 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
EXAMPLE
For n=6 the examples are 001200, 001201, 010210, 011201, 012001, 012010, 012011, 012012, 012201 under permutation of the letters.
PROG
(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^40)) \\ \\ Colin Barker, Nov 02 2019; adapted to a(0)=1 by_Georg Fischer_, Dec 03 2019
CROSSREFS
Cf. A164317(n).
Sequence in context: A036142 A036160 A271352 * A001218 A036158 A036136
KEYWORD
nonn,easy
AUTHOR
Jeffrey Shallit, Nov 02 2019
EXTENSIONS
a(0) = 1 prepended by Jeffrey Shallit, Dec 02 2019
STATUS
approved