Skip to main content

Chapter 10 Catalan Numbers

Exercises Practice Problems

1. Triangulating a convex \((n+2)\)-gon.

A triangulation of a convex \(n+2\)-gon consists of \(n-1\) diagonals so that (a) the diagonals do not intersect, and (b) the interior is partitioned into \(n\) triangles.

Here are the triangulations for \(n=0\text{,}\) \(n=1\) and \(n=2\text{,}\) which correspond to \(2\)-gons, \(3\)-gons and \(4\)-gons, respectively.

  1. List the 5 ways to triangulate a 5-gon. This corresponds to Catalan number \(C_3=5\text{.}\)

  2. In this problem, you will list the ways to triangulate a 6-gon. This corresponds to Catalan number \(C_4=14\text{.}\)

    1. For now, draw your 6-gons with the corners labeled \(0,1,2,3,4,5\text{.}\) The edge \((0,5)\) must be in some triangle. List the FOUR ways that you can complete the triangle that contains the edge \((0,5)\text{.}\)

    2. For each of your answers in part (a), list all the ways to complete the triangulation of the 6-gon.

    3. Explain how part (b) relates to the Catalan recurrence \(C_4 = C_0C_3 + C_1 C_2 + C_2 C_1 + C_3 C_0.\) In particular, treat the triangle containing the edge \((0,5)\) as special.

2. Some Catalan Families.

Here are a few different Catalan families. We illustrate the elements for \(n=3\text{,}\) hoping that these examples will make any undefined terminology clear.

For each family, you should

  • List all of the examples for \(n=0,1,2,3,4\text{.}\)

  • Show that this problem is counted by the Catalan numbers. You can either:

    • Describe a bijection (reversible mapping) to a known Catalan problem

    • Explain how this problem satisfies the Catalan recurrence \[ C_n = C_0 C_{n-1} + C_1 C_{n-2} + \cdots + C_{n-1} C_0. \]

  1. A Nondecreasing Sequence. Sequences \(0 \leq a_1 \leq a_2 \cdots \leq a_n \leq n-1\) of integers with \(a_i \leq i-1\text{.}\)

    \begin{equation*} \begin{array}{ccccc} 000 & 001 & 002 & 011 & 012 \end{array} \end{equation*}

  2. Young tableaux of Form \((n,n)\text{.}\) Make a Young tableau of the form \((n,n)\text{.}\) This consists of two rows of length \(n\text{.}\) The numbers \(1,2,\ldots 2n\) are placed in these rows so that

    • the numbers are increasing in each row

    • the numbers are increasing in each column

    \begin{equation*} \begin{array}{ccccc} \begin{array}{c} 135 \\ 246 \end{array} & \begin{array}{c} 134 \\ 256 \end{array} & \begin{array}{c} 125 \\ 346 \end{array} & \begin{array}{c} 124 \\ 356 \end{array} & \begin{array}{c} 123 \\ 456 \end{array} \end{array} \end{equation*}

  3. Stacking Coins in the Plane. Stack coins in the plane, where the bottom row consists of \(n\) consecutive coins.

  4. Plane Binary Trees with \(2n\) Edges. Make plane binary trees with \(2n\) edges. A plane binary tree has a root vertex. When \(n>0\text{,}\) the root vertex is incident with 2 edges. All other vertices are incident with either 3 edges or 1 edge.

  5. Non-Nested Arcs. Start with \(2n\) points arranged in a line. Connect the points with \(n\) arcs to that

    • the arcs line above the line of points

    • No arc is contained entirely below another arc

    .

  6. Staircase Partitions. A staircase of size \(n\) consists of \(n\) rows of boxes, where the \(i\)th row contains \(n+1-i\) boxes. A staircase partition is a division of a staircase into \(n\) rectangles.