login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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).

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)

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

Cf. A007777.

Sequence in context: A088954 A000123 A268752 * A241337 A103257 A103259

Adjacent sequences:  A277274 A277275 A277276 * A277278 A277279 A277280

KEYWORD

nonn,easy

AUTHOR

Jeffrey Shallit, Oct 08 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 14 10:47 EDT 2020. Contains 336480 sequences. (Running on oeis4.)