A241903 Number of binary strings of length n avoiding the pattern x x x^R (where x^R means reverse of x).

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

Giovanni Resta, Table of n, a(n) for n = 0..300

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 A293422 A132002

Adjacent sequences: A241900 A241901 A241902 * A241904 A241905 A241906

Keyword

nonn

Author

Jeffrey Shallit, May 01 2014

Status

approved