Catalan Number

Triangulation of Convex Polygons

${\mathcal{P}_{n+2}}$$(n \geq 0)$: convex $(n+2)$-polygons (interior angles $\leq 180^\circ$, vertices point outward)

DEFINITION: A triangulation of $\mathcal{P}_{n+2}$$(n \geq 0)$ is a set of $n-1$ diagonals of $\mathcal{P}_{n+2}$ which do not cross in their interiors.

The $n$th Catalan Number$C_n$ (Euler, 1751): # of triangulations of $\mathcal{P}_{n+2}$$(C_0 = 1)$

Earlier findings: Ming Antu (1692-1763) in Qing court (China), established the following formula in “Quick Methods for Accurate Values of Circle Segments”:

Recurrence Relation: $C_{n+1} = \sum_{k=0}^n C_k C_{n-k}$, $C_0 = 1$

• $\mathcal{P}_{n+3}$ has $C_{n+1}$ triangulations
• After removing an edge $e$, each triangulation of $\mathcal{P}_{n+3}$ gives
  • a triangulation for $\mathcal{P}_{a+2}$ and a triangulation for $\mathcal{P}_{b+2}$
  • $a + b = n$

Binary Trees

DEFINITION: A binary tree is defined recursively as follows.

• The empty set $\emptyset$ is a binary tree.
• Otherwise, a binary tree has a root vertex $v$, a left subtree $T_{1}$, and a right subtree $T_{2}$, both of which are binary trees.
  • left child: the root of $T_{1}$ ; right child: the root of $T_{2}$

THEOREM: The number of binary trees with $n$ vertices is $C_{n}$

• proof is omitted

Plane Trees

DEFINITION: A plane tree (ordered tree) is defined recursively as follows.

• A single vertex $v$ is a plane tree. And the vertex is called the root of the tree.
• Otherwise, a plane tree has a root vertex $v$, and a sequence $(P_{1}, \dots, P_{m})$ of subtrees, each of which is a plane tree.

THEOREM: The number of plane trees with $n+1$ vertices is $C_{n}$.

• proof is omitted

Parenthesization

DEFINITION: A parenthesization (or bracketing) of a string of $n+1$ symbols $x_{0}, x_{1}, \dots, x_{n}$ consists of the insertion of $n$ left parentheses and $n$ right parentheses that define $n$ binary operations on the string.

• Eugêne Charles Catalan (1814-1894) studied this problem in 1838

EXAMPLE: There are five parenthesizations on four symbols $x_{0},x_{1},x_{2},x_{3}$

• $\left(\left(\left(x_{0} x_{1}\right) x_{2}\right) x_{3}\right)$;
• $\left(\left(x_{0} x_{1}\right)\left(x_{2} x_{3}\right)\right)$;
• $\left(\left(x_{0}\left(x_{1} x_{2}\right)\right) x_{3}\right)$;
• $\left(x_{0}\left(\left(x_{1} x_{2}\right) x_{3}\right)\right)$;
• $\left(x_{0}\left(x_{1}\left(x_{2} x_{3}\right)\right)\right)$

THEOREM: The number of parenthesizations of a string of $n+1$ symbols is $C_{n}$.

• proof is omitted

Ballot sequence

DEFINITION: A ballot sequence of length $2n$ is a sequence of $1$‘s and $-1$‘s, where

• the number of $1$‘s is equal to the number of $-1$‘s; and
• the sum of every prefix of the sequence is nonnegative.

Bertrand’s Ballot Problem (special case): There are two candidates A and B in an election. Each receives $n$ votes. What is the probability $p_{n}$ that A will never trail B during the count of votes?

• First published by W. A. Whitworth (1840-1905) in 1878
• Named after Joseph Louis Francois Bertrand (1822-1900) who rediscovered it in 1887.

EXAMPLE: AABABBBAAB is bad, since among the first 7 votes, A receives 3 but B receives 4 , which is greater than 3.

THEOREM: The number of Ballot sequences of length $2n$ is $C_{n}$.

• proof is omitted

Dyck path

DEFINITION: A Dyck path of length $2n$ is a sequence $P_{0}=(x_{0}, y_{0})=(0,0)$, $P_{i}=(x_{i}, y_{i})$$(1\leq i<2n)$, $P_{2n}=(x_{2n}, y_{2n})=(2n, 0)$ of $2n+1$ lattice points (points with integral entries) such that

• $(x_{i+1}, y_{i+1})-(x_{i}, y_{i}) \in \{(1,1),(1,-1)\}$ for all $i=0,1, \dots, 2n-1$
• $y_{i}\geq 0$ for all $i=0,1, \dots, 2n$

THEOREM: The number of Dyck paths of length $2n$ is $C_{n}$.

REMARK: Dyck path may be called T-route generally. The name of “Dyck path” is in memory of German mathematician Walther von Dyck (1856-1934)

THEOREM: Let $A = (a, \alpha), B = (b, \beta) \in \mathbb{Z}^2$ satisfy the T-condition, where $\alpha, \beta > 0$. Then # of T-routes from $A$ to $B$ that do not intersect the x-axis is