|
|
A277277
|
|
Number of overpal-free binary words of length n.
|
|
1
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
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
|
|
LINKS
|
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.
|
|
FORMULA
|
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)
|
|
EXAMPLE
|
For n = 4, the 14 words are 00100, 00101, 00110, 01001, and their complements and reversals.
|
|
PROG
|
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|