Finding Catalan Numbers

Date: 12/15/1999 at 21:34:28
From: Bradley
Subject: Catalan Numbers

Dear Dr. Math,

For a research paper, I must study Catalan numbers. Could you possibly 
explain them (how to find them, applications, etc.)?

Thanks a million.

Date: 12/16/1999 at 10:36:52
From: Doctor Anthony
Subject: Re: Catalan Numbers

A physical interpretation is to consider an n x n square grid of 
streets and to find the number of routes from one corner of the square 
to the corner diagonally opposite that do not cross the diagonal. That 
is, while making the journey, the number of blocks north is always 
equal to or ahead of the number of blocks east - and of course vice 
versa.

Catalan Numbers
---------------
The number of sequences a(1), a(2), a(3), ..., a(2n) of 2n terms that 
can be formed by using n +1's and n -1's whose partial sums satisfy

     a(1) + a(2) + ... + a(k) >= 0  (where k = 1, 2, ..., 2n)  ....[1]

equals the nth Catalan number

     C_n = 1/(n+1) C(2n,n)   (n >= 0)

We call a sequence of n +1's and n -1's acceptable if it satisfies [1] 
and unacceptable otherwise. [This is equivalent to the number of 
routes consisting of n northerly blocks (+1) and n easterly blocks 
(-1) that never cross the diagonal.]

Let A(n) denote the number of acceptable sequences of n +1's and n 
-1's and let U(n) denote the number of unacceptable ones. The TOTAL 
number of sequences of n +1's and n -1's is

     (2n)!/(n!n!) = C(2n,n)

So we must have

     A(n) + U(n) = C(2n,n)

and we evaluate A(n) by first evaluating U(n) and subtracting from 
C(2n,n).

Consider an unacceptable sequence of n +1's and n -1's. Because the 
sequence is unacceptable there is a smallest k such that the partial 
sum:

     a(1) + a(2) + ... + a(k) < 0

Because k is smallest there is an equal number of +1's and -1's 
preceding a(k) and we have:

     a(1) + a(2) + ... + a(k-1) = 0   and   a(k) = -1

In particular, k is an ODD integer. We now reverse the signs of each 
of the first k terms; that is we replace a(i) by -a(i) for each i = 1, 
2, 3, ..., k and leave unchanged the remaining terms. The resulting 
sequence a'(1), a'(2), ..., a'(2n) is a sequence of (n+1) +1's and 
(n-1) -1's.

This process is reversible:
 
Given a sequence of (n+1) +1's and (n-1) -1's there is a first 
instance when the number of +1's exceeds the number of -1's (since 
there are more +1's than -1's). Reversing the +1's and -1's up to that 
point results in an unacceptable sequence of n +1's and n -1's. Thus 
there are as many unacceptable sequences as there are sequences of 
(n+1) +1's and (n-1) -1's. The number of sequences of (n+1) +1's and 
(n-1) -1's is the number (2n)!/[(n+1)!(n-1)!] = C(2n,n-1).

Therefore

               (2n)!
     U(n) = ------------
            (n+1)!(n-1)!

and thus
            (2n)!      (2n)!
     A(n) = ----- - ------------
            n! n!   (n+1)!(n-1)!

            (2n)!      1      1
          = -------- [--- - -----]
            n!(n-1)!   n    (n+1)

             (2n)!      1
          = -------- [------] 
            n!(n-1)!  n(n+1)

              1    (2n)!
          = ----- [-----]
            (n+1)  n! n!

          =  1/(n+1) C(2n,n)

There are many different interpretations of this theorem. The 
following are two examples.

Example (1)
------------
There are 2n people in line to get into a theatre. Admission is 50 
cents. Of the 2n people, n have 50-cent pieces and n have a $1 bill. 
The box office rather foolishly begins with an empty cash register. In 
how many ways can the people line up so whenever a person with a $1 
bill buys a ticket, the box office has a 50-cent piece in order to 
give change?

If we regard the people as indistinguishable and identify a 50-cent 
piece with a +1 and a dollar bill with -1, then the answer is the 
number

     C_n = 1/(n+1) C(2n,n)

of acceptable sequences. If the people are regarded as distinguishable 
the answer is:

    (n!)(n!) 1/(n+1) C(2n,n) = (2n)!/(n+1)

Example (2)
-----------
A city lawyer works n blocks north and n blocks east of his place of 
residence. Every day he walks 2n blocks to work. How many routes are 
possible if he never crosses (but may touch) the diagonal line from 
home to office?

Each acceptable route is either above the diagonal or below the 
diagonal. We find the number of acceptable routes above the diagonal 
and multiply by 2. Each route is a sequence of n northerly blocks and 
n easterly blocks. We identify north with +1 and east with -1. Thus 
each route corresponds to a sequence 

     a(1), a(2) , a(3), ..., a(2n)

of n +1's and n -1's and in order that the route not dip below the 
diagonal we must have

     a(1) + a(2) + a(3) + ... + a(k) >= 0

for k = 0, 1, 2, ..., 2n

Hence by theorem proved above the total number of acceptable routes is

     2.C_n = 2/(n+1) C(2n,n)

Recurrence Relation for Catalan Numbers
----------------------------------------
We have

     C_n = 1/(n+1) C(2n,n)

         = 1/(n+1) (2n)!/(n!n!)
and
     C_(n-1) = (1/n) (2n-2)!/[(n-1)!(n-1)!]

dividing we obtain

       C_n     (4n-2)
     ------- = ------
     C_(n-1)   (n+1)

Therefore the Catalan sequence is determined by the following 
recurrence relation and initial condition:

             4n-2 
     C_n = ------  C_(n-1)   and   C(1) = 1
             n+1

Parenthesizing an Expression
----------------------------
If we have to find all the ways to parenthesize the letters abcd we 
could have:

   (((ab)c)d)    (((abc     111000
   ((a(bc))d)    ((a(bc     110100
   ((ab)(cd))    ((ab(c     110010
   (a((bc)d))    (a((bc     101100
   (a(b(cd)))    (a(b(c     101010

The connection with Catalan numbers is that the information about 
parenthesizing does not require the letter d and we replace each left 
parenthesis '(' with '1' and each letter with '0'. Then an acceptable 
sequence must have the number of 1's equal to or exceeding the number 
of 0's.

In general one can parenthesize the product of n+1 letters in C_n 
ways.

So for the letters abcd we can parentesize in  C_3 ways

     C(3) = 1/4 C(6,3)

          = (1/4) 20

          =  5 ways

You can find additional information about Catalan numbers here:

  Catalan Numbers
  http://mathforum.org/advanced/robertd/catalan.html

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/