Feeds:
Posts

## The Catalan numbers, regular languages, and orthogonal polynomials

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.

This identity is not too surprising from the perspective of continued fractions of surds: any root of a quadratic equation can be described as the fixed point of a fractional linear transformation, which gives rise to a continued fraction representation. It only makes sense that the Catalan generating function, which is the “positive” root of

$\displaystyle C(x) = 1 + x C(x)^2$

(and note that this gives a different combinatorial interpretation of the Catalan numbers, this time as binary trees), can be represented in this form.

What’s surprising is that this change in perspective has a combinatorial interpretation. Now, motivated by the usual theory of continued fractions we might like to talk about convergents to this continued fraction. To that end, we’ll define

$\displaystyle P_1(x) = 1, P_n(x) = \frac{1}{1 - xP_{n-1}(x)}.$

(Both the choice of letter and the choice of indexing will be explained later.) This gives us an interesting sequence of rational functions that “approximate” the Catalan numbers in some sense. In fact, there’s a pretty clear combinatorial interpretation: $P_n(x)$ is the generating function of a certain regular language that can be described as counting ordered rooted trees with depth at most $n$. As a regular language, multiplication by $x$ corresponds to appending a new extra character to the beginning of every word in a language, and substitution into the sequence species $\frac{1}{1 - x}$ corresponds to what computer scientists call the Kleene star operator. I don’t know of a particularly good notation for writing down all of these regular languages at once, but, for example, the language corresponding to $P_3$ consists of repeating blocks of the form $ab^n$; in other words, $P_3$ consists of the set of words on two letters that are either empty or start with $a$, which has generating function

$P_3(x) = \frac{1}{1 - \frac{x}{1 - x}} = \frac{1 - x}{1 - 2x} = 1 + x + 2x^2 + 4x^3 + ... + 2^{n-1} x^n + ...$.

The bijection to ordered rooted trees of depth at most three should be clear: the vertices adjacent to the root can be labeled with a’s and the vertices adjacent to those vertices can be labeled with b’s, and one reads a tree using a depth-first search, reading each non-root vertex once. Note that by construction $P_n(x)$ agrees with $C(x)$ to $n$ terms. More interesting is the next convergent,

$P_4(x) = \frac{1 - 2x}{1 - 3x + x^2} = 1 + x + 2x^2 + 5x^3 + 13x^4 + ...$,

which you might recognize as the even Fibonacci numbers. The corresponding regular language is a certain language on three letters, and the bijection to the usual definition on the Fibonacci numbers is an interesting combinatorial exercise.

Let’s try to generalize and figure out where these numerators and denominators are coming from. Let’s guess that we have

$P_n(x) = \frac{p_{n-1}(x)}{p_n(x)}$

for some sequence of polynomials beginning $p_0(x) = p_1(x) = 1, p_2(x) = 1 - x$, which therefore satisfies

$\frac{p_n(x)}{p_{n+1}(x)} = \frac{p_n(x)}{p_n(x) - x p_{n-1}(x)}$

giving us the identity $p_{n+1}(x) = p_n(x) - x p_{n-1}(x)$. Funnily enough, when $x = -1$ we obtain the Fibonacci numbers, and the Catalan generating function evaluates to the golden ratio. There appears to be something deeper here involving what I’ll refer to as “generalized cardinality”; see, for example, The Everything Seminar regarding the $x = 1$ case.

But we’ll try something else instead. The coefficients of $P_n(x)$ are controlled by the reciprocal of the roots of the denominator, so it’ll be more useful to consider a slightly different set of polynomials. To figure out exactly what we’ll need to do, however, note that $p_n$ is a polynomial of degree $\lfloor \frac{n}{2} \rfloor$, and we’d really prefer to work with polynomials of degree $n$. Moreover, the even Fibonacci numbers remind us that the Catalan numbers, as Dyck words, can also count objects of “size” $2n$, rather than $n$. So we should really be looking at $C(x^2)$ and modifying our other computations accordingly. We’ll also instead try to look at polynomials of degree $n$ instead, which requires adding a few extra factors. To make a long story short, what we want are the polynomials

$q_{2n}(x) = x^{2n} p_{2n} \left( \frac{1}{x^2} \right), q_{2n-1} = x^{2n} p_{2n-1} \left( \frac{1}{x^2} \right)$

