[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:

N 4 5 6 7 8 9 10
Expressions 14 42 132 429 1430 4862 16796

 

This sequence is referred to as Catalan numbers.

 

The Catalan numbers are named after the Belgian mathematician Eugène Charles Catalan. However, in the 18th 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.

Triangle

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

Squares

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

Polygon

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:

Catalan Numbers - Formula - Econowmics

 

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:

 

# Econowmics.com

# First I import the factorial module
from math import factorial

# function to calculate the catalan number
def catalan(n):
    '''calculates the n-th Catalan number'''
    
    return factorial(2 * n) // (factorial(n+1) * factorial(n))

 

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:

First 20 Catalan numbers

 


Also watch

 


Further reading