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)

Shortest Path

DEFINITION: A $\boldsymbol{p \times q}$-grid is a collection of $pq$ squares of side length 1, organized as a rectangle of side length $p$ and $q$.

THEOREM: The number of shortest paths from $(0,0)$ to $(p,q)$ is $\displaystyle\frac{(p+q)!}{p!q!}$.

• Let $A = \{p \cdot \rightarrow, q \cdot \uparrow\}$ be a $(p+q)$-multiset.
• The number of shortest paths $=$ the number of permutations of $A$.

T-Route

DEFINITION: Let $A = (x, y), B \in \mathbb{Z}^2$. // integral (lattice) points

• A T-Step at $A$ is a segment from $A$ to $(x + 1, y + 1)$ or $(x + 1, y – 1)$.
• A T-Route from $A$ to $B$ is a route where each step is a T-step.

THEOREM: There is a T-route from $A = (a, \alpha)$ to $B = (b, \beta)$ only if (1) $b > a$; (2) $b – a \geq |\beta – \alpha|$; and (3) $2 \mid (b + \beta – a – \alpha)$.

• Let $A = P_0, P_1, \dots, P_k = B$ be a T-route from $A$ to $B$, where $P_i = (x_i, y_i)$.
  • $x_0 = a, y_0 = \alpha$; $x_k = b, y_k = \beta$;
  • $x_i – x_{i-1} = 1$; $y_i – y_{i-1} \in \{\pm 1\}$ for every $i = 1,2, \dots, k$
• $b – a = x_k – x_0 = (x_k – x_{k-1}) + (x_{k-1} – x_{k-2}) + \dots + (x_1 – x_0) = k > 0$
• $\beta – \alpha = y_k – y_0 = (y_k – y_{k-1}) + (y_{k-1} – y_{k-2}) + \dots + (y_1 – y_0)$
  • $|\beta – \alpha| \leq |y_k – y_{k-1}| + |y_{k-1} – y_{k-2}| + \dots + |y_1 – y_0| = k = b – a$
• $b + \beta – a – \alpha = \sum_{i=1}^k (y_i – y_{i-1} + x_i – x_{i-1})$
  • $y_i – y_{i-1} + x_i – x_{i-1} \in \{0,2\}$
  • $2 \mid (b + \beta – a – \alpha)$

REMARK: The T-condition (1)+(2)+(3) is sufficient for the existence of a T-route.

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