OFFSET
19,1
COMMENTS
The expected wait time to see all sixteen 4-bit words is Sum_{n>=0} (1-a(n)/2^n) ~ 58.632877... (with a(n) = 0 for 0 <= n <= 18).
LINKS
Alois P. Heinz, Table of n, a(n) for n = 19..2000
Eric Weisstein's World of Mathematics, Coin Tossing
Wikipedia, Deterministic finite automaton
EXAMPLE
a(19) = 256: 0000100110101111000, 0000100111101011000, 0000101001101111000, ..., 1111010110010000111, 1111011000010100111, 1111011001010000111.
MAPLE
b:=
proc(n, l) option remember; local m; m:= min(l[]);
`if`(m=5, 2^n, `if`(5-m>n, 0, b(n-1, [ [2, 3, 4, 5, 5][l[1]],
[1, 1, 1, 1, 5][l[2]], [2, 3, 4, 4, 5][l[3]], [1, 1, 1, 5, 5][l[4]],
[2, 3, 3, 5, 5][l[5]], [1, 1, 4, 1, 5][l[6]], [2, 2, 4, 5, 5][l[7]],
[1, 3, 1, 3, 5][l[8]], [1, 3, 4, 5, 5][l[9]], [2, 2, 2, 2, 5][l[10]],
[2, 3, 3, 2, 5][l[11]], [1, 1, 4, 5, 5][l[12]], [2, 2, 2, 5, 5][l[13]],
[1, 3, 4, 1, 5][l[14]], [2, 2, 4, 2, 5][l[15]], [1, 3, 1, 5, 5][l[16]]])+
b(n-1, [ [1, 1, 1, 1, 5][l[1]], [2, 3, 4, 5, 5][l[2]],
[1, 1, 1, 5, 5][l[3]], [2, 3, 4, 4, 5][l[4]], [1, 1, 4, 1, 5][l[5]],
[2, 3, 3, 5, 5][l[6]], [1, 3, 1, 3, 5][l[7]], [2, 2, 4, 5, 5][l[8]],
[2, 2, 2, 2, 5][l[9]], [1, 3, 4, 5, 5][l[10]], [1, 1, 4, 5, 5][l[11]],
[2, 3, 3, 2, 5][l[12]], [1, 3, 4, 1, 5][l[13]], [2, 2, 2, 5, 5][l[14]],
[1, 3, 1, 5, 5][l[15]], [2, 2, 4, 2, 5][l[16]]])))
end:
a:= n-> b(n, [1$16]):
seq(a(n), n=19..40);
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, May 09 2014
STATUS
approved