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,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.

Index entries for linear recurrences with constant coefficients, signature (0,0,1,1).

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

Adjacent sequences: A329020 A329021 A329022 * A329024 A329025 A329026

Keyword

nonn,easy

Author

Jeffrey Shallit, Nov 02 2019

Extensions

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

Status

approved