cp's OEIS Frontend

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

%I A242257 #23 Feb 16 2025 08:33:22
%S A242257 256,1344,5376,19028,61808,188474,547350,1522758,4083256,10620590,
%T A242257 26912658,66671138,161950112,386663750,909204980,2109158718,
%U A242257 4834062186,10960141396,24608994426,54771900982,120939714274,265121486866,577386711942,1249925021562,2691031388142
%N A242257 Number of binary words of length n that contain all sixteen 4-bit words as (possibly overlapping) contiguous subwords.
%C A242257 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).
%H A242257 Alois P. Heinz, <a href="/A242257/b242257.txt">Table of n, a(n) for n = 19..2000</a>
%H A242257 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CoinTossing.html">Coin Tossing</a>
%H A242257 Wikipedia, <a href="https://en.wikipedia.org/wiki/Deterministic_finite_automaton">Deterministic finite automaton</a>
%e A242257 a(19) = 256: 0000100110101111000, 0000100111101011000, 0000101001101111000, ..., 1111010110010000111, 1111011000010100111, 1111011001010000111.
%p A242257 b:=
%p A242257 proc(n, l) option remember; local m; m:= min(l[]);
%p A242257   `if`(m=5, 2^n, `if`(5-m>n, 0,        b(n-1, [   [2, 3, 4, 5, 5][l[1]],
%p A242257   [1, 1, 1, 1, 5][l[2]],  [2, 3, 4, 4, 5][l[3]],  [1, 1, 1, 5, 5][l[4]],
%p A242257   [2, 3, 3, 5, 5][l[5]],  [1, 1, 4, 1, 5][l[6]],  [2, 2, 4, 5, 5][l[7]],
%p A242257   [1, 3, 1, 3, 5][l[8]],  [1, 3, 4, 5, 5][l[9]],  [2, 2, 2, 2, 5][l[10]],
%p A242257   [2, 3, 3, 2, 5][l[11]], [1, 1, 4, 5, 5][l[12]], [2, 2, 2, 5, 5][l[13]],
%p A242257   [1, 3, 4, 1, 5][l[14]], [2, 2, 4, 2, 5][l[15]], [1, 3, 1, 5, 5][l[16]]])+
%p A242257   b(n-1, [                [1, 1, 1, 1, 5][l[1]],  [2, 3, 4, 5, 5][l[2]],
%p A242257   [1, 1, 1, 5, 5][l[3]],  [2, 3, 4, 4, 5][l[4]],  [1, 1, 4, 1, 5][l[5]],
%p A242257   [2, 3, 3, 5, 5][l[6]],  [1, 3, 1, 3, 5][l[7]],  [2, 2, 4, 5, 5][l[8]],
%p A242257   [2, 2, 2, 2, 5][l[9]],  [1, 3, 4, 5, 5][l[10]], [1, 1, 4, 5, 5][l[11]],
%p A242257   [2, 3, 3, 2, 5][l[12]], [1, 3, 4, 1, 5][l[13]], [2, 2, 2, 5, 5][l[14]],
%p A242257   [1, 3, 1, 5, 5][l[15]], [2, 2, 4, 2, 5][l[16]]])))
%p A242257 end:
%p A242257 a:= n-> b(n, [1$16]):
%p A242257 seq(a(n), n=19..40);
%Y A242257 Cf. A001146, A052944, A242167, A242206, A242323, A243820.
%K A242257 nonn
%O A242257 19,1
%A A242257 _Alois P. Heinz_, May 09 2014