Chapter 1 Introduction to the project

This webpage is for the presentation of The final project for MAA205 - Algorithms for Discrete Mathematics at Ecole Polytechnique provided by Professor Lucas Gerin. The whole project is implemented through Jupyter Notebook. You can find the sources code, pdf version of the project in the following link.

  1. [Source Code]: link
  2. [PDF Report]: link

In this project, we focus on the properties and applications of Catalan number through numerical algorithms and analytical tools.

  • Chapter 2, In this chapter we present the most intuitive algorithms for calculating the catalan number, for example by recursion, iteration or binomial formula, and their corresponding efficiency analysis.

  • Chapter 3, In this part, we first compute the generating functions of catalan numbers and duduce the formula from the generating function. We will also introduce the method with Taylor expansion and compare the efficiency of these approaches. After we will discover Motzkin Numbers and its propositions.

  • Chapter 4, Since the catalan numbers increase pretty fast, therefore in this chapter we try to have analysis using asymptotic analysis as well as algebraic means.

  • Chapter 5, In the last chapter, we will discover some application in Combinatorial mathematics and some paths algorithmic problems.

1.1 Initialization of the Library

## loading python libraries

# necessary to display plots inline:
%matplotlib inline   

# load the libraries
import matplotlib.pyplot as plt # 2D plotting library
import numpy as np              # package for scientific computing  
from pylab import *

from math import *              # package for mathematics (pi, arctan, sqrt, factorial ...)
import sympy as sympy             # package for symbolic computation
from sympy import *