login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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: A192797 A278355 A160619 * A132477 A102651 A102652

Adjacent sequences:  A330008 A330009 A330010 * A330012 A330013 A330014

KEYWORD

nonn,easy

AUTHOR

Jeffrey Shallit, Nov 27 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 26 09:15 EDT 2021. Contains 347664 sequences. (Running on oeis4.)