|
|
A210031
|
|
Number of binary words of length n containing no subword 100001.
|
|
2
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Each of the subwords 100001, 100011, 100101, 100111, 101001, 101011, 101111, 110001, 110101, 111001, 111101 and their binary complements give the same sequence.
|
|
LINKS
|
|
|
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.
|
|
EXAMPLE
|
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.
|
|
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);
|
|
CROSSREFS
|
Columns k=33, 35, 37, 39, 41, 43, 47, 49, 53, 57, 61 of A209972.
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|