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