login
A241903
Number of binary strings of length n avoiding the pattern x x x^R (where x^R means reverse of x).
3
1, 2, 4, 6, 10, 16, 24, 34, 48, 62, 80, 100, 124, 148, 178, 210, 244, 282, 324, 372, 426, 488, 556, 630, 712, 804, 908, 1024, 1152, 1296, 1454, 1626, 1814, 2018, 2244, 2490, 2756, 3044, 3354, 3690, 4050, 4438, 4856, 5300, 5772, 6272, 6800, 7370, 7966, 8598, 9266, 9964, 10708, 11484, 12300, 13166
OFFSET
0,2
LINKS
James Currie, Narad Rampersad, Growth rate of binary words avoiding xxx^R, arXiv preprint arXiv:1502.07014, 2015
J. D. Currie and N. Rampersad. Growth rate of binary words avoiding xxxR. Theoret. Comput. Sci. 609 (2016), 456-468.
Chen Fei Du, Hamoon Mousavi, Luke Schaeffer, and Jeffrey Shallit, Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance, preprint, June 3 2014
EXAMPLE
For n=4 the strings {0000,0001,0111,1000,1110,1111} have instances of x x x^R, so a(4) = 16-6 = 10.
CROSSREFS
Sequence in context: A132212 A327047 A332281 * A261204 A374145 A293422
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, May 01 2014
STATUS
approved