A330010 Number of length-n ternary strings x with the property that if w is a subword of x and |w| >= 3, then w reversed is not a subword of x.

1, 3, 9, 18, 30, 48, 78, 126, 204, 330, 534, 864, 1398, 2262, 3660, 5922, 9582, 15504, 25086, 40590, 65676, 106266, 171942, 278208, 450150, 728358, 1178508, 1906866, 3085374, 4992240, 8077614, 13069854, 21147468, 34217322, 55364790, 89582112, 144946902

Offset

0,2

Comments

Also the number of length-n ternary words containing no palindromes of length > 2.

Links

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

Lukas Fleischer, Jeffrey Shallit, Words Avoiding Reversed Factors, Revisited, arXiv:1911.00248 [cs.FL], November 26 2019.

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

Formula

a(n) = 6*F(n+1) for n >= 3, where F(n) is the n-th Fibonacci number.

From Colin Barker, Nov 27 2019: (Start)

G.f.: (1 + 2*x + 5*x^2 + 6*x^3 + 3*x^4) / (1 - x - x^2).

a(n) = a(n-1) + a(n-2) for n>4.

(End)

Example

For n = 4, the 30 strings are 0011, 0012, 0112, 0120, 0122 and the 25 similar strings formed by permutation of the alphabet.

Mathematica

CoefficientList[Series[(1 + 2 x + 5 x^2 + 6 x^3 + 3 x^4)/(1 - x - x^2), {x, 0, 36}], x] (* Michael De Vlieger, Dec 01 2019 *)

Prog

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

Crossrefs

Cf. A000045.

Sequence in context: A134479 A184969 A194113 * A194114 A127759 A064843

Adjacent sequences: A330007 A330008 A330009 * A330011 A330012 A330013

Keyword

nonn,easy

Author

Jeffrey Shallit, Nov 27 2019

Status

approved