Something very unfortunate has happened: several things I have recently written that could have been blog entries are instead answers on math.SE! In the interest of exposition beyond the Q&A format I am going to “rescue” one of these answers. It is an answer to the following question, which I would like you to test your intuition about:
Flip
coins. What is the probability that, at some point, you flipped at least
consecutive tails?
Jot down a quick estimate; see if you can get within a factor of 
; then 
might count the number of paths from 
to 
. If the path is only constrained by the fact that its steps must come from some set 
of steps containing only up or left steps, then we have the simple identity
.
in closed form?
be the ordinary generating function for the ordered rooted trees on 
vertices (essentially we ignore the root as a vertex). This is one of the familiar definitions of the 
.
describes the species 
of sequences. So what this definition means is that, after tossing out the root, an ordered rooted tree is equivalent to a sequence of ordered rooted trees (counting their roots) in the obvious way; the roots of these trees are precisely the neighbors of the original root. Multiplying out gets us a quadratic equation we can use to find the usual closed form of 
, but we can instead recursively apply the above to obtain the beautiful continued fraction
.
