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

Author

Geoffrey Critzer, Mar 01 2014

Keywords

• nonn

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.

Examples

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

Links

• 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).

Crossrefs

Cf. A171861.

Programs

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]

Formula

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