|
%I #21 Dec 19 2017 18:37:00
%S 1,2,4,6,10,14,20,28,36,44,56,72,92,116,148,188,240,304,388,492,628,
%T 796,1016,1288,1644,2084,2660,3372,4304,5456,6964,8828,11268,14284,
%U 18232,23112,29500,37396,47732,60508,77232,97904,124964,158412,202196,256316,327160,414728,529356,671044,856516
%N Number of overpal-free binary words of length n.
%C 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.
%C 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
%H Colin Barker, <a href="/A277277/b277277.txt">Table of n, a(n) for n = 0..1000</a>
%H Aayush Rajasekaran, Narad Rampersad, Jeffrey Shallit, <a href="https://dx.doi.org/10.1007/978-3-319-66396-8_3">Overpals, Underlaps, and Underpals</a>, In: Brlek S., Dolce F., Reutenauer C., Vandomme É. (eds) Combinatorics on Words, WORDS 2017, Lecture Notes in Computer Science, vol 10432.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,1,0,1).
%F From _Colin Barker_, Oct 08 2016: (Start)
%F a(n) = a(n-2)+a(n-4) for n>9.
%F 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).
%F (End)
%e For n = 4, the 14 words are 00100, 00101, 00110, 01001, and their complements and reversals.
%o (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
%Y Cf. A007777.
%K nonn,easy
%O 0,2
%A _Jeffrey Shallit_, Oct 08 2016
|
