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

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

Offset

1,2

Links

Colin Barker, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Formula

For n >= 2, a(n) = 2F(n-1)+2n-4, where F(n) is the n-th Fibonacci number.

From Colin Barker, Mar 20 2017: (Start)

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

Sequence in context: A330130 A053799 A343949 * A212585 A085891 A006501

Adjacent sequences: A284119 A284120 A284121 * A284123 A284124 A284125

Keyword

nonn,easy

Author

Jeffrey Shallit, Mar 20 2017

Status

approved