The Catalan Numbers from Their Generating Function

Deriving the expression \displaystyle C_n = \frac{1}{n+1} \binom{2n}{n} for the Catalan numbers from the Catalan recurrence \displaystyle C_{n+1} = \sum_{k=0}^n C_k C_{n-k} is a classic exercise in generating function manipulation, although the details are sometimes omitted in textbooks (and on the Wikipedia page).  This post fills in the details.

The Catalan numbers are the solution to many combinatorial problems.  See, for example, this selection from Vol. II, Chapter 6, of Stanley’s Enumerative Combinatorics [1], as well as the Catalan addendum, for many such combinatorial interpretations.  My favorite is that C_n is the number of lattice paths from (0,0) to (n,n) that do not go above the diagonal y = x.

Let’s define C(x) to be the generating function for the Calatan numbers; i.e.,

\displaystyle C(x) = \sum_{n=0}^{\infty} C_n x^n.

To derive a closed-form for C_n from the recurrence, start by multiplying both sides of the Catalan recurrence by x^n and summing up:

\displaystyle \sum_{n=0}^{\infty} C_{n+1} x^n = \sum_{n=0}^{\infty} \left(\sum_{k=0}^n C_k C_{n-k}\right)x^n \\ \implies \frac{1}{x}\sum_{n=0}^{\infty} C_{n+1} x^{n+1} = C^2(x) \\ \implies \frac{1}{x}\sum_{n=1}^{\infty} C_n x^n = C^2(x) \\ \implies \frac{1}{x} \left(\sum_{n=0}^{\infty} C_n x^n - C_0 \right) = C^2(x) \\ \implies \frac{1}{x} C(x) - \frac{1}{x} = C^2(x) \\ \implies xC^2(x) - C(x) + 1 = 0 \\ \implies C(x) = \frac{1 \pm \sqrt{1 - 4x}}{2x}.

Now, do we want the positive or the negative square root?  We know that C_0 = 1, so the generating function satisfies C(0) = 1.  Subbing in 0 for either form of C(x) gives division by zero.  However, \displaystyle \lim_{x \to 0^+} C(x) is the indeterminate form 0/0 for the negative square root, so let’s take a closer look at this limit.  (The same limit evaluates to \infty for the positive square root, so that cannot be the right choice.)

Applying l’Hôpital’s rule, we have

\displaystyle \lim_{x \to 0^+} \frac{1 - \sqrt{1 - 4x}}{2x} = \lim_{x \to 0^+} \frac{2 (1-4x)^{-1/2}}{2} = 1.

The negative square root does evaluate to the correct number, so that one must be the right choice for C(x):

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

Applying Newton’s generalized binomial series, we then have

\displaystyle C(x) = \frac{1}{2x} \left(1 - \sqrt{1 - 4x} \right) = \frac{1}{2x} \left(1 - \sum_{n=0}^{\infty} \binom{1/2}{n} (-4x)^n \right).

The coefficient of x^n in the summand simplifies to

\displaystyle \frac{\frac{1}{2} (\frac{1}{2}-1) \cdots (\frac{1}{2}-n+1) }{n!} (-4)^n \\ = \frac{1(1-2) \cdots (1-2n+2) }{n!} (-1)^n 2^n \\ = \frac{(-1)(-3) \cdots (-(2n-3)) }{(n!)^2} (-1)^n 2^n (n)(n-1) \cdots (1) \\ = \frac{(-1)(-3) \cdots (-(2n-3)) }{(n!)^2} (-1)^n (2n)(2n-2) \cdots (2) \\ = - \frac{(2n)!}{(n!)^2 (2n-1)} \\ = - \binom{2n}{n} \frac{1}{2n-1}.

Therefore,
\displaystyle C(x) = \frac{1}{2x} \left(1 + \sum_{n=0}^{\infty} \binom{2n}{n} \frac{1}{2n-1} x^n \right) \\ = \frac{1}{2x} \left(1 + -1 + \sum_{n=1}^{\infty} \binom{2n}{n} \frac{1}{2n-1} x^n \right) \\ = \frac{1}{2} \sum_{n=1}^{\infty} \binom{2n}{n} \frac{1}{2n-1} x^{n-1} \\ = \frac{1}{2} \sum_{n=0}^{\infty} \binom{2(n+1)}{n+1} \frac{1}{2n+1} x^n \\ = \sum_{n=0}^{\infty} \frac{2(n+1)(2n+1)}{2(n+1)^2}\binom{2n}{n} \frac{1}{2n+1} x^n \\ = \sum_{n=0}^{\infty} \frac{1}{n+1}\binom{2n}{n} x^n.

Thus \displaystyle C_n = \frac{1}{n+1}\binom{2n}{n}, the coefficient of x^n in the generating function C(x).

References

1.  Richard Stanley, Enumerative Combinatorics, Vol. II, 2nd ed., Cambridge University Press, 2011.

Advertisements
This entry was posted in Catalan numbers, combinatorics. Bookmark the permalink.

9 Responses to The Catalan Numbers from Their Generating Function

  1. Marvis says:

    That is a very nice derivation of the generating function and the relation to binomial coefficients. Just a small correction. The limit for the positive square-root will be \infty and hence l’Hospital is not applicable and hence the limit is not -1. Hence, you can directly discard it. Also, interestingly, I encountered Catalan again last week in my answer [here](http://math.stackexchange.com/questions/326714/need-help-proving-this-integration/326825#326825)

  2. John says:

    How do we get C^2 (x)

    it is not obvious for me.

    10x

    • mzspivey says:

      I’m using the formula for term-by-term multiplication of an infinite series, sometimes called the Cauchy product. I realize now that I didn’t define C(x), though. I’ll go back and do that.

      • John says:

        10x for the answer but i would like to know how sum c(k)*c(n-k) leads to C^2

        Thank you in advance

      • mzspivey says:

        It probably makes more sense if you think about it from the other direction. Calculating C^2(x) involves multiplying an infinite series by itself. The result is another infinite series, but what is the coefficient of term x^n in that resulting series? For example, the coefficient of x^{10} is obtained by adding up all the different ways you could multiply two terms from C(x) and get a term with a coefficient of x^{10}. These would be C_0 x^0 C_{10}x^{10} +  C_1 x^1 C_9 x^9 + \cdots + C_{10}x^{10} C_0 x^0. The Cauchy product gives the formula in general.

  3. John says:

    Thank you very much!

    Best Regards,
    John

  4. shakeel says:

    Hi, two lines before the “Now, do we want the positive or the negative square root?” (second last line) you multiplied the equation by ‘x’ but the ‘1’ remained. It should be ‘x.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s