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

Author

Edward Williams and Geoffrey Critzer, May 07 2014

Keywords

• nonn

Comments

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

Examples

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

Links

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

Crossrefs

Cf. A242167, A242257, A242323.

Programs

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

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