Euler’s Polygon Triangulation Problem

Problem

Let P be a convex polygon with \(n \) sides. Calculate in how many different ways the polygon can be divided into triangles using diagonals that do not intersect each other in the interior of P.

This problem was proposed by Euler in 1751 to his friend Christian Goldbach. The number of the different triangulations found by Euler, indicated with \(E_ {n} \), is the following:

\[ E_{n} = \frac {2 \cdot 6 \cdot 10 \cdots (4n-10)}{(n-1)!} \]

If \(n = 3 \) we have \(E_{3} = 1 \).
If \(n = 4\) we have \(E_{4} = 2 \).
In the case of a pentagon we have \(E_{5} = 5 \), as can be seen from the following table:

1) Solution with the generating function method

Let’s consider a polygon of \(n \) sides with the vertices labeled as \(v_{1}, v_{2}, \cdots v_{n} \). Let \(E_{n} \) denote the number of different decompositions in triangles for a polygon of \(n \) sides. Let’s take any side, for example the side with vertices \(v_{1}, v_{2} \). It is evident that this side will be the basis of a triangle in each of the \(E_{n} \) decompositions. To the triangle with vertices \(v_{1}, v_{2}, v_{3} \) correspond \(E_{n-1} \) decompositions. To the triangle of vertices \(v_{1}, v_{2}, v_{4} \) correspond \(E_ {3} E_ {n-2} \) decompositions, and so on. These decompositions are all distinct, therefore the total number of triangulations is given by the following formula:

\[ E_{n}= E_{2}E_{n-1} + E_{3}E_{n-2} + \cdots + E_{n-1}E_{2} \]

where we place for uniformity \(E_{2} = 1 \). This recurrence formula was introduced by Segner in 1758.
Now let’s compute the generating function of the numbers \(E_ {n} \):

\[ F(x) = E_{0} + E_{1}\cdot x + E_{2} \cdot x^2 + E_{3}\cdot x^{3}+ \cdots \]

where \(E_{0} = E_{1} = 0 \).

If we calculate the square of the \(F (x) \), with the product rule between two polynomials, we have:

\[ (F(x))^{2} = E_{3}\cdot x^{4} + E_{4}\cdot x^{5} + E_{5} \cdot x^{6} + \cdots \]

by virtue of the recurrence equation satisfied by the coefficients \(E_ {n} \). With simple steps we can write the functional equation satisfied by the function \(F (x) \):

\[ F(x)^2 – xF(x) + x^{3} = 0 \]

The initial conditions are \(F (0) = 0 \) and \(F’ (0) = 0 \), where the symbol \(F’ (0) \) denotes the derivative calculated at the point \(x = 0\). Solving with respect to \(F (x) \) and taking into account the initial conditions, we find the following solution (the other with the positive sign is discarded):

\[ F(x)= x \left(\frac{1- \sqrt{1- 4x}}{2}\right) \]

We now use the Taylor-McLaurin series development of the function \(\sqrt{1-4x} \), that is Newton’s binomial formula, valid for \(| x | <1 \) and for every real number \(\alpha \):

\[ \begin{array}{l} (1+t)^{\alpha} &= \sum\limits_{k=0}^{\infty} \dbinom{\alpha}{k} t^{k} \\ &= 1 + \alpha t + \dfrac{\alpha \cdot (\alpha -1)t^{2}}{2!}+ \dfrac{\alpha \cdot (\alpha -1)(\alpha -2)t^{3}}{3!} + \cdots \\ \end{array} \]

In our case \(\alpha = \frac{1}{2}\) and \(t = -4x \). The binomial coefficient \(\dbinom{\frac {1}{2}}{n} \) has the following expression:

\[ \dbinom{\frac {1}{2}}{n} =\frac{\left(\frac{1}{2}\right)\left(\frac{-1}{2}\right)\left(\frac{-3}{2}\right) \cdots \left(\frac{-(2n-3)}{2 }\right)}{n!}=\frac{(-1)^{n-1}}{2^{2n-1}n}\binom{2n-2}{n-1} \]

where we used the following formula, which is easily proved by the induction method:

\[ 1 \cdot 3 \cdot 5 \cdots \cdot (2n-1)= \frac {(2n)!}{2^{n}n!} \]

Continuing we have:

\[ \binom {\frac {1}{2}}{n}(-4)^{n}=\left(\frac{-2}{n}\right)\binom {2n-2}{n-1} \]

Finally, putting together what we have found, we have that the coefficient of the power \(x^{n}\) in the generating function \(F (x) \) is:

\[ E(n)=\frac {1}{n-1} \binom {2n-4}{n-2} \]

The expression found coincides with the Catalan number \(C_{n-2}\), where \(C_{n} = \dfrac {1} {n + 1} \dbinom {2n} {n} \) and \(C_{0} = 1 \). Recall that sometimes \(C_{n + 1} \) is written in place of \(C_{n} \); this depends on the choice of the initial values ​​of the sequence \(C_{n} \).

For an exhaustive study about the properties and applications of Catalan numbers, see the text ^[1] (available on Amazon.com).

Exercise 1
Prove the following recurrence formula for the Catalan numbers, for \(n> 0\):

\[ C_{n+1} = \frac{2(2n+1)}{n+2} C_{n} \]

Exercise 2
Prove the following recurrence formula for \(E (n) \):

\[ E(n+1) = \frac{4n-6}{n}E(n) \quad n \gt 2 \]

Exercise 3
Prove that even the formula found by Euler

\[ E(n) = \frac{2 \cdot 4 \cdot 6 \cdots \cdot (4n-10)}{(n-1)!} \]

verifies the same recurrence equation of exercise 2.

2) The Lamé solution

The French mathematician Lamé (1795-1870) solved the problem with a different strategy. Instead of using one side of the polygon to enumerate triangles, he used diagonals. To each of the \((n-3)\) diagonals which can be drawn from a vertex corresponds a group of decompositions, where the diagonal is one side of two adjacent triangles. The problem that arises is that not all decomposition triangles are counted if we start from a single diagonal. However, if we do this operation starting from every vertex of the polygon, then all triangles are certainly included, and we get this total number:

\[ n(E_{3}E_{n-1}+ E_{4}E_{n-2} + \cdots +E_{n-1}E_{3}) \]

However, in this way the triangles are counted several times. To calculate the exact number \(E (n) \), we must therefore avoid counting the same decomposition several times. For this we imagine an arbitrary decomposition of \(n-2 \) triangles, with \(3 (n-2) \) sides. We remove from it the sides of the polygon and then divide by two, obtaining \(n-3\), which corresponds to the number of diagonals that appear in the given decomposition. This particular decomposition is repeated for as many as the extremes of these diagonals are, that is \(2n-6 \). Using this repetition factor, Lamé calculated the total number of decompositions as follows:

\[ E(n) = \frac{n(E_{3}E_{n-1}+ E_{4}E_{n-2} + \cdots +E_{n-1}E_{3})}{2n-6} \]

Exercise 4
Prove the recurrence formula

\[ E_{n+1}=\frac {4n-6}{n} E_{n} \]

without using the expression of Catalan numbers.

Proof
We first write the recurrence equation for a polygon of \(n + 1 \) sides:

\[ E_{n+1}= E_{2}E_{n} + E_{3}E_{n-1} + \cdots + E_{n-1}E_{3} + E_{n}E_{2} \]

By combining this formula with the expression found by Lamé we easily prove the recurrence formula.

---

Bibliography

^[1]R. Stanley – Catalan Numbers (Cambridge University Press)