A238644 Number of binary words on {H,T} that end in THTH but do not contain the contiguous subsequence HTHH.

0, 0, 0, 0, 1, 2, 3, 6, 11, 19, 34, 62, 112, 202, 365, 659, 1189, 2146, 3874, 6993, 12623, 22786, 41131, 74245, 134019, 241917, 436683, 788254, 1422873, 2568420, 4636240, 8368850, 15106563, 27268770, 49222700, 88851613, 160385536, 289511009, 522594658, 943332613, 1702804277

Offset

0,6

Comments

In the Penney game THTH beats HTHH 9 times out of 14 yet the expected wait time for THTH is 20 while that for HTHH is only 18.

Links

Table of n, a(n) for n=0..40.

Penney Ante, Counterintuitive Probabilities in Coin Tossing, Bay Area Circle for Teachers Summer Workshop. [broken link]

Raymond S. Nickerson, Penney Ante: Counterintuitive Probabilities in Coin Tossing, 2008.

Eric Weisstein's World of Mathematics, Coin Tossing

Wikipedia, Penney's game

Index entries for linear recurrences with constant coefficients, signature (2,-1,1,0,0,1).

Formula

G.f.: G(x) = (x^4 + x^7)/(1 - 2x + x^2 - x^3 - x^6). We note G(1/2) = 9/14.

Example

a(7)=6 because we have: TTTTHTH, THTTHTH, THHTHTH, HTTTHTH, HHTTHTH, HHHTHTH.

Mathematica

nn=40; CoefficientList[Series[(x^4+x^7)/(1-2x+x^2-x^3-x^6), {x, 0, nn}], x]
LinearRecurrence[{2, -1, 1, 0, 0, 1}, {0, 0, 0, 0, 1, 2, 3, 6}, 50]

Crossrefs

Cf. A171861.

Sequence in context: A024971 A038084 A018169 * A191629 A285553 A242842

Adjacent sequences: A238641 A238642 A238643 * A238645 A238646 A238647

Keyword

nonn

Author

Geoffrey Critzer, Mar 01 2014

Status

approved