login
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.
6
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,1
COMMENTS
The expected wait time to see all eight 3 bit strings is 89259/3640 (approximately 24.5).
LINKS
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).
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
EXAMPLE
a(10) = 16 because we have: 0001011100, 0001110100, 0010111000, 0011101000, 0100011101, 0101110001, 0111000101, 0111010001, 1000101110, 1000111010, 1010001110, 1011100010, 1100010111, 1101000111, 1110001011, 1110100011.
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]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Edward Williams and Geoffrey Critzer, May 05 2014
STATUS
approved