|
|
A284122
|
|
Number of binary words w of length n for which s, the longest proper suffix of w that appears at least twice in w, is of length 1 (i.e., either s = 0 or s = 1).
|
|
2
|
|
|
0, 2, 4, 8, 12, 18, 26, 38, 56, 84, 128, 198, 310, 490, 780, 1248, 2004, 3226, 5202, 8398, 13568, 21932, 35464, 57358, 92782, 150098, 242836, 392888, 635676, 1028514, 1664138, 2692598, 4356680, 7049220, 11405840, 18454998, 29860774, 48315706, 78176412, 126492048, 204668388, 331160362, 535828674
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
For n >= 2, a(n) = 2F(n-1)+2n-4, where F(n) is the n-th Fibonacci number.
G.f.: 2*x^2*(1 - x - x^3) / ((1 - x)^2*(1 - x - x^2)).
a(n) = 2*(-2+(2^(-1-n)*((1-sqrt(5))^n*(1+sqrt(5)) + (-1+sqrt(5))*(1+sqrt(5))^n)) / sqrt(5) + n) for n>1.
a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-4) for n>4.
(End)
|
|
EXAMPLE
|
For n = 5, the 12 such strings are {00010,00011,00110,01011,01100,01110} and their binary complements.
|
|
MATHEMATICA
|
Rest@ CoefficientList[Series[2 x^2*(1 - x - x^3)/((1 - x)^2*(1 - x - x^2)), {x, 0, 43}], x] (* Michael De Vlieger, Mar 20 2017 *)
LinearRecurrence[{3, -2, -1, 1}, {0, 2, 4, 8, 12}, 50] (* Harvey P. Dale, Apr 07 2023 *)
|
|
PROG
|
(PARI) concat(0, Vec(2*x^2*(1 - x - x^3) / ((1 - x)^2*(1 - x - x^2)) + O(x^50))) \\ Colin Barker, Mar 20 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|