A242323 -id:A242323 - 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

A242206 Number of length n binary words which contain 00 and 01 and 10 and 11 as (possibly overlapping) contiguous subsequences.

Original entry on oeis.org

4, 18, 54, 138, 324, 724, 1568, 3326, 6954, 14390, 29552, 60344, 122684, 248586, 502366, 1013122, 2039804, 4101532, 8238520, 16534390, 33161554, 66473198, 133189224, 266771328, 534178324, 1069385154, 2140434438, 4283561466, 8571479604, 17150008420, 34311422672

Offset: 5

Edward Williams and Geoffrey Critzer, May 07 2014

nonn

The expected wait time to see all four substrings is 19/2.

			a(5) = 4 because we have: 00110, 01100, 10011, 11001.

Alois P. Heinz, Table of n, a(n) for n = 5..1000
Eric Weisstein's World of Mathematics, Coin Tossing

Cf. A242167, A242257, A242323.

sol=Solve[{A==va (z^2+z A+z C),B==vb (z^2+z A+z C),C==vc (z^2+z B+z D), D==vd (z^2+z B+z D)}, {A,B,C,D}];
S=1/(1-2 z-A-B-C-D);
vsub={va->ua-1,vb->ub-1,vc->uc-1,vd->ud-1};
Fz[z_,ua_,ub_,uc_,ud_]=Simplify[S/.sol/.vsub];
G[z_]=Simplify[Fz[z,1,1,1,0]+Fz[z,0,1,1,1]+Fz[z,1,0,1,1] +Fz[z,1,1,0,1] -Fz[z,1,1,0,0] -Fz[z,1,0,1,0]-Fz[z,1,0,0,1]-Fz[z,0,1,1,0] -Fz[z,0,1,0,1] -Fz[z,0,0,1,1]+Fz[z,1,0,0,0]+Fz[z,0,1,0,0] +Fz[z,0,0,1,0] +Fz[z,0,0,0,1] -Fz[z,0,0,0,0]];
Drop[Flatten[CoefficientList[Series[1/(1-2z)-G[z], {z,0,40}],z]],5]
CoefficientList[Series[-2x^5(-2+x+2x^2)/((2x-1)(x^2+x-1)(x-1)^2),{x,0,50}],x] (* Harvey P. Dale, May 30 2018 *)

G.f.: -2*x^5*(-2+x+2*x^2)/((2*x-1)*(x^2+x-1)*(x-1)^2). - 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);

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

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

A242206 Number of length n binary words which contain 00 and 01 and 10 and 11 as (possibly overlapping) contiguous subsequences.

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

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