A397833 Number of binary words of length n containing the consecutive word abab.

0, 0, 0, 0, 1, 4, 11, 28, 68, 158, 357, 792, 1731, 3738, 7996, 16972, 35789, 75052, 156647, 325616, 674436, 1392570, 2867433, 5889840, 12071527, 24692662, 50420348, 102789856, 209250377, 425413364, 863844579, 1752204420, 3550576068, 7188094422, 14539918861, 29388174664, 59357010539

Offset

0,6

Links

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

Wikipedia, Autocorrelation (words)

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

Formula

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

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

a(n) = 2^n - A118870(n).

Example

a(5) = 4: the words are aabab, ababa, ababb, babab.

Prog

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

Crossrefs

Cf. A000079, A118870, A397834, A397835.

Sequence in context: A003230 A099326 A127985 * A397834 A339252 A005409

Adjacent sequences: A397820 A397823 A397824 * A397834 A397835 A397837

Keyword

nonn,easy,new

Author

Seiichi Manyama, Jul 12 2026

Status

approved