A210003 Number of binary words of length n containing no subword 10001.

1, 2, 4, 8, 16, 31, 60, 116, 224, 433, 837, 1618, 3128, 6047, 11690, 22599, 43688, 84457, 163271, 315633, 610177, 1179585, 2280356, 4408350, 8522156, 16474904, 31849037, 61570080, 119026354, 230099960, 444825787, 859930531, 1662404788, 3213735970, 6212746113

Offset: 0

Author

Alois P. Heinz, Mar 16 2012

Keywords

• nonn
• easy

Comments

Each of the subwords 10001, 10011, 10111, 11001, 11101 and their binary complements give the same sequence.

Examples

			a(7) = 116 because among the 2^7 = 128 binary words of length 7 only 12, namely 0010001, 0100010, 0100011, 0110001, 1000100, 1000101, 1000110, 1000111, 1010001, 1100010, 1100011 and 1110001 contain the subword 10001.
		

Links

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

Crossrefs

Columns k=17, 19, 23, 25, 29 of A209972.

Programs

Maple

a:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>, <0|0|0|0|1>, <1|-1|0|0|2>>^n. <<1, 2, 4, 8, 16>>)[1, 1]: seq(a(n), n=0..40);

Mathematica

LinearRecurrence[{2,0,0,-1,1},{1,2,4,8,16},40] (* Harvey P. Dale, Oct 05 2015 *)

Formula

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

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