This article is from the Puzzles FAQ, by Chris Cole firstname.lastname@example.org and Matthew Daly email@example.com with numerous contributions by others.
What are the odds that a run of one H or T (i.e., THT or HTH) will occur
in n flips of a fair coin?
John P. Robinson, Transition Count and Syndrome are Uncorrelated, IEEE
Transactions on Information Theory, Jan 1988.
First we define a function or enumerator P(n,k) as the number of length
"n" sequences that generate "k" successes. For example,
P(4,1)= 4 (HHTH, HTHH, TTHT, and THTT are 4 possible length 4 sequences).
I derived two generating functions g(x) and h(x) in order to enumerate
P(n,k), they are compactly represented by the following matrix
_ _ _ _ _ _ | g(x) | | 1 1 | (n-3) | 4 | | | = | | | | | h(x) | | 1 x | |2+2x | |_ _| |_ _| |_ _|