Classical combinatorial numbers · Definition

Catalan number

enumerative combinatoricsclassical combinatorial numbers

Catalan numbers appear in counting problems that look quite different from one another. Their study relies on recurrences and on a reflection argument that relates forbidden paths to unrestricted ones.

Definition

The Catalan number \(C_n\) counts, among many other structures, the triangulations of a convex polygon with \(n+2\) sides and the Dyck paths of length \(2n\).

\[C_n=\frac{1}{n+1}\binom{2n}{n}=\frac{(2n)!}{n!\,(n+1)!}\]

Catalan numbers satisfy the recurrence \(C_0=1\) and \(C_{n+1}=\sum_{k=0}^{n} C_k C_{n-k}\), and their ordinary generating function \(C(x)\) satisfies the quadratic equation \(xC(x)^2-C(x)+1=0\). By the reflection principle, the number of Dyck paths of length \(2n\) that never go below the axis equals \(\binom{2n}{n}-\binom{2n}{n+1}\), which yields the closed formula.

For \(n=3\), the formula gives \(C_3=\frac{1}{4}\binom{6}{3}=5\). This value matches the number of ways to parenthesize a product \(x_1x_2x_3x_4\) and the number of triangulations of a convex pentagon.

A typical mistake is confusing \(C_n\) with \(\binom{2n}{n}\): for \(n=3\) the binomial coefficient equals \(20\), while \(C_3=5\). Another common error is forgetting the factor \(\frac{1}{n+1}\) when applying the closed formula.

Think about it

Why does the unrestricted count \(\binom{2n}{n}\) not directly give \(C_n\)?

Because it also counts paths that dip below the axis; the reflection principle subtracts the \(\binom{2n}{n+1}\) that do, leaving \(C_n\).

Exercises 10

  1. What is the value of \(C_2\)?
  2. What is the value of \(C_0\)?
  3. How many distinct triangulations does a convex hexagon have, using diagonals that do not cross in its interior?
  4. In how many different ways can the product \(x_1x_2x_3\) be parenthesized?
  5. Which of the following expressions equals \(C_n\)?
  6. Compute \(C_4\) using the recurrence \(C_{n+1}=\sum_{k=0}^{n} C_k C_{n-k}\) with \(C_0=1\), \(C_1=1\), \(C_2=2\), \(C_3=5\).
  7. Compute \(\binom{10}{5}\) and use it to find \(C_5\) through \(C_n=\frac{1}{n+1}\binom{2n}{n}\).
  8. Compute \(\frac{C_{n+1}}{C_n}\) for \(n=3\) from \(C_3=5\) and \(C_4=14\).
  9. How many Dyck paths of length 6 exist?
  10. Using the generating function \(xC(x)^2-C(x)+1=0\), show that \(C_4=14\) from \(C_0=1\), \(C_1=1\), \(C_2=2\), \(C_3=5\), and check the result with the closed formula.

References

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.