[Python] Catalan Numbers

 

You cannot evade quantity. You may fly to poetry and music, and quantity and number will face you in your rhythms and your octaves.

Alfred North Whitehead

Catalan numbers are a sequence of natural numbers with applications in many counting problems and combinatorial mathematics. To shed some light on this, let’s consider some examples.

Suppose we want to write some valid expressions, where each expression consists of n right parenthesis and n left parenthesis. Let’s consider the first few values of n.

For n = 0, we can create no such expression.

When n = 1, we only have one possibility:

• ()

For n = 2, there will be two possibilities:

• () ()
• (())

When n = 3, there will be 5 possibilities:

• () () ()
• () (()), (()) ()
• (() ())
• ((()))

Continuing in this fashion, the possibilities grow as follows:

This sequence is referred to as Catalan numbers.

The Catalan numbers are named after the Belgian mathematician Eugène Charles Catalan. However, in the 18^th century, Leonhard Euler had also refered to this sequence in a letter to Christian Goldbach. Euler had found the number of possible ways to triangulate a polygon.

Suppose that we want to count the number of different ways that we can divide a convex polygon with n+2 sides into triangles, by connecting its vertices with non-crossing line segments.

If n=1, then the polygon will have 3 sides and will be a triangle itself. So there is 1 possibility.

If n = 2, we can divide the resulting polygon into triangles in 2 different ways.

If n = 3, there will 5 possibilities to create triangles.

And so on, the number of possible triangulations for the polygons increases according to the Catalan sequence.

Calculating Catalan numbers

Using binomial coefficients, the n-th Catalan number can be calculated using this formula:

Hence, writing a code to calculate the n-th Catalan number in Python will be easy peasy lemon squeezy. Let’s jump to the code:

The code uses the factorial module to calculate the numerator and the denominator and returns the result of dividing them. Here are the first 20 Catalan numbers:

Also watch

Further reading

• Here you can find many applications of the Catalan numbers
  Exercises on Catalan and Related Numbers
  
• MIT Combinatorics Seminar
  Catalan Numbers: From EGS to BEG