A242206 -id:A242206 - cp's OEIS frontend

A242167 Number of length n binary words that contain 000 and 001 and 010 and 011 and 100 and 101 and 110 and 111 as contiguous subsequences. The 3 letter subsequences are allowed to overlap.

16, 80, 298, 934, 2632, 6890, 17118, 40908, 94884, 214956, 477922, 1046544, 2263228, 4843834, 10277132, 21645226, 45303842, 94314954, 195443594, 403391590, 829703588, 1701379556, 3479560910, 7099569872, 14455857024, 29380784736, 59618421994, 120801765892

Offset: 10

Edward Williams and Geoffrey Critzer, May 05 2014

The expected wait time to see all eight 3 bit strings is 89259/3640 (approximately 24.5).

			a(10) = 16 because we have: 0001011100, 0001110100, 0010111000, 0011101000, 0100011101, 0101110001, 0111000101, 0111010001, 1000101110, 1000111010, 1010001110, 1011100010, 1100010111, 1101000111, 1110001011, 1110100011.

Alois P. Heinz, Table of n, a(n) for n = 10..1000
Eric Weisstein's World of Mathematics, Coin Tossing
Index entries for linear recurrences with constant coefficients, signature (10, -41, 89, -114, 99, -58, -30, 120, -121, 109, -97, 20, -20, 37, 33, -17, 20, -66, 9, -9, 21, 21, -3, 0, -11, -2, -1, 1, 2).

Cf. A242206, A242257, A242323, A243882.

