凸多邊形的三角化與二元樹的一對一證明

Abstract

How many ways can a convex polygon of n（≥3） sides be triangulated by diagonals that do not intersect？ The problem was first proposed by Leonard Euler. Instead of setting up a recurrence relation and using the method of generating function to solve it, we shall set up a one-to-one correspondence between the convex-polygon triangulations we are trying to count the rooted binary trees that have already been counted. Let bn denote the number of rooted ordered binary trees with n vertices and let tn denote the number of triangulations of convex polygon with n sides. We conclude that tn＝bn＝1/(n-1) ((2n-4)¦(n-2)).