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

Author

Edward Williams and Geoffrey Critzer, May 05 2014

Keywords

• nonn
• easy

Comments

The expected wait time to see all eight 3 bit strings is 89259/3640 (approximately 24.5).

Examples

			a(10) = 16 because we have: 0001011100, 0001110100, 0010111000, 0011101000, 0100011101, 0101110001, 0111000101, 0111010001, 1000101110, 1000111010, 1010001110, 1011100010, 1100010111, 1101000111, 1110001011, 1110100011.
		

Links

• 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).

Crossrefs

Cf. A242206, A242257, A242323, A243882.

Programs

Mathematica

(* 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]

Formula

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