Please use this identifier to cite or link to this item: `https://ah.nccu.edu.tw/handle/140.119/87367`

 Title: 凸多邊形的三角化與二元樹的一對一證明A Bijective Proof from Triangulated Convex Polygons to Binary Trees Authors: 李世仁Lee, Shih-Jen Contributors: 李陽明Li, Young-Ming李世仁Lee, Shih-Jen Keywords: 凸多邊的三角形化 Date: 1996 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: [1] Ralph P. Grimaldi. Discrete and Combinatorial Mathematics: A n Applied Introduction.3rd ed .Addison- Wesley, 1994. [2] Ellis Horowit.z and Sartaj Sahni . Fundamentals of Data Struchlres. Computer Science Press,Inc., 1982. [3] Richard A. Brualdi. Introductory Combinatorics. Elsevier North-Holland; Inc., 1977. [4] Jean-Paul Tremblay and Richard B. Bunt. An Introduction to Computer Science: An Algorithmic Approach.McGraw-Hill: Inc. , 1979. [5] C. L. Liu . Introduction to Combinatorial 111athcmatics. McGraw-Hill; Inc., 1968. Description: 碩士國立政治大學應用數學系82155003 Source URI: http://thesis.lib.nccu.edu.tw/record/#B2002002892 Data Type: thesis Appears in Collections: [應用數學系] 學位論文

Files in This Item:

File SizeFormat
index.html0KbHTML177View/Open