A397834 - OEIS

%I #20 Jul 12 2026 09:21:52

%S 0,0,0,0,0,0,1,4,11,28,68,160,368,830,1845,4056,8835,19098,41016,

%T 87600,186196,394108,831101,1746892,3661031,7652344,15956936,33201944,

%U 68947596,142918554,295757337,611105328,1260898647,2598199062,5347277764,10992515464,22573447784,46308912184

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

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Autocorrelation_%28words%29">Autocorrelation (words)</a>

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (4,-5,4,-5,4,-5,2).

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

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

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

%o (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)))))

%Y Cf. A256813, A397833.

%K nonn,easy,new

%O 0,8

%A _Seiichi Manyama_, Jul 12 2026