%I #21 May 30 2018 17:52:23
%S 4,18,54,138,324,724,1568,3326,6954,14390,29552,60344,122684,248586,
%T 502366,1013122,2039804,4101532,8238520,16534390,33161554,66473198,
%U 133189224,266771328,534178324,1069385154,2140434438,4283561466,8571479604,17150008420,34311422672
%N Number of length n binary words which contain 00 and 01 and 10 and 11 as (possibly overlapping) contiguous subsequences.
%C The expected wait time to see all four substrings is 19/2.
%H Alois P. Heinz, <a href="/A242206/b242206.txt">Table of n, a(n) for n = 5..1000</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CoinTossing.html">Coin Tossing</a>
%F 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
%e a(5) = 4 because we have: 00110, 01100, 10011, 11001.
%t 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}];
%t S=1/(1-2 z-A-B-C-D);
%t vsub={va->ua-1,vb->ub-1,vc->uc-1,vd->ud-1};
%t Fz[z_,ua_,ub_,uc_,ud_]=Simplify[S/.sol/.vsub];
%t 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]];
%t Drop[Flatten[CoefficientList[Series[1/(1-2z)-G[z], {z,0,40}],z]],5]
%t 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 *)
%Y Cf. A242167, A242257, A242323.
%K nonn
%O 5,1
%A Edward Williams and _Geoffrey Critzer_, May 07 2014
|