given by $q_0(x) = 1, q_1(x) = x$ and satisfying the new, but closely related, recurrence relation

$q_{n+1}(x) = x q_n(x) - q_{n-1}(x)$.

Now, just like we would do for the Fibonacci numbers, let’s construct the new generating function

$\displaystyle F(x, y) = \sum_{n \ge 0} q_n(x) y^n = \frac{1}{1 - xy + y^2}$

where the closed form is a consequence of the recurrence relation and the first few terms. Those of you familiar with special functions might recognize this as the generating function for the Chebyshev polynomials of the second kind (up to a factor of two)! As we’ve constructed them, these polynomials satisfy

$q_n(2 \cos \theta) = \frac{\sin (n+1)\theta}{\sin \theta}$

and it follows that their roots are the numbers $2 \cos \frac{k \pi}{n+1}, k = 1, 2, ... n$. This is great; for $n = 4$, for example, this gives the identity

$2 \cos \frac{\pi}{5} = \phi$

familiar from the algebraic proof of the constructibility of the regular pentagon. It also implies that the growth rate of $[x^k] P_n(x)$ is controlled by the largest root of $q_n(x)$; more precisely, we have

$[x^k] P_n(x) = \Theta \left( 4^k \cos^{2k} \frac{\pi}{n+1} \right)$.

This is in some sense an approximation of the growth rate of the Catalan numbers. We can say something more precise, but first, there’s another way to think about the Chebyshev polynomials. I claim that the determinant identity

$q_n(x) = \left| \begin{array}{cccccc} x & -1 & 0 & 0 & \hdots & 0 \\ -1 & x & -1 & 0 & \hdots & 0 \\ 0 & -1 & x & -1 & \hdots & 0 \\ 0 & 0 & -1 & x & \hdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \hdots & x \\ \end{array} \right|$

holds. This is a corollary of a more general result about continued fractions that I have never seen actually written down anywhere, but for our purposes a different interpretation will be more useful: what this says is that $q_n(x)$ is the characteristic polynomial of the adjacency matrix of the path graph on $n$ vertices. And now we come full circle.

Proposition: The number of closed paths from one end to itself of length $2k$ on the path graph on $n$ vertices is $[x^k] P_n(x)$.

This implies a bijection between such paths and rooted ordered trees that will get us right back where we started, but I’d like to give the algebraic proof first. Let $\mathbf{P}_n$ denote the adjacency matrix of the path graph on $n$ vertices (which you can read off from the determinant I wrote down earlier). Then the generating function

$\displaystyle (\mathbf{I} - \mathbf{P}_n x)^{-1} = \sum_{k \ge 0} \mathbf{P}_n^k x^k$

(which is matrix-valued) gives us the number of paths between any two vertices of any length. We want to compute the top-left entry of this matrix, but by the construction of the adjugate matrix this is equal to

$\displaystyle \frac{ \det \left( \mathbf{I} - \mathbf{P}_n x ; 1, 1 \right) }{ \det \left( \mathbf{I} - \mathbf{P}_n x \right) }$

where $\det \left( \mathbf{I} - \mathbf{P}_n x ; 1, 1 \right)$ is the minor formed by deleting the first row and column. But this is just $\det \left( \mathbf{I} - \mathbf{P}_{n-1} x \right)$. Moreover, these determinants are essentially the polynomials $q_n(x)$, but with the reciprocal roots as expected, so the result follows.

This strongly suggests that there should be a combinatorial proof, and we should’ve suspected this all along. One way to define the Catalan numbers is as the number of closed walks from one end of the “infinite path graph” to itself, so we should expect that restricting walks corresponds in some way to restricting trees. In fact, there’s an even more general reason we should expect this: it’s well-known that regular languages correspond to languages recognized by finite automata. So let’s think like a finite automaton: how do you verify that a given ordered rooted tree has depth at most $n$?

Just as before, the answer is to perform a depth-first search. At each step, the state of our automaton will be the current level of the search, and the transitions between each state are precisely the edges of the path graph. The ordered rooted trees of depth $n$ are precisely those recognized by the finite automaton built from a path graph with $n$ vertices, and we get a bijection between such trees and the closed paths from the starting state to itself. (Note that there are two transitions for each non-root vertex: one the first time we encounter it going down, and one the second time we encounter it going up.) Of course, it is also possible to describe this algorithm in terms of recognizing the corresponding regular language.

