|
|
A329824
|
|
Number of length-n binary words having no palindromes of length > 5 as contiguous subwords.
|
|
1
|
|
|
2, 4, 8, 16, 32, 56, 84, 120, 164, 226, 312, 428, 584, 802, 1096, 1500, 2056, 2816, 3852, 5280, 7228, 9892, 13548, 18554, 25396, 34788, 47636, 65212, 89296, 122278, 167404, 229252, 313932, 429830, 588556, 805910, 1103420, 1510924, 2068960, 2832944, 3879100
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
a(n) is asymptotically equal to c*alpha^n, where alpha = 1.36927381628918060784... is the positive real zero of the equation X^10-3X^4-2X^3-2X^2-2X-1, and c = 9.8315779... .
|
|
LINKS
|
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,3,2,2,2,1).
|
|
FORMULA
|
a(n) = 3a(n-6) + 2a(n-7) + 2a(n-8) + 2a(n-9) + a(n-10) for n >= 20.
G.f.: 2*x*(1 + x)*(1 + x + x^2)*(1 + 2*x^2 + 3*x^3 + 6*x^4 + 8*x^5 + 8*x^6 + 14*x^7 + 12*x^8 + 15*x^9 + 11*x^10 + 8*x^11 + 5*x^12 + 4*x^13 + 2*x^15) / (1 - 3*x^6 - 2*x^7 - 2*x^8 - 2*x^9 - x^10). - Colin Barker, Nov 22 2019
|
|
EXAMPLE
|
For n=6 the 8 strings NOT enumerated are 000000, 001100, 010010, 011110, and their binary complements.
|
|
MATHEMATICA
|
Rest@ CoefficientList[Series[2 x (1 + x) (1 + x + x^2) (1 + 2 x^2 + 3 x^3 + 6 x^4 + 8 x^5 + 8 x^6 + 14 x^7 + 12 x^8 + 15 x^9 + 11 x^10 + 8 x^11 + 5 x^12 + 4 x^13 + 2 x^15)/(1 - 3 x^6 - 2 x^7 - 2 x^8 - 2 x^9 - x^10), {x, 0, 41}], x] (* Michael De Vlieger, Nov 22 2019 *)
|
|
PROG
|
(PARI) Vec(2*x*(1 + x)*(1 + x + x^2)*(1 + 2*x^2 + 3*x^3 + 6*x^4 + 8*x^5 + 8*x^6 + 14*x^7 + 12*x^8 + 15*x^9 + 11*x^10 + 8*x^11 + 5*x^12 + 4*x^13 + 2*x^15) / (1 - 3*x^6 - 2*x^7 - 2*x^8 - 2*x^9 - x^10) + O(x^40)) \\ Colin Barker, Nov 22 2019
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|