login
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.
0
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
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
KEYWORD
nonn,easy
AUTHOR
Jeffrey Shallit, Nov 27 2019
STATUS
approved