login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

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

Cf. A242206, A242257, A242323, A243882.

Sequence in context: A212090 A212240 A050468 * A068778 A247817 A034570

Adjacent sequences:  A242164 A242165 A242166 * A242168 A242169 A242170

KEYWORD

nonn

AUTHOR

Edward Williams and Geoffrey Critzer, May 05 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 25 07:52 EST 2020. Contains 331241 sequences. (Running on oeis4.)