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