Posts Tagged ‘regular languages’

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 150 coins. What is the probability that, at some point, you flipped at least 7 consecutive tails?

Jot down a quick estimate; see if you can get within a factor of 2 or so of the actual answer, which is below the fold.


Read Full Post »

Needless to say, I have been very, very busy. But enough about me.

Suppose you are given a bivariate generating function

\displaystyle F(x, y) = \sum_{m, n \ge 0} f(m, n) x^m y^n

in “closed form,” where I’ll be vague about what that means. Such a generating function may arise, for example, from counting lattice paths in \mathbb{Z}_{\ge 0}^2; then f(m,  n) might count the number of paths from (0, 0) to (m, n). If the path is only constrained by the fact that its steps must come from some set S \subset \mathbb{Z}_{\ge 0}^2 of steps containing only up or left steps, then we have the simple identity

\displaystyle F_S(x, y) = \frac{1}{1 - \sum_{(a, b) \in S} x^a y^b}.

Question: When can we determine the generating function \displaystyle D_F(x) = \sum_{n \ge 0} f(n, n) x^n in closed form?

I’d like to discuss an analytic approach to this question that gives concrete answers in at least a few important special cases, including the generating function for the central binomial coefficients, which is our motivating example.


Read Full Post »

I’ve been inspired by The Unapologetic Mathematician (and his pages and pages of archives!) to post more often, at least for the remainder of the summer. So here is a circle of ideas I’ve been playing with for some time.

Let C(x) = \sum_{n \ge 0} C_n x^n be the ordinary generating function for the ordered rooted trees on n+1 vertices (essentially we ignore the root as a vertex). This is one of the familiar definitions of the Catalan numbers. From a species perspective, ordered rooted trees are defined by the functional equation

\displaystyle C(x) = \frac{1}{1 - xC(x)}.

The generating function \frac{1}{1 - x} = 1 + x^2 + ... describes the species \textsc{Seq} 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 C(x), but we can instead recursively apply the above to obtain the beautiful continued fraction

\displaystyle C(x) = \frac{1}{1 - \frac{x}{1 - \frac{x}{1 - ...}}}.

Today’s discussion will center around this identity and some of its consequences.


Read Full Post »


Get every new post delivered to your Inbox.

Join 325 other followers