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,2

Comments

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

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

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.

Example

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.

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 *)

Crossrefs

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

Sequence in context: A118891 A107066 A141019 * A209888 A210021 A226188

Adjacent sequences: A210000 A210001 A210002 * A210004 A210005 A210006

Keyword

nonn,easy

Author

Alois P. Heinz, Mar 16 2012

Status

approved