A209888 Number of binary words of length n containing no subword 01101.

1, 2, 4, 8, 16, 31, 60, 116, 225, 436, 845, 1637, 3172, 6146, 11909, 23075, 44711, 86633, 167863, 325256, 630226, 1221144, 2366125, 4584673, 8883398, 17212733, 33351899, 64623621, 125216632, 242623433, 470114310, 910907331, 1765000872, 3419917668, 6626533192

Offset: 0

Author

Alois P. Heinz, Mar 14 2012

Keywords

• nonn

Comments

Notice that the proper suffix 01 of 01101 is also a prefix of 01101. If instead of 01101 subword 01011 is not allowed, we get A107066 with A107066(n) < a(n) for all n >= 8. Word 01101101 of length 8 is the smallest binary word having two or more copies of 01101.

Examples

			a(6) = 60 because among the 2^6 = 64 binary words of length 6 only 4, namely 001101, 011010, 011011 and 101101 contain the subword 01101.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (2,0,-1,2,-1).

Crossrefs

Column 22 of A209972.

Column k=0 of A277751.

Cf. A107066, A317669.

Programs

Maple

a:= n-> (Matrix(5, (i, j)-> `if`(i=j-1, 1, `if`(i=5, [-1, 2, -1, 0, 2][j], 0)))^n. <<1, 2, 4, 8, 16>>)[1, 1]: seq(a(n), n=0..40);

Mathematica

CoefficientList[Series[(x + 1)*(x^2 - x + 1)/(x^5 - 2*x^4 + x^3 - 2*x + 1), {x, 0, 40}], x] (* Wesley Ivan Hurt, Apr 28 2017 *)
LinearRecurrence[{2,0,-1,2,-1},{1,2,4,8,16},40] (* Harvey P. Dale, Sep 17 2017 *)

Formula

G.f.: (x+1)*(x^2-x+1) / (x^5-2*x^4+x^3-2*x+1).

a(n) = 2^n if n<5, and a(n) = 2*(a(n-1)+a(n-4)) -a(n-3) -a(n-5) otherwise.