login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A242257 Number of binary words of length n that contain all sixteen 4-bit words as (possibly overlapping) contiguous subwords. 6
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 (list; graph; refs; listen; history; text; internal format)
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..1000

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 28 09:17 EST 2020. Contains 331318 sequences. (Running on oeis4.)