Skip to content
Econowmics
Menu
  • Home
  • Economics
    • Econometrics
    • Economics and History
    • Macroeconomics
    • Microeconomics
    • Miscellaneous
      • Awards and Honors
      • Economic Schools of Thought
      • Economic Quotes
      • Economic Videos
    • Terms and Concepts
  • Cognitive Biases
  • Data Analysis
    • Statistics
    • Python Programming
  • Contact
Menu

[Python] Catalan Numbers

Posted on

 

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 - Econowmics
Photo by George Pagan III on Unsplash

 

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

  • 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

 

 

Related posts:

[Python] Law of Large Numbers: Dice Roll
[Python] Greatest Common Factor
[Python] Pi Estimation Using Monte Carlo Method
[Python] Prime number generator
Benford's Law

Anything in here will be replaced on browsers that support the canvas element

  • Amos Tversky
  • Daniel Kahneman
  • cognitive bias
  • Milton Friedman
  • Wealth of Nations
  • Nobel Prize Laureate
  • Adam Smith
  • 20:20 ratio
  • law of small numbers
  • the halo effect
  • wealth inequality
  • income inequality
  • Law of Large Numbers
  • Dow Jones Industrial Average
  • status quo bias
  • Behavioral Economics
  • daniel kahnemann
  • hyperinflation
  • the gambler's fallacy
  • gambler's fallacy
©2023 Econowmics | Design: Newspaperly WordPress Theme