Finite automata and regular languages are two of the most general ways to understand rational generating functions. While the regular language interpretation makes it particularly easy to write down a generating function that takes the form of a continued fraction, the finite automaton interpretation lets us use the tools of linear algebra, as we have seen. Let’s use another such tool: eigenvectors. Since $\mathbf{P}_n$ is symmetric, its eigenvectors form an orthonormal basis. In fact, they are given (up to scaling) by

$\mathbf{v}_{i, j} = \sin \frac{\pi i j}{n+1}$.

I don’t know of a particularly nice proof of this; the computation makes use of the product-to-sum formula. There’s a curious analogy to the harmonics of a closed tube and the Fourier sine basis that I don’t understand very well. I have a slightly slicker proof of the appropriate scale factor: the length of any of these eigenvectors is

$\displaystyle \sum_{i=1}^{n} \sin^2 \frac{\pi i j}{n+1}.$

The corresponding sum for the cosine is easy to read off using eigenvalues: the number of closed walks of length two on any undirected graph is twice the number of edges, giving the identity

$\displaystyle \sum_{i=1}^{n} 4 \cos^2 \frac{\pi i j}{n+1} = 2(n-1)$

which implies that the sum for the sine we want evaluates to $\frac{n+1}{2}$. Now we’ve got an orthonormal basis of eigenvectors, and from here (I’ll spare you the details) we can compute that the number of closed walks of length $2k$ from one end of the path graph to itself is

$\displaystyle \frac{1}{n+1} \sum_{i=1}^{n} 2 \sin^2 \frac{\pi}{n+1} \left( 2 \cos \frac{\pi i}{n+1} \right)^{2k} = [x^k] P_n(x)$.

If $k \le n-1$, this number agrees with the corresponding Catalan number. Taking the limit as $n \to \infty$ and interpreting the LHS as a Riemann sum, we obtain the integral identity

$\displaystyle \int_{0}^{1} 2 \sin^2 \pi x \left( 2 \cos \pi x \right)^{2k} \, dx = \frac{1}{k+1} {2k \choose k}.$

Now, we want to think of $d \mu = 2 \sin^2 \pi x \, dx$ as a sort of Borel measure on $[0, 1]$. The orthogonality of the Fourier sine basis on this space can be rephrased in terms of the identity

$\displaystyle \int_{0}^{1} \frac{\sin (n+1) \pi x}{\sin \pi x} \frac{ \sin (m+1) \pi x}{\sin \pi x} \, d \mu = \delta_{mn}$.

You can probably see where I’m going with this. Letting $y = 2 \cos \pi x$, this is equivalent to the identity

$\displaystyle \frac{1}{\pi} \int_{-2}^{2} q_n(y) q_m(y) \sqrt{4 - y^2} \, dy = \delta_{mn}$.

The Chebyshev polynomials have reappeared! Apparently the connection between continued fractions of power series and orthogonal polynomials is well-known and quite deep, but I have to admit it’s got me mystified. Part of the connection involves defining the linear functional

$\displaystyle L(f) = \int_{-2}^{2} f(y) \, \sqrt{4 - y^2} dy = \int_{0}^{1} f \left( 2 \cos \pi x \right) d \mu$.

The Chebyshev polynomials are orthogonal with respect to the inner product $(f, g) = L(fg)$, and we call the sequence $L(y^n)$ the sequence of moments associated to $\mu$. Now, we’ve just shown that this sequence of moments alternates between zero and the Catalan numbers; as the Secret Blogging Seminar mentions, this sequence also occurs when one computes the expected values of powers of the trace of a random element of $SU(2)$ distributed according to Haar measure, so the structure of $\mu$ presumably reflects this connection (although I’m clueless on this matter).

There’s a very interesting circle of ideas going on here, but I’m afraid I’ll have to end without closing it fully: according to a marvelous paper by Krattenthaler, I believe that the continued fraction identity

$\displaystyle \sum_{n \ge 0} L(y^n) x^n = \frac{1}{1 - \frac{x^2}{1 - \frac{x^2}{1 - ...}}}$

should imply the beautiful Hankel determinant identity

$\displaystyle \det_{0 \le i, j < n} \left( C_{i+j} \right) = 1$

