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
Keywords
Examples
For n=4 the strings {0000,0001,0111,1000,1110,1111} have instances of x x x^R, so a(4) = 16-6 = 10.
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