login
A242206
Number of length n binary words which contain 00 and 01 and 10 and 11 as (possibly overlapping) contiguous subsequences.
6
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,1
COMMENTS
The expected wait time to see all four substrings is 19/2.
LINKS
Eric Weisstein's World of Mathematics, Coin Tossing
FORMULA
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
EXAMPLE
a(5) = 4 because we have: 00110, 01100, 10011, 11001.
MATHEMATICA
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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Edward Williams and Geoffrey Critzer, May 07 2014
STATUS
approved