A397834 Number of binary words of length n containing the consecutive word ababab.

0, 0, 0, 0, 0, 0, 1, 4, 11, 28, 68, 160, 368, 830, 1845, 4056, 8835, 19098, 41016, 87600, 186196, 394108, 831101, 1746892, 3661031, 7652344, 15956936, 33201944, 68947596, 142918554, 295757337, 611105328, 1260898647, 2598199062, 5347277764, 10992515464, 22573447784, 46308912184

Offset

0,8

Links

Table of n, a(n) for n=0..37.

Wikipedia, Autocorrelation (words)

Index entries for linear recurrences with constant coefficients, signature (4,-5,4,-5,4,-5,2).

Formula

G.f.: x^6/((1-2*x) * (x^6 + (1-2*x) * (1+x^2+x^4))). Equivalently, 1/(1-2*x) - (1+x^2+x^4)/(x^6 + (1-2*x) * (1+x^2+x^4)).

a(n) = 4*a(n-1) - 5*a(n-2) + 4*a(n-3) - 5*a(n-4) + 4*a(n-5) - 5*a(n-6) + 2*a(n-7).

Example

a(7) = 4: the words are aababab, abababa, abababb, bababab.

Prog

(PARI) my(N=40, x='x+O('x^N)); concat([0, 0, 0, 0, 0, 0], Vec(x^6/((1-2*x)*(x^6+(1-2*x)*(1+x^2+x^4)))))

Crossrefs

Cf. A256813, A397833.

Sequence in context: A099326 A127985 A397833 * A339252 A005409 A245124

Adjacent sequences: A397825 A397826 A397833 * A397835 A397837 A397838

Keyword

nonn,easy,new

Author

Seiichi Manyama, Jul 12 2026

Status

approved