A210031 Number of binary words of length n containing no subword 100001.

1, 2, 4, 8, 16, 32, 63, 124, 244, 480, 944, 1857, 3653, 7186, 14136, 27808, 54703, 107610, 211687, 416424, 819176, 1611457, 3170007, 6235937, 12267137, 24131522, 47470763, 93382976, 183700022, 361368844, 710873303, 1398407365, 2750902517, 5411487988

Offset: 0

Author

Alois P. Heinz, Mar 16 2012

Keywords

• nonn
• easy

Comments

Each of the subwords 100001, 100011, 100101, 100111, 101001, 101011, 101111, 110001, 110101, 111001, 111101 and their binary complements give the same sequence.

Examples

			a(8) = 244 because among the 2^8 = 256 binary words of length 8 only 12, namely 00100001, 01000010, 01000011, 01100001, 10000100, 10000101, 10000110, 10000111, 10100001, 11000010, 11000011, 11100001 contain the subword 100001.
		

Links

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

Crossrefs

Columns k=33, 35, 37, 39, 41, 43, 47, 49, 53, 57, 61 of A209972.

Programs

Maple

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

Formula

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

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