\documentclass[11pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{amsfonts}
\usepackage{epsfig}
\setlength{\topmargin}{-.55in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.1in}
\newcommand{\br}{\mathbf {R}}
\newcommand{\bq}{\mathbf {Q}}
\newcommand{\bz}{\mathbf {Z}}
\newcommand{\bn}{\mathbf {N}}
\newcommand{\z}{$\circ$}
\newcommand{\lph}{$\leftharpoondown$}
\begin{document}
\title{Counting Triangulations of a Convex Polygon}
\author{Desh Ranjan \footnote{Department of Computer Science; New Mexico State University; Las Cruces, NM 88003;
\texttt{dranjan@cs.nmsu.edu}.}\thinspace\footnote{With thanks to David Pengelley, Inna Pivkina and Karen Villaverde.}\smallskip}
\date{}
\maketitle
\section*{Introduction}
In a 1751 letter to Christian Goldbach (1690--1764), Leonhard Euler (1707--1783) discusses the problem of counting
the number of triangulations of a convex polygon. Euler, one of the most prolific mathematicians of all times, and
Goldbach, who was a Professor of Mathematics and historian at St. Petersburg and later served as a tutor for Tsar Peter II,
carried out extensive correspondence, mostly on mathematical matters. In his letter, Euler provides a ``guessed'' method
for computing the number of triangulations of a polygon that has $n$ sides but does not provide a proof of his method.
The method, if correct,
leads to a formula for calculating the number of triangulations of an $n$-sided polygon which can be used to quickly
calculate this number \cite[p.\ 339-350]{DREuler1751} \cite{DREuler1758}.
Later, Euler communicated this problem to the Hungarian mathematician Jan Andrej Segner (1704--1777). Segner, who spent most
of his professional
career in Germany (under the German name Johann Andreas von Segner), was the first Professor of Mathematics at the University
of G\"{o}ttingen, becoming the chair in 1735. Segner ``solved'' the problem by providing a proven correct method for computing
the number of triangulations of a convex $n$-sided polygon using the number of triangulations for polygons with fewer
than $n$ sides \cite{DRSegner1756}. However, this method did not establish the validity (or invalidity) of Euler's guessed method.
Segner communicated
his result to Euler in 1756 and in his communication he also calculated the number of triangulations for the $n$-sided
polygons for $n =1 \ldots 20$ \cite{DRSegner1756}. Interestingly enough, he made simple arithmetical errors in calculating the
number of triangulations
for polygons with 15 and 20 sides. Euler corrected these mistakes and also calculated the number of triangulations for
polygons with up to 25 sides. It turns out that with the corrections, Euler's guessed method gives the right number
triangulations of polygons with up to 25 sides.
Was Euler's guessed method correct? It looked like it was but there was no proof. The problem was posed as an
open challenge to the mathematicians by Joseph Liouville (1809--1882) in the late 1830's. He received solutions or purported
solutions to the problem by many mathematicians (including one by Belgian mathematician Catalan which was correct but not so
elegant),
some of which were later published in the Liouville journal, one of the primary
journals of mathematics at that time and for many decades.
The most elegant of these solutions was communicated to him
in a paper by Gabriel Lam\'e (1795-1870) in 1838.
French mathematician, engineer and physicist Lam\'e was educated at
the prestigious Ecole Polyt\'echnique and later at the Ecole des
Mines\cite[p.\ 601--602]{DRGillispie}. From 1832 to 1844 he served as the
chair of physics at the
Ecole Polyt\'echnique, and in 1843 joined the Paris Academy of
Sciences in the geometry section. He contributed to the fields of
differential geometry, number theory, thermodynamics and applied
mathematics. Among his publications are textbooks in physics and
papers on heat transfer, where he introduced the rather useful
technique of curvilinear coordinates. In 1851 he was appointed
Professor of Mathematical Physics and Probability at the University of
Paris, and resigned eleven years later after becoming deaf. Gauss
considered Lam\'e the foremost French mathematician of his day
\cite[p.\ 601--602]{DRGillispie}.
A translated version of this paper by Lam\'e is the key historical source for this
project. This translation is presented in its entirety before the description of the
major project tasks in the next section. Interestingly and perhaps somewhat ironically,
today these numbers (the number of triangulations of an $n$ sided polygon for $n = 1,2,3 \ldots$))
are called {\em Catalan numbers}. Although none of Segner, Euler or
Catalan provided any insight into why they were interested in calculating the number
of triangulations of convex polygons. However, the related problem of computing optimal polygon
triangulations has become a well-studied problem in the realm of algorithm design and is
fairly commonly used to illustrate the effectiveness of dynamic programming paradigm
for designing efficient algorithms.
\section*{Understanding Triangulations}
A {\em diagonal} in a (convex) polygon is a straight line that connects two non-adjacent
vertices of the polygon. Two diagonals are different if they have at least one different endpoint.
A {\em triangulation} of a polygon is a division of the polygon into triangles
by drawing {\em non-intersecting} diagonals. For example, the 6-sided polygon $ABCDEF$ below
is triangulated into 4 triangles by using the diagonals $AD, AE, BD$.
\begin{figure}[h]
\centerline{\epsfig{figure=t1.eps, height = 1.52 in, width= .50\textwidth}}
\caption{A Triangulation of $ABCDEF$}
\end{figure}
Two triangulations are different if
at least one of the diagonals in a triangulation is different from all diagonals in the
other triangulation.\\
\\
\noindent{\bf TASKS:}
\begin{itemize}
\item[1.1] Draw a triangulation of $ABCDEF$ that is different from the triangulation in Figure 1. How many
diagonals does your triangulation have? How many triangles does it divide $ABCDEF$ into?
\item[1.2] Consider an $n$-sided polygon $A_1A_2\ldots A_n$. How many different possible diagonals does this
polygon have? {\bf Note:} We are talking about all possible diagonals, not just diagonals in a triangulation.
\item[1.3] Use mathematical induction to prove that any triangulation of an $n$ sided
polygon has $n-2$ triangles and $n-3$ diagonals.
\end{itemize}
Let's now read from Lam\'e's letter to Liouville \cite{DRLame}.
\begin{quote}{\sf
\begin{center}
Excerpt from a letter of Monsieur Lam\'{e} to Monsieur Liouville on the
question: Given a convex polygon, in how many ways can one partition it into
triangles by means of diagonals?\footnote{See a Memoir of Segner (\emph{Novi
Commentarii Acad.\ Petrop}., vol.\ VII, p.\ 203). The author found equation
(1) of M. Lam\'{e}; but formula (3) presents a much simpler solution. Formula
(3) is no doubt due to Euler. It is pointed out without proof on page 14 of
the volume cited above. The equivalence of equations (1) and (3) is not easy
to establish. M. Terquem proposed this problem to me, achieving it with the
help of some properties of factorials. I then communicated it to various
geometers: none of them solved it; M. Lam\'{e} has been very successful: I am
unaware of whether others before him have obtained such an elegant solution.
\quad\textsc{J. Liouville}}
%Translation copyright \copyright \ 2004 by David Pengelley
%(Individual educational use only of this translation \linebreak may be made
%without permission)
\bigskip
%Extrait d'une lettre de M. Lam\'{e} \`{a} M. Liouville sur cette question: Un
%polygone convexe \'{e}tant donn\'{e}, de combien de mani\`{e}res peut-on le
%partager en triangles au moyen de diagonales?
%\emph{Journal de Math\'{e}matiques Pures et Appliqu\'{e}es (Journal de
%Liouville)} \linebreak\textbf{3} (1838), 505--507.
%(http://math-doc.ujf-grenoble.fr/JMPA/)
%(http://gallica.bnf.fr/Catalogue/noticesInd/FRBNF34348784.htm)
\bigskip
\end{center}
%\textquotedblleft
The formula that you communicated to me yesterday is easily
deduced from the comparison of two methods leading to the same goal.
%\textquotedblleft
Indeed, with the help of two different methods, one can
evaluate the number of decompositions of a polygon into triangles: by
consideration of the sides, or of the vertices.
\begin{center}
\medskip
I.
\medskip
\end{center}
%\textquotedblleft
Let $ABCDEF\ldots$ be a convex polygon of $n+1$ sides, and
denote by the symbol $P_{k}$ the total number of decompositions of a polygon
of $k$ sides into triangles. An arbitrary side $AB$ of $ABCDEF\ldots$ serves
as the base of a triangle, in each of the $P_{n+1}$ decompositions of the
polygon, and the triangle will have its vertex at $C$, or $D$, or $F\ldots$ ;
to the triangle $CBA$ there will correspond $P_{n}$ different decompositions;
to $DBA$ another group of decompositions, represented by the product
$P_{3}P_{n-1}$; to $EBA$ the group $P_{4}P_{n-2}$; to $FBA$, $P_{5}P_{n-3}$;
and so forth, until the triangle $ZAB$, which will belong to a final group
$P_{n}$. Now, all these groups are completely distinct: their sum therefore
gives $P_{n+1}$. Thus one has
\begin{multline}
P_{n+1}=\tag{1}\\
P_{n}+P_{3}P_{n-1}+P_{4}P_{n-2}+P_{5}P_{n-3}+\cdots+P_{n-3}P_{5}+P_{n-2}%
P_{4}+P_{n-1}P_{3}+P_{n}\text{.}%
\end{multline}
\begin{center}
\medskip
II.
\medskip
\end{center}
Let $abcde\ldots$ be a polygon of $n$ sides. To each of the
$n-3$ diagonals, which end at one of the vertices $a$, there will correspond a
group of decompositions, for which this diagonal will serve as the side of two
adjacent triangles: to the first diagonal $ac$ corresponds the group
$P_{3}P_{n-1}$; to the second $ad$ corresponds $P_{4}P_{n-2}$; to the third
$ae$, $P_{5}P_{n-3}$, and so forth until the last $ax$, which will occur in
the group $P_{3}P_{n-1}$. These groups are not totally different, because it
is easy to see that some of the partial decompositions, belonging to one of
them, is also found in the preceding ones. Moreover they do not include the
partial decompositions of $P_{n}$ in which none of the diagonals ending in $a$ occurs.
But if one does the same for each of the other vertices of
the polygon, and combines all the sums of the groups of these vertices, by
their total sum
$$ n\left( P_{3}P_{n-1}+P_{4}P_{n-2}+\cdots+P_{n-2}
P_{4}+P_{n-1}P_{3}\right) $$
one will be certain to include all the partial
decompositions of $P_{n}$; each of these is itself repeated therein a certain
number of times.
Indeed, if one imagines an arbitrary such decomposition, it
contains $n-2$ triangles, having altogether $3n-6$ sides; if one removes from
this number the $n$ sides of the polygon, and takes half of the remainder,
which is $n-3$, one will have the number of diagonals appearing in the given
decomposition. Now, it is clear that this partial decomposition is repeated,
in the preceding total sum, as many times as these $n-3$ diagonals have ends,
that is $2n-6$ times: since each end is a vertex of the polygon, and in
evaluating the groups of this vertex, the diagonal furnished a group including
the particular partial decomposition under consideration.
Thus, since each of the partial decompositions of the total
group $P_{n}$ is repeated $2n-6$ times in $n\left( P_{3}P_{n-1}+P_{4}%
P_{n-2}+\cdots+P_{n-2}P_{4}+P_{n-1}P_{3}\right) $, one obtains $P_{n}$ upon
dividing this sum by $2n-6$. Therefore one has
\begin{equation}
P_{n}=\frac{n\left( P_{3}P_{n-1}+P_{4}P_{n-2}+\cdots+P_{n-2}P_{4}%
+P_{n-1}P_{3}\right) }{2n-6}\text{.} \tag{2}%
\end{equation}
\begin{center}
\medskip
III.
\medskip
\end{center}
The first formula (1) gives
\[
P_{3}P_{n-1}+P_{4}P_{n-2}+\cdots+P_{n-2}P_{4}+P_{n-1}P_{3}=P_{n+1}%
-2P_{n}\text{,}%
\]
and the second (2) gives
\[
P_{3}P_{n-1}+P_{4}P_{n-2}+\cdots+P_{n-2}P_{4}+P_{n-1}P_{3}=\frac{2n-6}{n}%
P_{n}\text{;}%
\]
so finally
\[
P_{n+1}-2P_{n}=\frac{2n-6}{n}P_{n}\text{,}%
\]
or
\begin{equation}
P_{n+1}=\frac{4n-6}{n}P_{n}\text{.}\tag{3}%
\end{equation}
This is what was to be proven.
\medskip
\hfill{\small Paris, 25 August, 1838}
}\end{quote}
\section*{Optimal Triangulation and Counting Triangulations}
The {\em Optimal Polygon Triangulation} Problem is the following: Given an $n$-sided polygon
$A_1A_2\ldots A_n$
and a weight $w_{i,j}$ for each diagonal $A_iA_j$, find a triangulation of the polygon such that the
sum of the weights of the diagonals in the triangulations is minimized.
A na\"{i}ve way to solve the problem is to generate all possible triangulations one by one, calculate their
weight (i.e. sum of weights of all the diagonals in the triangulation) and keep the best. The efficiency
of this na\"{i}ve method depends on the number of possible triangulations of a polygon with $n$ sides. Thus,
we would like to count how many different triangulations an $n$-sided polygon has. As mentioned in the introduction,
the problem of counting the number of triangulations of an $n$-sided convex polygon was already being discussed
in the mid eighteenth century by well-known figures in mathematics like Euler and Segner and an elegant solution
was provided by Lam\'e in 1838. As noted before, the numbers $P_n$ in Lam\'{e}'s paper are now called Catalan numbers.\\
\\
\noindent{\bf TASKS:}
\begin{itemize}
\item[2.1] Read Section I in Lam\'{e}'s paper. Explain what Lam\'{e} is saying in your own words
and derive the general recursive formula for $P_{n+1}$, i.e., formula (1) in Lam\'{e}'s paper.
\item[2.2] Use the recursive formula to calculate $P_i$ for $i=2,3,4,5,6,7,8$ by hand and display it as a table.
\item[2.3] Draw all triangulations of polygons with $n$ sides for $n=4,5$.
\item[2.4] Lam\'{e}'s recurrence relation in his section 1 for $n=5$ yields
$P_6 = P_5 + P_3P_4 +P_4P_3 + P_5$.
Draw all triangulations of a $6$-sided polygon classified into groups according to
the idea of the recurrence relation, i.e., the triangulations should be classified into
four groups with each group corresponding to a term on the right-hand side of the recurrence above.
\item[2.5] Write a simple recursive function $SRCAT(n)$ (for ''Simple Recurrence CATalan") in Java that given an input $n$ calculates $P_n$ using
the recurrence relation (1) in Lam\'{e}'s paper directly.
\item[2.6] Write another Java program that repeatedly uses $SRCAT$ to calculate $P_i$ for $i=3,4,5\ldots$ Restrict
the total time your program uses to 10 minutes. What is the largest value $N_0$ of $i$ for which your program
calculates $P_i$? Print out a table with $i$ and the time required in seconds
by $SRCAT$ to calculate each of the $P_i$ values. Your table should have a row for each $i=3,4,5\ldots, N_0$.
\item[2.7] From your calculations you may observe that it seems that for all $n$,
if $n \geq 3$ then $P_{n+1} \geq 2*P_n$.
Give a simple mathematical argument that establishes the truth of this statement.
\item[2.8] Prove that for all $n$, if $n \geq 3$ then $P_n \geq 2^n/8$.
\item[2.9] What does this tell you about the efficiency of the na\"{i}ve algorithm for solving
the optimal polygon triangulation problem?
\item[2.10] Write a Java program that repeatedly uses the recurrence given in formula (1) in Lam\'{e}'s paper
to calculate $P_i$ for $i=3,4,5\ldots$ but that stores the computed values in
an array systematically and uses them as needed. Restrict
the total time your program uses to 10 minutes. What is the largest value $M_0$ of $i$ for which your program
calculates $P_i$?
\item[2.11] Extend your program to print out a table of values of $i$ and time required in seconds to compute
$P_i$ for $i=3,4,\ldots, M_0$.
\item[2.12] Graph the tables obtained in 2.6 and 2.11.
Analyse these graphs and write down your observations.
\end{itemize}
\section*{Lam\'{e}'s Method for deriving a formula for $P_n$}
Section II of Lam\'{e}'s paper gives an alternative way of counting triangulations of a polygon.
Read this section carefully.\\
\\
\noindent{\bf TASKS:}
Consider a 6-sided polygon $ABCDEF$.
\begin{itemize}
\item[3.1] Draw all triangulations of the polygon where:
\begin{itemize}
\item $AC$ is one of the diagonals in the triangulation.
\item $AD$ is one of the diagonals in the triangulation.
\item $AE$ is one of the diagonals in the triangulation.
\end{itemize}
How many total triangulations did you draw?
\item[3.2] Repeat the same with vertex $B$ as the ``special'' vertex, i.e., draw all triangulations
where:
\begin{itemize}
\item $BD$ is one of the diagonals in the triangulation.
\item $BE$ is one of the diagonals in the triangulation.
\item $BF$ is one of the diagonals in the triangulation.
\end{itemize}
How many total triangulations did you draw?
\item[3.3] Do the same with vertices $C$, $D$, $E$, $F$ being ``special''.
\item[3.4] Consider the triangulation of $ABCDEF$ in figure 1 (of section 1). How many times is that
triangulation repeated in all the triangulations that you drew for $ABCDEF$ in this section?
Identify the diagonals in whose group it was drawn.
\item[3.5] Do the same for the different triangulations of $ABCDEF$ that you drew in section 1.
\item[3.6] What would you guess about the number of times any triangulation of $ABCDEF$ is repeated?
Argue why your guess is correct.
\item[3.7] Consider the $n$-sided polygon $A_1A_2\ldots A_n$. Let $P_i$ denote the number of different
triangulations of a polygon with $i$ sides.
\begin{itemize}
\item[($a$)] Calculate, in terms of $P_i$'s, the number of triangulations of this polygon
that have $A_1A_3$ as a diagonal,
that have $A_1A_4$ as a diagonal, that have $A_1A_j$ as a diagonal.
\item[($b$)] Consider drawing triangulations treating $A_1$ as the ``special'' vertex. That is, draw all triangulations
where $A_1A_3$ is a diagonal, then draw all triangulations where $A_1A_4$ is a diagonal, etc. all the way up to
where $A_1A_{n-1}$ is a diagonal. What is the number of triangulations you draw (in terms of $P_i$'s)
when $A_1$ is treated as a special vertex?
\item[($c$)] Suppose we repeat the above process with with another vertex (say $A_2$) being the special vertex instead
of $A_1$. What can you say about the number of triangulations drawn as compared to the number
of triangulations drawn when $A_1$ was chosen as the special vertex? Explain in your own words why this
is true.
\item[($d$)] Consider doing what you did for $A_1 $ in ($b$) successively for each vertex. That is,
enumerate all triangulations treating $A_1$ as a special vertex, treating $A_2$ as
a special vertex, \ldots treating $A_n$ as a special vertex.
Now consider the specific triangulation of $A_1,A_2\ldots A_n$ obtained by drawing the diagonals
$A_1A_3, A_1A_4,\ldots A_1A_{n-1}$. How many times is this triangulation enumerated? What about the
triangulation obtained by drawing the diagonals $A_1A_4,A_1A_5\ldots A_1A_{n-2}$
and the two diagonals $A_2A_4,A_{n-2}A_{n}$? Justify your answer.
\item[($e$)] What is your guess as to how many times any specific triangulation is enumerated? Explain in your
own words why this is the case.
\end{itemize}
\item[3.8] Combine ($b$) and ($e$) to derive the formula (2) in Lam\'{e}'s paper. Explain in your own
words how this formula is obtained.
\item[3.9] Combine formulas (1) and (2) in Lam\'{e}'s paper to obtain the formula (3) in Lam\'{e}'s paper.
Show all the steps in your calculation.
Explain why this formula is better for calculating $P_n$.
\item[3.10] Using formula (3) in Lam\'{e}'s paper, show that $P_{n+2} = \frac{1}{n+1}{{2n}\choose{n}}$
where ${{2n}\choose{n}} = \frac{(2n)!}{n!n!}$.
\item[3.11] Write a simple recursive function $ASRCAT(n)$ (for ''Another Simple Recurvise CATalan") in Java that given an input $n$ calculates $P_n$ using
the recurrence relation (3) in Lam\'{e}'s paper directly.
\item[3.12] Write another Java program that repeatedly uses $ASRCAT$ to calculate $P_i$ for $i=3,4,5\ldots$ Restrict
the total time your program uses to 10 minutes. What is the largest value $L_0$ of $i$ for which your program
calculates $P_i$?
\item[3.13] Extend your program to print out a table of values of $i$ and time required in seconds
by $ASRCAT(n)$ to compute each of the $P_i$ values for $i=3,4,\ldots, L_0$.
Your table should have a row for each $i=3,4,\ldots, L_0$.
\item[3.14] Write a better Java program using the ideas from dynamic programming (``store and re-use")
that repeatedly calculates $P_i$ for $i=3,4,\ldots$ Restrict
the total time your program uses to 10 minutes. What is the largest value $L_1$ of $i$ for which your program
calculates $P_i$.
\item[3.15] Extend your program to print out a table of values of $i$ and the time required in seconds
to calculate each of the $P_i$ values. Your table should have a row for each $i=3,4,\ldots, L_1$.
\item[3.16] Graph the tables obtained in 3.13 and 3.15. Analyse all four graphs obtained and write down your observations.
How do the results for the second two programs compare with your first two programs? How fast does the running time of the last two programs grow?
\item[3.17] Discuss how the choice of Lam\'{e}'s formulas (1) or (3), or using dynamic versus na\"{i}ve recursive programming influences the
effectiveness of computation.
\end{itemize}
\section*{Notes to the Instructor}
This project is most suitable for use in an upper-division undergraduate algorithm
design and analysis course. In particular, it is best used at the time when the students are
learning the {\em dynamic programming} paradigm for algorithm design. It allows them
to see why a na\"{i}ve solution is infeasible for solving the Optimal Polygon Triangulation
Problem for polygons with large number of sides and how the dynamic programming technique
allows one to do the same calculation much more efficiently.
Some of thet tasks, as stated in the project, ask the students to write JAVA programs.
Use of JAVA is not critical. Any programming language that allows for recursion and use
of arrays (e.g. C, C++) can be substituted for JAVA without affecting the project.
\begin{thebibliography}{99}
\bibitem{DREuler1751} Euler, L., {\em Leonhard Euler und Christian
Goldbach, Briefwechsel 1729--1764}, Juskevic, A. P., Winter,
E. (editors), Akademie Verlag, Berlin, 1965.
\bibitem{DREuler1758} Euler, L., {\em Novi Commentarii Academiae
Scientarium Imperialis Petropolitanque} {\bf{7}} (1758--59),
p. 9--28.
\bibitem{DRGillispie} Gillispie, C. C., Holmes, F. L., (editors)
\emph{Dictionary of Scientific Biography}, Scribner, New York, 1970.
\bibitem{DRLame} Lam\'e, G., ``Un polygone convexe \'etant donn\'e, de
combien de mani\`eres peut-on le partager en triangles au moyen de
diagonales?,'' {\em Journal de Math\'ematiques Pures et Appliqu\'ees},
{\bf{3}} (1838), 505--507.
\bibitem{DRSegner1756} Segner, A., ``Enumeratio Modorum Quibus Figurae
Planae Rectilinae per Diagonales Dividuntur in Triangula'',
{\em Novi Commentarii Academiae Scientarium Imperialis
Petropolitanque} {\bf{7}} (1758-59), 203--209.
%\bibitem{Luo} Luo, Jian-Jin, ``Catalan Numbers in the History of
%Mathematics in China,'' in {\em Combinatorics and Graph Theory},
%Proceedings of the Spring School and International Conference on
%Combinatorics, Yap, H. P., et. al. (eds.), World Scientific,
%Singapore, 1992.
\end{thebibliography}
\end{document}