A242257 Number of binary words of length n that contain all sixteen 4-bit words as (possibly overlapping) contiguous subwords.

256, 1344, 5376, 19028, 61808, 188474, 547350, 1522758, 4083256, 10620590, 26912658, 66671138, 161950112, 386663750, 909204980, 2109158718, 4834062186, 10960141396, 24608994426, 54771900982, 120939714274, 265121486866, 577386711942, 1249925021562, 2691031388142

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

Cf. A001146, A052944, A242167, A242206, A242323, A243820.

Sequence in context: A205090 A231943 A206327 * A206320 A237315 A237309

Adjacent sequences: A242254 A242255 A242256 * A242258 A242259 A242260

Keyword

nonn

Author

Alois P. Heinz, May 09 2014

Status

approved