You are here

Gabriel Lamé’s Counting of Triangulations

Author(s): 
Jerry Lodder (New Mexico State University)
French mathematician Gabriel Lamé (Source: Wikimedia Commons)

Introduction

This project offers Gabriel Lamé’s (1795–1870) clever and highly original method for counting the number of triangulations of a convex polygon with n sides, forming a sequence today known as the Catalan numbers. Lamé’s solution [4] was written as a letter to Joseph Liouville (1809–1882) in response to Liouville’s challenge to solve the problem of counting such triangulations, for which Leonhard Euler (1707–1783) had earlier guessed a result. Euler, however, was unable to provide a proof of his conjectured formula. Liouville received many proofs in response to his query and published several of them in Journal de Mathématiques Pures et Appliquées (also known as “Liouville’s Journal”), including those of Lamé and the Belgian mathematician Eugène Charles Catalan (1814–1894). Catalan’s solution is difficult to follow, while Lamé’s method offers a clever geometric argument involving two recursion formulas for Pn, the number of triangulations of a convex n-gon. When algebraically combined, these two recursion formulas yield a result for Pn in terms of certain binomial coefficients equivalent to the modern formula for the so-called Catalan numbers.

The project Gabriel Lamé’s Counting of Triangulations is ready for students, and the Latex source is also available for instructors who may wish to modify the project for students. The comprehensive “Notes to the Instructor” presented next are also appended to the project itself.

This primary source project module for students is part of a larger collection published in Convergence, and an entire introductory discrete mathematics course or combinatorics course can be taught from various combinations selected from these projects. For more projects, see Primary Historical Sources in the Classroom: Discrete Mathematics and Computer Science.

Belgian mathematican Eugène Catalan (Source: Wikimedia Commons)

Notes to the Instructor

This project contains original source material from Gabriel Lamé’s 1838 publication “Given a convex polygon, in how many ways can one partition it into triangles by means of diagonals?” [4]. The paper, written as a letter to Joseph Liouville, develops a clever and highly original method for counting the number of triangulations of a convex polygon, yielding what today is called the sequence of Catalan numbers. Catalan’s own derivation of these numbers, however, is somewhat difficult to follow. Lamé’s method relies on an averaging argument over certain symmetries of a (regular) polygon. The project offers engaging material for an upper-divisional course in combinatorics or discrete mathematics. Section two of the project carefully leads the reader through Lamé’s argument with several student exercises. This section closes with Lamé’s simple recursion relation for the number of triangulations of a convex polygon. The third section offers a formulation of these numbers in terms of binomial coefficients. A prerequisite for the project is an introductory course in discrete mathematics covering binomial coefficients and the concept of a one-to-one correspondence. If the project is covered in its entirety, allow about three weeks.

A version of this curricular module for a computer science course has been written by Desh Ranjan [1, 2] in which the running times for Lamé’s equations (1) and (3) are compared. Both the programming version and this mathematical version share the same introduction, co-authored by Desh Ranjan and Jerry Lodder. The Catalan numbers occur quite naturally in other enumeration problems, such as counting the number of rooted, binary planar trees. Every triangulation of a convex polygon corresponds to such a binary tree and vice versa. Although this correspondence is not developed in the project, it could be discussed in class. For a study of other applications of these numbers, see the text by Koshy [3].

Download the project Gabriel Lamé’s Counting of Triangulations as a pdf file ready for classroom use.

Download the modifiable Latex source file for this project.

For more projects, see Primary Historical Sources in the Classroom: Discrete Mathematics and Computer Science.

Bibliography

[1]  Barnett, J., Bezhanishvili, G., Leung, H., Lodder, J., Pengelley, D., Ranjan, D.,  Teaching Discrete Mathematics via Primary Historical Sources, http://www.math.nmsu.edu/hist_projects/.

[2]  Barnett, J., Bezhanishvili, G., Leung, H., Lodder, J., Pengelley, D., Ranjan, D., “Historical Projects in Discrete Mathematics and Computer Science” in Resources for Teaching Discrete Mathematics, Hopkins, B. (editor), Mathematical Association of America, Washington, D.C., 2009.

[3]  Koshy, T., Catalan Numbers with Applications, Oxford University Press, New York, 2009.

[4]  Lamé, G., “Un polygone convexe étant donné, de combien de manières peut-on le partager en triangles au moyen de diagonales?,” Journal de Mathématiques Pures et Appliquées, 3 (1838), pp. 505–507.

Acknowledgment



The development of curricular materials for discrete mathematics has been partially supported by the National Science Foundation's Course, Curriculum and Laboratory Improvement Program under grants DUE-0717752 and DUE-0715392 for which the authors are most appreciative. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

Jerry Lodder (New Mexico State University), "Gabriel Lamé’s Counting of Triangulations," Loci (July 2013), DOI:10.4169/loci003996

Dummy View - NOT TO BE DELETED