Please use this identifier to cite or link to this item:
A Bijective Proof from Triangulated Convex Polygons to Binary Trees
|Issue Date:||2016-04-28 13:29:59 (UTC+8)|
|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)).|
|Reference:|| Ralph P. Grimaldi. Discrete and Combinatorial Mathematics: A n Applied Introduction.3rd ed .Addison- Wesley, 1994.
 Ellis Horowit.z and Sartaj Sahni . Fundamentals of Data Struchlres. Computer Science Press,Inc., 1982.
 Richard A. Brualdi. Introductory Combinatorics. Elsevier North-Holland; Inc., 1977.
 Jean-Paul Tremblay and Richard B. Bunt. An Introduction to Computer Science: An Algorithmic Approach.McGraw-Hill: Inc. , 1979.
 C. L. Liu . Introduction to Combinatorial 111athcmatics. McGraw-Hill; Inc., 1968.
|Appears in Collections:||[應用數學系] 學位論文|
Files in This Item:
All items in 學術集成 are protected by copyright, with all rights reserved.