A242167 -id:A242167 - cp's OEIS frontend

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

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

A243882 Number of Dyck paths of semilength n such that all eight consecutive step patterns of length 3 occur at least once.

Original entry on oeis.org

1, 21, 124, 636, 2749, 11265, 44028, 168673, 636526, 2385703, 8903294, 33177968, 123602040, 460821006, 1720240295, 6432225711, 24095079682, 90435264009, 340097165156, 1281506663877, 4838093967400, 18299480354681, 69340086808691, 263195643048634

Offset: 5

Alois P. Heinz, Jun 13 2014

nonn

			a(5) = 1: 1011100010.
a(6) = 21: 101011100010, 101110001010, 101110100010, 101111000010, 101111000100, 101111001000, 110010111000, 110011101000, 110100111000, 110111000010, 110111000100, 110111001000, 111000101100, 111000110100, 111001011000, 111001101000, 111010001100, 111010011000, 111011000010, 111011000100, 111011001000.
Here 1=Up=(1,1), 0=Down=(1,-1).

Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 5..1000 (first 500 terms from Alois P. Heinz)
Vaclav Kotesovec, Recurrence (of order 14)

Cf. A242167, A243820.

b:= proc(x, y, t, s) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, `if`(s={}, 1, 0), `if`(nops(s)>x, 0, add(
      b(x-1, y-1+2*j, irem(2*t+j, 4), s minus {2*t+j}), j=0..1))))
    end:
a:= n-> add(b(2*n-2, l[], {$0..7}), l=[[0, 2], [2, 3]]):
seq(a(n), n=5..35);

b[x_, y_, t_, s_List] := b[x, y, t, s] = If[y<0 || y>x, 0, If[x == 0, If[s == {}, 1, 0], If[Length[s]>x, 0, Sum[b[x-1, y-1 + 2*j, Mod[2*t+j, 4], s ~Complement~ {2*t + j}], {j, 0, 1}]]]]; a[n_] :=  Sum[b[2*n-2, Sequence @@ l, Range[0, 7]], {l, {{0, 2}, {2, 3}}}]; Table[a[n], {n, 5, 35}] (* Jean-François Alcover, Feb 05 2015, after Alois P. Heinz *)

a(n) ~ 4^n / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jun 15 2014

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

cp's OEIS Frontend

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

A243882 Number of Dyck paths of semilength n such that all eight consecutive step patterns of length 3 occur at least once.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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