but the result that Krattenthaler quotes implies that the entries of the matrix should be $C_{2i+2j}$, and I haven’t quite figured out what’s going on because it seems as if this is the wrong indexing; without the factor of two, there’s a beautiful proof of this identity using the Gessel-Viennot lemma which I may discuss in a later post.

Questions

How does the above circle of ideas fit together? How does it generalize? (For example, there is an analogue of some of the above for the central binomial coefficients where we replace path graphs with cycle graphs; I believe we get the Chebyshev polynomials of the first kind this way, and a relationship to traces in $SO(2)$.)

Is there an algorithm that, given a rational function built from a regular language, gives its “decomposition” into products, disjoint unions, and Kleene stars, or recognizes when such a decomposition does not exist? I haven’t given it much thought, but I don’t think there’s a straightforward analogue of the standard algorithm for computing the continued fraction of a rational number. This is related to my earlier question about automata, which I’ll pose in this alternate form: does there exist a rational function whose Taylor coefficients are all non-negative integers which is not generated from the functions $x, \frac{1}{1 - x}$ by addition, multiplication, and composition?

What’s the connection between the Catalan numbers and the golden ratio? I have an idea about this due to an exam problem set by my professor last semester, Gregg Musiker. Define a sequence of posets $\textsc{F}_n$ as follows: its elements are the subsets of $\{ i_1, ... i_{2k} \} \subset \{ 1, 2, ... 2n \}$ such that

$i_1, i_2 - i_1, ... i_{2k} - i_{2k-1}, (2n+1) - i_{2k}$

are odd positive integers, and the order relation is subset. $\textsc{F}_n$ is graded of rank $n+1$, and a standard result about Fibonacci numbers shows that the total number of its elements is given by

$\displaystyle \sum_{k=0}^{n} {n+k \choose 2k} = F_{2n+1}$

(where each term describes a rank.) Here’s the connection: the Mobius function of this poset is $\mu_k = (-1)^k C_k$ (another good combinatorial exercise; I don’t know of a way to deduce this from first principles), and the values of the Mobius function of a poset are related to the Euler characteristic (which is related to generalized cardinality) of a certain topological space associated to the poset, although I don’t understand this connection very well. Stanley and Rota are (two of) the authorities in this regard. So it seems as if the “limit” of these posets should correspond to a space with “generalized cardinality” related to $\phi$.

### 14 Responses

1. Hi. The number $2+4\frac{\pi}{3^(5/2)}=F(1,2;1/2;1/4)= 2.806133050770763...$ is the sum of the series of the reciprocals Catalan number, but in trying to demonstrate we begin to enter in desperado mood, so we would be very thankful any clue. Greets! above there’s a very good article.

• What I would try is to use the Beta function evaluation, which gives, if I’m not mistaken,

$(2n+1)(n+1) \int_{0}^{1} t^n (1 - t)^n \, dt = C_n^{-1}$.

Then sum over all $n$ and integrate. I haven’t worked out the details, though.

• it worked perfect! $\infty$-thanks… Now, do you know about a generating function for \$latex {C_n}^{-1}?. Let me tell you that we had discovered one, but we aren’t sure if it was quoted somewhere else.

2. I forgot to said please.

3. oops… it was ${C_n}^{-1}$

• Repeat the same trick as above; this generating function is known.

4. i’ll try, but allow me the last 2 q’s: do you known which is a ref? does it involve the arcsin map? please.
It seems at least that it isn’t widely known.
Thanks!

• Differentiate the generating function in Theorem 2.1 here. The argument is quite standard.

You should be aware that there exist software packages that have gotten very good at dealing with hypergeometric identities and I am certain that one or more of them could write down the generating function automatically given a description of its coefficients.

• it works again, super-thanks! it is equal the function we have, so it answers the 2nd quizz above, still a good reference it would be superb, thanks again my friend.

5. … we already knew Sprugnoli work and, yes, with $\frac{d}{dx}\left(\frac{x^{n+1}}{{2n\choose n}}\right)=\frac{(n+1)x^n}{{2n\choose n}}$ we got everything in place. You are very kind. Gracias.

6. […] the corresponding result for the Catalan numbers using their functional equation, then […]

7. […] Posts Optimizing parametersThe Catalan numbers, regular languages, and orthogonal polynomialsUpdate and blegHeron's formulaAboutBibliographyGILA I: Group actions and equivalence […]

8. […] A special case of part of the following discussion can be found in an old post on the Catalan numbers. […]