|
%I #11 Nov 29 2019 08:31:20
%S 1,4,12,24,48,96,168,264,456,720,1056,1656,2520,3600,5352,7944,11256,
%T 16248,23664,33432,47520,68232,96216,135696,192888,271488,381384,
%U 538464,756456,1060488,1490712,2090592,2927424,4103712,5746680,8040888,11252880,15739896
%N 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.
%C 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.
%H Lukas Fleischer, Jeffrey Shallit, <a href="https://arxiv.org/abs/1911.11704">Words Avoiding Reversed Factors, Revisited</a>, arXiv:1911.00248 [cs.FL], November 26 2019.
%H <a href="/index/Rec#order_12">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,5,-3,-2,-8,1,6,5,2,-4,-2).
%F 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.
%F 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
%e For n = 5 the a(5) = 96 strings are 01201, 01203, 01230, 01231 and the 92 similar strings formed by permutation of the alphabet.
%o (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
%K nonn,easy
%O 1,2
%A _Jeffrey Shallit_, Nov 27 2019
|
