\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amsthm} %\usepackage{thmdefs}
\theoremstyle{plain} %% This is the default
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{axiom}{Axiom}[section]
%\newtheorem{remark}{Remark}[section]
%\newtheorem{example}{Example}[section]
%\theoremstyle{definition}
%\newtheorem{exercise}{Exercise}[chapter]
\numberwithin{equation}{section}
\newcommand{\br}{\mathbf {R}}
\newcommand{\bn}{\mathbf {N}}
\newcommand{\ot}{\otimes}
\newcommand{\ld}{\ldots}
\begin{document}
\title{Gabriel Lam\'e's Counting of Triangulations}
\author{An Historical Project}
\date{ }
\maketitle
\section{Introduction}
In a letter to Joseph Liouville (1809--1882) in 1838, Gabriel Lam\'e
(1795--1870) offered an elegant and efficient counting argument for
the number of triangulations of a convex $n$-sided polygon
\cite{Lame}. The
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]{Gillispie}. 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]{Gillispie}.
The triangulation problem, studied earlier by the prolific
Leonhard Euler (1707--1783),
can be stated as follows. Given a convex $n$-sided polygon, divide it
into triangles by drawing {\em non-intersecting} diagonals connecting
some of the vertices of the polygon.
Euler calculated the number, $P_n$, of distinct triangulations of a
convex $n$-gon for the first few values of $n$, and conjectured a
formula for $P_n$ based on an empirical study of the ratios $P_{n+1}/P_n$
\cite[p.\ 339-350]{Euler1751} \cite{Euler1758}.
Lam\'e was one of the first to provide
the details for a combinatorial proof of Euler's conjectured result
for $P_{n+1}/P_n$, a proof which the reader will study in its original
(translated) version in this project.
Although Euler does not state his motivation for studying the
triangulation problem, it may have roots in surveying,
where a given region to be surveyed is divided into triangles, with
the three vertices of the triangle serving as reference points.
A modern use of
triangulation is the Global Positioning System, where readings
from three satellites are used to determine the position of a point on
earth. For this project, however, we will consider polygons $\cal P$
in the plane with the property that if $A$ and $B$ are points in $\cal
P$, then the line segment connecting $A$ and $B$ is also contained in
$\cal P$. This latter property is expressed by stating that $\cal P$
is convex. As a further simplification, we will often use regular
polygons, which have all sides congruent and all angles congruent.
Lam\'e, and not Euler, uses the subscripted notation $P_n$ to denote the number of
triangulations of a convex polygon with $n$ sides.
\smallskip
\noindent
1.1. Explain why $P_3 = 1$.
\smallskip
\noindent
To determine $P_4$, consider the following triangulations of square
$A_1 A_2 A_3 A_4$.
\begin{picture}(500,95)
\thicklines
\put(100,25){\line(1,1){40}}
\put(100,65){\line(1,0){40}}
\put(100,25){\line(0,1){40}}
\put(100,25){\line(1,0){40}}
\put(140,25){\line(0,1){40}}
\put(88,70){$A_1$}
\put(141,70){$A_2$}
\put(141,15){$A_3$}
\put(88,15){$A_4$}
\put(230,65){\line(1,-1){40}}
\put(230,65){\line(1,0){40}}
\put(230,25){\line(0,1){40}}
\put(230,25){\line(1,0){40}}
\put(270,25){\line(0,1){40}}
\put(218,70){$A_1$}
\put(271,70){$A_2$}
\put(271,15){$A_3$}
\put(218,15){$A_4$}
\end{picture}
\noindent
1.2. Can you find any other ways to triangulate square $A_1 A_2 A_3
A_4$ with non-intersecting diagonals? What is the value of $P_4$?
\smallskip
\noindent
1.3. Let $A_1 A_2 A_3 A_4 A_5$ be a regular pentagon and compute
$P_5$, the number of distinct triangulations of the pentagon. Can you
identify how the number of triangulations of a convex quadrilateral
(or square) enters into the
calculation of the triangulations of the pentagon? Consider
triangulations of the pentagon which contain the triangle $A_1 A_2
A_3$ first, then triangle $A_1 A_2 A_4$, then triangle $A_1 A_2 A_5$.
Write an equation for $P_5$ in terms of $P_4$ and $P_3$.
\smallskip
\noindent
1.4. Let $A_1 A_2 \, \ldots \, A_6$ be a regular hexagon and devise a
strategy for computing $P_6$ by using the previous results for a
pentagon, quadrilateral, and a triangle. Be sure to explain your approach.
What is the value of $P_6$?
\smallskip
\noindent
1.5. Find a recursion relation for $P_{n+1}$ in terms of the previous
$P_k$'s. Be sure to justify your answer. For what values of $k$ must
$P_k$ be known in order to compute $P_{n+1}$? Compare your result with
\S I from Lam\'e's letter \cite{Lame} in the next part.
\section{Lam\'e's Letter to Liouville}
\begin{center}
{\sf
{\bf{Extrait d'une lettre de M. Lam\'{e} \`{a} M. Liouville sur cette question:}}
{\em Un polygone convexe \'{e}tant donn\'{e}, de combien de mani\`{e}res peut-on le
partager en triangles au moyen de diagonales?}\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}}}
\bigskip
\centerline{Translation copyright \copyright $\ $ 2004 by David Pengelley}
\bigskip
{\sf
{\bf{Excerpt from a letter of Monsieur Lam\'{e} to Monsieur Liouville on the
question: }}{\em Given a convex polygon, in how many ways can one partition it into
triangles by means of diagonals?}}
\bigskip
\end{center}
{\sf
\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{align*}
& (1) \ \ \ \ \ P_{n+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{align*}}
\bigskip
\noindent
2.1. Explain why the triangulations belonging to the groups
$$ P_n, \ P_3 P_{n-1}, \ P_4 P_{n-2},
\ \ldots \, , \ P_{n-1} P_3, \ P_n $$
are distinct.
\smallskip
\noindent
2.2. Does every triangulation of a convex polygon with $n+1$ sides
occur in one of the groups represented by
$$ P_n, \ P_3 P_{n-1}, \ P_4 P_{n-2},
\ \ldots \, , \ P_{n-1} P_3, \ P_n \ {\rm?} $$
Why or why not?
\smallskip
\noindent
2.3. Use Lam\'e's recursion relation of \S I to compute $P_{10}$.
What difficulties do you encounter in this computation?
In \S I of his letter, Lam\'e uses triangle $A_1 A_2 A_k$ to divide
the $(n+1)$-sided polygon $A_1 A_2 A_3 \, \ldots \, A_{n+1}$ into two
subpolygons. The triangulations for the subpolygons then figure into
the recursion relation for $P_{n+1}$. In \S II Lam\'e changes his
point of view, and uses instead the diagonal $A_1 A_k$ to divide the
$n$-gon $A_1 A_2 A_3 \, \ldots \, A_n$ into two subpolygons. Let's
examine the consequences of using a diagonal instead of a triangle to
divide the polygon.
\smallskip
\noindent
2.4. Consider a regular pentagon $A_1 A_2 A_3 A_4 A_5$. Using
diagonal $A_1 A_3$ to split the pentagon into two figures, how many
resulting triangulations of the original pentagon are there? Let
$T_1$ denote the set of these triangulations. Using diagonal $A_1
A_4$, how many triangulations of the pentagon are there? Let $T_2$
denote the set of these triangulations. Compute the sum of the
cardinality (the number of elements) of $T_1$ and $T_2$, and let $S_5$
denote this value. How does $S_5$ compare to $P_5$?
Are all elements of $T_1$ and $T_2$ distinct? Is
every possible triangulation of the original pentagon an element of
$T_1 \cup T_2$? Justify your answers.
\smallskip
\noindent
2.5. Consider a regular hexagon $A_1 A_2 A_3 \, \ldots \, A_6$. Let
$T_1$ be the set of all triangulations of the hexagon that are formed
using the diagonal $A_1 A_3$. Let $T_2$ be the set of triangulations
of the hexagon using $A_1 A_4$, and $T_3$ the set of triangulations
using $A_1 A_5$. Compute
$$ S_6 = |T_1| + |T_2| + |T_3| \, , $$
where $|T_i|$ denotes the cardinality of $T_i$. Do you recognize this
sum? How does $S_6$ compare to $P_6$? Are all elements of $T_1$ and
$T_2$ distinct? Is every triangulation of the original hexagon an
element of $T_1 \cup T_2 \cup T_3$? Justify your answers.
\smallskip
\noindent
2.6. Consider now a regular $n$-gon $A_1 A_2 A_3 \, \ldots \,
A_{n-1} A_n$. Let $T_i$ be the set of all triangulations of the
$n$-gon which are formed using the diagonal $A_1 A_{i+2}$ for $i = 1$,
2, 3, $\ldots$, $n-3$. Write an algebraic expression for
$$ S_n = |T_1| + |T_2| + |T_3| + \cdots + |T_{n-3}| $$
in terms of the $P_k$'s. How does $S_n$ compare to $P_n$? Are the
sets $T_1$ and $T_2$ disjoint? Is every triangulation of the original
$n$-gon an element of
$$ T_1 \cup T_2 \cup T_3 \cup \, \cdots \, \cup T_{n-3}\, {\text{?}} $$
Justify your answer.
Let's now read from \S II of Lam\'e's letter.
\bigskip
{\sf
\begin{center}
\medskip
II.
\medskip
\end{center}
\textquotedblleft 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.}
\bigskip
\noindent
2.7. In the above statement, what groups is Lam\'e referring to by
``[T]hese groups are not totally different''? What notation have we
used for ``diagonals ending in $a$''?
Lam\'e's use of diagonals leads to an enumeration of triangulations
which is neither one-to-one nor inclusive of all triangulations. His
genius, however, was to slightly alter this strategy to first include
all triangulations, and then to count how many times a generic
triangulation occurs. Combined with the results of \S I, this results
in a streamlined computation for $P_n$.
\smallskip
\noindent
2.8. Returning to pentagon $A_1 A_2 A_3 A_4 A_5$, recall that $S_5$
counts with certain repetitions the number of triangulations arising
from diagonals $A_1A_3$ and $A_1 A_4$. How many triangulations,
counting possible repetitions, would occur if diagonals $A_2 A_4$ and
$A_2 A_5$ are used? Denote this number by $S^{(2)}_5$. How many
triangulations, counting possible repetitions, would occur if
diagonals $A_3 A_5$ and $A_3 A_1$ are used? Denote this number by
$S^{(3)}_5$. Similarly, let $S^{(4)}_5$ denote the number of
triangulations with repetition formed by diagonals $A_4 A_1$ and $A_4
A_2$. Compute $S^{(4)}_5$. What diagonals would be used to define
$S^{(5)}_5$? Compute $S^{(5)}_5$ and $\sum_{i=1}^5 S^{(i)}_5$, where
$S^{(1)}_5 = S_5$.
\smallskip
\noindent
2.9. Let $\cal T$ be an arbitrary triangulation of the pentagon.
Must $\cal T$ be included in the count
$$ S^{(1)}_5 + S^{(2)}_5 + S^{(3)}_5 + S^{(4)}_5 + S^{(5)}_5 \,
{\text{?}} $$
Justify your answer. How many times does $\cal T$ occur in the sum
$\sum_{i=1}^5 S^{(i)}_5$? Why? Use this number of duplications to
find integers $K$ and $L$ with
$$ K \cdot S_5 = L \cdot P_5 $$
and justify your answer.
\smallskip
\noindent
2.10. For the hexagon, consider numbers $S^{(1)}_6$, $S^{(2)}_6$,
$\ldots$, $S^{(6)}_6$ defined similarly. Based on the number of times
a generic triangulation is counted in $\sum_{i=1}^6
S^{(i)}_6$, find integers $K$ and $L$
with
$$ K \cdot S_6 = L \cdot P_6 \, , $$
and justify your answer.
\smallskip
\noindent
2.11. For a regular $n$-gon, find integers $K$ and $L$ with
$$ K \cdot S_n = L \cdot P_n \, , $$
where $L$ indicates the number of times a fixed triangulation occurs in
the count $\sum_{i=1}^n S^{(i)}_n$.
\smallskip
Lam\'e continues:
\bigskip
{\sf
\textquotedblleft 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.
\textquotedblleft 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.
\textquotedblleft 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
$$
(2) \hskip.5in
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{.}\hskip.5in $$ }
\bigskip
\noindent
2.12. In equation (2) identify terms which play the role of $S_n$,
$K$ and $L$.
Lam\'e's equations (1) and (2) thus represent two strategies for
computing $P_n$, although each equation is itself a recursion relation
requiring the value of $P_3$, $P_4$, $\ldots$, $P_{n-1}$ to compute
$P_n$. Can these two equations be combined to solve for $P_n$
directly?
\smallskip
\noindent
2.13. Find a fraction $N$ with $P_{n+1} = N P_n$. Be sure to
carefully justify your work. Use this equation to find a fraction
$N'$ with $P_{n+1} = N'P_{n-1}$.
Lam\'e concludes:
\bigskip
\begin{center}
\medskip
{\sf III.}
\medskip
\end{center}
{\sf
\textquotedblleft 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
$$ (3) \hskip2in
P_{n+1}=\frac{4n-6}{n}P_{n}\text{.}\hskip2in $$
This is what was to be proven.\textquotedblright\
\medskip
\hfill{\small Paris, 25 August, 1838.}}
\section{A Modern Formula}
3.1. Let $P_2 = 1$. Using the simple recursion relation $P_{n+1} = NP_n$,
explain why
\begin{align*}
& P_3 = \frac{2}{2} \, P_2 \\
& P_4 = \frac{2}{2} \cdot \frac{6}{3} \, P_2
\end{align*}
Find an integer $M$ with
$$ P_5 = \frac{2 \cdot 6 \cdot M}{2 \cdot 3 \cdot 4} \, P_2 . $$
Letting $M_1 =2$ and $M_2 = 6$, find integers $M_3$, $M_4$, $M_5$,
$\ldots$, $M_{n-1}$ with
$$ P_{n+1} = \frac{M_1 \cdot M_2 \cdot M_3 \cdot M_4 \, \cdots
\, M_{n-1}}{2 \cdot 3 \cdot 4 \cdot 5 \, \cdots \, n} \,
P_2 . $$
We have $n! = 2 \cdot 3 \cdot 4 \cdot 5 \, \cdots \, n$. Factor
a 2 from each $M_i$ to write
$$ P_{n+1} = 2^x \, \frac{(M_1/2)(M_2/2) \, \cdots \,
(M_{n-1}/2)}{n!} \, P_2 . $$
What is the value of $x$? Do you recognize the product
$$ \prod_{i=1}^{n-1}(M_i/2) = (M_1/2)(M_2/2)(M_3/2) \, \cdots \, (M_{n-1}/2)
\, {\text{?}} $$
What is missing from $\prod_{i=1}^{n-1}(M_i/2)$ to form a factorial?
Include the missing terms in both the numerator and denominator to
write
$$ P_{n+1} = \frac{(2n-2)!}{D_1\, n!} \, P_2 \, , $$
for some integer $D_1$.
Find an integer $D_2$ with
$$ P_{n+1} = \frac{1}{D_2}\binom{2n-2}{n-1} \, P_2 . $$
Justify your answer via a direct argument.
\smallskip
\noindent
3.2. Use the above equation for $P_{n+1}$ to compute $P_{10}$ and
compare this to exercise (2.3).
\begin{thebibliography}{99}
\bibitem{Euler1751} Euler, L., {\em Leonhard Euler und Christian
Goldbach, Briefwechsel 1729--1764}, Juskevic, A. P., Winter,
E. (eds.), Akademie Verlag, Berlin, 1965.
\bibitem{Euler1758} Euler, L., {\em Novi Commentarii Academiae
Scientarium Imperialis Petropolitanque} {\bf{7}} (1758--59),
p. 9--28.
\bibitem{Gillispie} Gillispie, C. C., Holmes, F. L. (eds.)
{\em Dictionary of Scientific Biography}, Vol. VII, Scribner, New
York, 1970.
\bibitem{Lame} 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), p. 505--507.
%\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}