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


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:

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))

# Calculating the first 20 Catalan numbers
for i in range(15):
    print (str(i), '-', catalan(i))


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



Related Images: