A330012 Number of length-n binary strings w with the property that if x is a subword of w and |x| >= 6, then x reversed is not a subword of w.

1, 2, 4, 8, 16, 32, 56, 84, 120, 164, 226, 312, 428, 584, 786, 1052, 1404, 1856, 2440, 3164, 4112, 5316, 6850, 8812, 11342, 14596, 18782, 24192, 31144, 40068, 51574, 66428, 85814, 110956, 143576, 185676, 240328, 310816, 402604, 521968, 677902, 880952, 1145288

Offset

0,2

Comments

a(n) ∼ c*alpha^n, where c ~ 15.0313407 and alpha ~ 1.305429354041958520199761719029 is the positive real zero of X^10 -X^4 -2X^3 -2X^2 -2X -1.

Links

Table of n, a(n) for n=0..42.

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

Formula

a(n) satisfies a degree-195 recurrence, for n >= 213.

Crossrefs

Sequence in context: A374731 A374733 A231388 * A329824 A229614 A230216

Adjacent sequences: A330009 A330010 A330011 * A330013 A330014 A330015

Keyword

nonn

Author

Jeffrey Shallit, Nov 27 2019

Status

approved