cp's OEIS Frontend

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.

%I A242167 #36 Feb 16 2025 08:33:22
%S A242167 16,80,298,934,2632,6890,17118,40908,94884,214956,477922,1046544,
%T A242167 2263228,4843834,10277132,21645226,45303842,94314954,195443594,
%U A242167 403391590,829703588,1701379556,3479560910,7099569872,14455857024,29380784736,59618421994,120801765892
%N 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.
%C A242167 The expected wait time to see all eight 3 bit strings is 89259/3640 (approximately 24.5).
%H A242167 Alois P. Heinz, <a href="/A242167/b242167.txt">Table of n, a(n) for n = 10..1000</a>
%H A242167 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CoinTossing.html">Coin Tossing</a>
%H A242167 <a href="/index/Rec#order_29">Index entries for linear recurrences with constant coefficients</a>, 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).
%F A242167 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
%e A242167 a(10) = 16 because we have: 0001011100, 0001110100, 0010111000, 0011101000, 0100011101, 0101110001, 0111000101, 0111010001, 1000101110, 1000111010, 1010001110, 1011100010, 1100010111, 1101000111, 1110001011, 1110100011.
%t A242167 (* about 5 minutes of run time required *)
%t A242167 s=Tuples[{T,H},3];
%t A242167 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}];
%t A242167 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}];
%t A242167 S=1/(1-2z-a-b-c-d-e-f-g-h);
%t A242167 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};
%t A242167 Fz[ua_,ub_,uc_,ud_,ue_,uf_,ug_,uh_]=Simplify[S/.sol/.vsub];
%t A242167 tn=Table[Total[Map[Apply[Fz,#]&,Select[Tuples[{0,1},8],Count[#,0]==n&]]],{n,1,8}];
%t A242167 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]
%Y A242167 Cf. A242206, A242257, A242323, A243882.
%K A242167 nonn,easy
%O A242167 10,1
%A A242167 Edward Williams and _Geoffrey Critzer_, May 05 2014