OFFSET
10,1
COMMENTS
The expected wait time to see all eight 3 bit strings is 89259/3640 (approximately 24.5).
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).
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