A277277 Number of overpal-free binary words of length n.

1, 2, 4, 6, 10, 14, 20, 28, 36, 44, 56, 72, 92, 116, 148, 188, 240, 304, 388, 492, 628, 796, 1016, 1288, 1644, 2084, 2660, 3372, 4304, 5456, 6964, 8828, 11268, 14284, 18232, 23112, 29500, 37396, 47732, 60508, 77232, 97904, 124964, 158412, 202196, 256316, 327160, 414728, 529356, 671044, 856516

Offset: 0

Author

Jeffrey Shallit, Oct 08 2016

Keywords

• nonn
• easy

Comments

An "overpal" is a word of the form a x a x^R a, where a is a single letter, x is a (possibly empty) word, and x^R denotes the reverse of the word x. To be "overpal-free" is to contain no factor (contiguous block) that is an overpal.

A binary word avoids overpals if and only if it avoids aaa, ababa, and abbabba as factors (Narad Rampersad). This gives the proof of Barker's formulas below. - Jeffrey Shallit, Oct 09 2016 and Colin Barker, Oct 10 2016

Examples

			For n = 4, the 14 words are 00100, 00101, 00110, 01001, and their complements and reversals.
		

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Aayush Rajasekaran, Narad Rampersad, Jeffrey Shallit, Overpals, Underlaps, and Underpals, In: Brlek S., Dolce F., Reutenauer C., Vandomme É. (eds) Combinatorics on Words, WORDS 2017, Lecture Notes in Computer Science, vol 10432.
• Index entries for linear recurrences with constant coefficients, signature (0,1,0,1).

Crossrefs

Cf. A007777.

Programs

PARI

Vec((1+2*x+3*x^2+4*x^3+5*x^4+6*x^5+6*x^6+8*x^7+6*x^8+2*x^9)/(1-x^2-x^4) + O(x^50)) \\ Colin Barker, Oct 10 2016

Formula

From Colin Barker, Oct 08 2016: (Start)

a(n) = a(n-2)+a(n-4) for n>9.

G.f.: (1+2*x+3*x^2+4*x^3+5*x^4+6*x^5+6*x^6+8*x^7+6*x^8+2*x^9) / (1-x^2-x^4).

(End)