(* about 5 minutes of run time required *)
s=Tuples[{T,H},3];
t=Table[Total[Table[Total[z^Flatten[Position[Table[Take[s[[n]], 3-i]===Drop[s[[m]],i],{i,0,2}], True]-1]],{m,1,8}]*{a,b,c,d,e,f,g,h}],{n,1,8}];
sol=Solve[{a==va(z^3+t[[1]]-a),b==vb(z^3+t[[2]]-b),c==vc(z^3+t[[3]]-c), d==vd(z^3+t[[4]]-d),e==ve(z^3+t[[5]]-e), f==vf(z^3+t[[6]]-f),g==vg(z^3+t[[7]]-g),h==vh(z^3+t[[8]]-h)},{a,b,c,d,e,f,g,h}];
S=1/(1-2z-a-b-c-d-e-f-g-h);
vsub={va->ua-1,vb->ub-1,vc->uc-1,vd->ud-1,ve->ue-1,vf->uf-1,vg->ug-1,vh->uh-1};
Fz[ua_,ub_,uc_,ud_,ue_,uf_,ug_,uh_]=Simplify[S/.sol/.vsub];
tn=Table[Total[Map[Apply[Fz,#]&,Select[Tuples[{0,1},8],Count[#,0]==n&]]],{n,1,8}];
Drop[Flatten[CoefficientList[Series[1/(1-2z)-Simplify[tn[[1]] -tn[[2]] +tn[[3]]-tn[[4]]+tn[[5]]-tn[[6]]+tn[[7]]-tn[[8]]],{z,0,40}],z]],10]

G.f.: -2*x^10 *(2*x^23 +5*x^22 +9*x^21 +12*x^20 +14*x^19 -13*x^17 -19*x^16 -41*x^15 -6*x^14 -18*x^13 +33*x^12 +32*x^11 -6*x^10 +91*x^9 -111*x^8 +32*x^7 -8*x^6 -61*x^5 +107*x^4 -95*x^3 +77*x^2 -40*x +8) / ((2*x-1) *(x+1) *(x^2+1) *(x^2+x-1) *(x^3-x^2+2*x-1) *(x^3+x^2-1) *(x^3+x^2+x-1) *(x^4+x-1) *(x^4+x^3-1) *(x^3+x-1) *(x-1)^3). - Alois P. Heinz, May 07 2014

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

Original entry on oeis.org

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

Alois P. Heinz, May 09 2014

nonn

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).

			a(19) = 256: 0000100110101111000, 0000100111101011000, 0000101001101111000, ..., 1111010110010000111, 1111011000010100111, 1111011001010000111.

Alois P. Heinz, Table of n, a(n) for n = 19..2000
Eric Weisstein's World of Mathematics, Coin Tossing
Wikipedia, Deterministic finite automaton

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

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);

A242323 Number of binary words of length n that contain all 32 5-bit words as (possibly overlapping) contiguous subwords.

Original entry on oeis.org

65536, 352256, 1442816, 5313536, 18323520, 60481632, 192562808, 593792608, 1782459992, 5221699004, 14967607810, 42060446246, 116067269324

Offset: 36

Alois P. Heinz, May 10 2014

			a(36) = 65536: 000001000110010100111010110111110000, ... .

Eric Weisstein's World of Mathematics, Coin Tossing

Cf. A001146, A052944, A242167, A242206, A242257.

b:= proc(n, t, s) option remember; `if`(s={}, 2^n,
      `if`(nops(s)>n, 0, b(n-1, irem(2*t, 16), s minus {2*t})
        +b(n-1, irem(2*t+1, 16), s minus {2*t+1})))
    end:
a:= n-> add(b(n-4, j, {$0..31}), j=0..15):
seq(a(n), n=36..37);

b[n_, t_, s_] := b[n, t, s] = If[s == {}, 2^n,
   If[Length[s] > n, 0, b[n-1, Mod[2*t, 16], s~Complement~{2*t}] +
   b[n-1, Mod[2*t+1, 16], s~Complement~{2*t+1}]]];
a[n_] := Sum[b[n-4, j, Range[0, 31]], {j, 0, 15}];
Table[a[n], {n, 36, 39}] (* Jean-François Alcover, Sep 06 2022, after Alois P. Heinz *)

a(44)-a(48) from Alois P. Heinz, Feb 27 2015

A243862 Number of length n sequences on alphabet {0,1,2} that contain all of 00, 01, 02, 10, 11, 12, 20, 21, 22 as (possibly overlapping) contiguous subsequences.

Original entry on oeis.org

216, 2160, 14544, 78840, 374568, 1623420, 6580848, 25350384, 93835368, 336429336, 1175333232, 4019312448, 13502627088, 44688347724, 146041135932, 472142876544, 1512373800624, 4806068123880, 15168176407512, 47586553527408, 148517566558116, 461424138047280

Offset: 10

Geoffrey Critzer, Jun 12 2014

nonn

The expected wait time (average number of digits necessary) to see all 9 of the 2 bit strings is 18850259/711620 (approximately 26.4892).

Alois P. Heinz, Table of n, a(n) for n = 10..1000

Cf. A242206, A242167, A242257, A242323.

b:= proc(n, t, s) option remember; `if`(s={}, 3^n, `if`(nops(s)>n,
       0, add(b(n-1, j, s minus {3*t+j}), j=0..2)))
    end:
a:= n-> 3*b(n-1, 0, {$0..8}):
seq(a(n), n=10..40);  # Alois P. Heinz, Jun 13 2014

sol = Solve[{a == va(z^2 + z a + z d + z g),b == vb(z^2 + z a + z d + z g), c == vc (z^2 + z a + z d + z g), d == vd(z^2 + z b + z e + z h), e == ve(z^2 + z b + z e + z h), f == vf(z^2 + z b + z e + z h), g == vg(z^2 + z c + z f + z i), h == vh(z^2 + z c + z f + z i), i == vi(z^2 + z c + z f + z i)}, {a, b, c, d, e, f, g, h, i}];
vsub = {va -> ua - 1, vb -> ub - 1, vc -> uc - 1, vd -> ud - 1, ve -> ue - 1, vf -> uf - 1, vg -> ug - 1, vh -> uh - 1, vi -> ui - 1};
S = 1/(1 - 3z - a - b - c - d - e - f - g - h - i);
Fz[ua_, ub_, uc_, ud_, ue_, uf_, ug_, uh_, ui_] = S/.sol/.vsub; tn = Table[Total[Map[Apply[Fz, #] &, Select[Tuples[{0, 1}, 9], Count[#, 0] == n &]]], {n, 1, 9}];
Drop[Flatten[CoefficientList[Series[1/(1 - 3z) - (Simplify[tn[[1]] - tn[[2]] + tn[[3]] - tn[[4]] + tn[[5]] - tn[[6]] + tn[[7]] - tn[[8]]] + tn[[9]]), {z, 0, 40}], z]], 10]

G.f.: 12 *x^10 *(4*x^31 -29*x^30 +4*x^29 +137*x^28 -47*x^27 -414*x^26 +1491*x^25 +338*x^24 -6524*x^23 +1928*x^22 +7881*x^21 -4257*x^20 +7086*x^19 -2814*x^18 -28437*x^17 +30193*x^16 +18744*x^15 -47298*x^14 +17738*x^13 +13339*x^12 -14197*x^11 +18725*x^10 -17810*x^9 -13496*x^8 +35794*x^7 -19124*x^6 -6133*x^5 +12494*x^4 -6834*x^3 +1932*x^2 -288*x +18) / ((x-1) *(3*x-1) *(2*x-1) *(x+1) *(2*x^2-1) *(x^2+2*x-1) *(x^2+x-1) *(x^2-3*x+1) *(x^3+x^2+x-1) *(x^3-x^2-2*x+1) *(x^3-2*x^2-x+1) *(x^3+2*x-1) *(x^3-x^2+2*x-1) *(x^3+x^2-1) *(2*x^2+2*x-1) *(x^3+x-1) *(x^3+2*x^2+x-1) *(x^3-2*x^2+3*x-1)). - Alois P. Heinz, Jun 13 2014

A364685 The number of binary sequences of length n for which all patterns {0,1},{0,0},{1,0},{1,1} appear for the first time. In particular, three of the patterns will have appeared at least once before the (n-1)st digit in the sequence and the remaining pattern appears for the first and only time at positions {n-1,n} in the sequence.

Original entry on oeis.org

4, 10, 18, 30, 48, 76, 120, 190, 302, 482, 772, 1240, 1996, 3218, 5194, 8390, 13560, 21924, 35456, 57350, 92774, 150090, 242828, 392880, 635668, 1028506, 1664130, 2692590, 4356672, 7049212, 11405832, 18454990, 29860766, 48315698, 78176404, 126492040, 204668380

Offset: 5

Evan Fisher and Ruiqi (Violet) Cai, Aug 02 2023

			a(6)=10 is the number of cover time sequences of length 6 for binary patterns of length 2: {{0, 0, 0, 1, 1, 0}, {0, 0, 1, 0, 1, 1}, {0, 0, 1, 1, 1, 0}, {0, 1, 0, 0, 1, 1}, {0, 1, 1, 1, 0, 0}, {1, 0, 0, 0, 1, 1}, {1, 0, 1, 1, 0, 0}, {1, 1, 0, 0, 0, 1}, {1, 1, 0, 1, 0, 0}, {1, 1, 1, 0, 0, 1}}. (Notice that the final two digits in each of these sequences completes the appearance of all four patterns.)

Evan Fisher, Tianman Huang, and Xiaoshi Wang, Cover Times for Markov Generated Sequences of Length Two, Rocky Mountain J. Math. 50 (3) 957 - 974, June 2020.
Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Cf. A000045, A242206.

b[n_]:= b[n] = Tuples[{0, 1}, n];
a1[n_]:=
  Select[b[n],
   MatchQ[#, {_, PatternSequence[0, 0], _}] &&
     MatchQ[#, {_, PatternSequence[0, 1], _}] &&
     MatchQ[#, {_, PatternSequence[1, 0], _}] &&
     MatchQ[#, {_, PatternSequence[1, 1], _}] &];
Table[Length[
  Select[a1[k], Length[SequencePosition[#, Take[#, -2]]] == 1 &]], {k,
   5, 20}]

a(n) = 2*(n-6+F(n-1)), F(n) is the n-th Fibonacci number A000045(n).

G.f.: 2*x^5*(2*x^2+x-2)/((x^2+x-1)*(x-1)^2).

cp's OEIS Frontend

A242167 Number of length n binary words that contain 000 and 001 and 010 and 011 and 100 and 101 and 110 and 111 as contiguous subsequences. The 3 letter subsequences are allowed to overlap.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A242323 Number of binary words of length n that contain all 32 5-bit words as (possibly overlapping) contiguous subwords.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A243862 Number of length n sequences on alphabet {0,1,2} that contain all of 00, 01, 02, 10, 11, 12, 20, 21, 22 as (possibly overlapping) contiguous subsequences.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula