A330011 Number of length-n strings w over a 4-letter alphabet with the property that if x is a subword of w and |x| >= 2, then x reversed is not a subword of w.

1, 4, 12, 24, 48, 96, 168, 264, 456, 720, 1056, 1656, 2520, 3600, 5352, 7944, 11256, 16248, 23664, 33432, 47520, 68232, 96216, 135696, 192888, 271488, 381384, 538464, 756456, 1060488, 1490712, 2090592, 2927424, 4103712, 5746680, 8040888, 11252880, 15739896

Offset

1,2

Comments

Asymptotically we have a(n) = C * alpha^n, where alpha ~ 1.395336944 is the largest real zero of X^4 - 2X - 1 and C ~ 71.2145756.

Links

Table of n, a(n) for n=1..38.

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

Index entries for linear recurrences with constant coefficients, signature (1,0,5,-3,-2,-8,1,6,5,2,-4,-2).

Formula

a(n) = a(n - 1) + 5a(n - 3) - 3a(n - 4) - 2a(n - 5) - 8a(n - 6) + a(n - 7) + 6a(n-8) + 5a(n-9) + 2a(n-10) - 4a(n-11) - 2a(n-12) for n >= 17.

G.f.: x*(1 + 3*x + 8*x^2 + 7*x^3 + 7*x^4 + 2*x^5 + 4*x^6 - 17*x^7 - 10*x^8 - 41*x^9 - 22*x^10 - 40*x^11 - 6*x^12 + 8*x^13) / ((1 - x)*(1 - 2*x^3)*(1 - x^3 - x^4)*(1 - 2*x^3 - x^4)). - Colin Barker, Nov 27 2019

Example

For n = 5 the a(5) = 96 strings are 01201, 01203, 01230, 01231 and the 92 similar strings formed by permutation of the alphabet.

Prog

(PARI) Vec(x*(1 + 3*x + 8*x^2 + 7*x^3 + 7*x^4 + 2*x^5 + 4*x^6 - 17*x^7 - 10*x^8 - 41*x^9 - 22*x^10 - 40*x^11 - 6*x^12 + 8*x^13) / ((1 - x)*(1 - 2*x^3)*(1 - x^3 - x^4)*(1 - 2*x^3 - x^4)) + O(x^40)) \\ Colin Barker, Nov 27 2019

Crossrefs

Sequence in context: A278355 A160619 A352668 * A132477 A102651 A102652

Adjacent sequences: A330008 A330009 A330010 * A330012 A330013 A330014

Keyword

nonn,easy

Author

Jeffrey Shallit, Nov 27 2019

Status

approved