Segner’s Recurrence Relation, Euler’s Polygon Triangulation and Catalan Numbers
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. Near the end of the letter, Euler writes matter of factly, that he figured out the number of triangulations of the polygons with at most 10 sides. Evidently, he does this by hand and then takes ratios of the successive number to guess the general product formula.
At the end of the letter, Euler even guessed(correctly) the generating function for this sequence of numbers. He writes:
Die Induction aber, so ich gebraucht, war ziemlich mühsam, doch zweifle ich nicht, dass diese Sach, nicht sollte weit leichter entwickelt werden können.
Translation: The induction, however, when I used it, was rather difficult, but I do not doubt that the matter could not be developed much more easily
After that Goldbach replied with some of his observations and then Euler replied with more details on derivations of the generating function, but they could not finish the proof . Okay! Lets not dive much into the stories of Catalan Number and its related controversies. But if you are still interested you can follow this link : 🔗
Recurrence Relation
In 1758, Johann Andreas Segner published a paper with a proof of the following recurrence:
This recurrence relation is what we are going to visualize below for Euler’s Triangulation for n+2 sided polygon that means Cn is the number of triangulation possible for n+2 polygon.
Consider an octagon (6+2) sided , number of triangulation possible will be :
We will take a base side say AB and will split this polygon into two polygons with the help of a triangle whose base will be AB and vertex will be all other remaining vertex of the polygon one by one
That’s it!!
Python Implementation
Now we can also easily create a simple recursive function in python to calculate Cn
This can be further optimized using Dynamic Programming
Applications
Catalan numbers are the solution of so many other interesting combinatorial problems such as:
- number of different ways n + 1 factors can be completely parenthesized. For n = 3, for example, we have the following five different parenthesizations of four factors :
- number of Dyck Words and Dyck Paths of length 2n
- number of expressions containing n pairs of parentheses which are correctly matched, This can also be analyzed using Dyck word. For n=3 :
- number of full binary trees with n + 1 leaves, or, equivalently, with a total of n internal nodes
- number of ways to tile a stair-step shape of height n with n rectangles. Cutting across the anti-diagonal and looking at only the edges gives full binary trees. For n=4 :
- number of ways to form a “mountain range” with n upstrokes and n down-strokes that all stay above a horizontal line. The mountain range interpretation is that the mountains will never go below the horizon.
