Project III (MATH3382) 2013-14

Catalan numbers

Anna Felikson


Catalan numbers Cn form one of the most frequently used sequences of natural numbers. They appear as answers to numerous enumerative problems, completely different from the first glance.
    As an example of their appearance one can take the number of expressions containing n pairs of parentheses which are correctly matched. For example, C3=5 as you can see from the following list:

    ()()(),---- ()(()),---- (())(),---- (()()),---- ((()))

    (why is this list complete?)
      Catalan numbers not only offer a unified answer to a wide selection of combinatorial problems, they also may serve as a good starting point if you want to learn combinatorics of polytopes or cluster algebras .
      Prerequisites: open mind (to see similarities in different issues and to see different faces of the same thing)


      The wikipedia page for Catalan numbers contains many examples of problems where these numbers arise. Also, it contains many references, you could start your reading from "Catalan numbers" by Tom Davis. The following elementary book includes Catalan numbers in a series of other types of distinguished number sequences:
      • Conway and Guy (1996), The Book of Numbers.
      You can find the connections to combinatorics of polytopes in Finally, you can go for Catalan numbers page by Igor Pak, where you can find unlimited quantity of selected and sorted by topics information on Catalan numbers.

      email: Anna Felikson