A241903 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

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

(list; graph; refs; listen; history; text; internal format)

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

Adjacent sequences: A241900 A241901 A241902 * A241904 A241905 A241906

KEYWORD

nonn

AUTHOR

Jeffrey Shallit, May 01 2014

STATUS

approved