Please use this identifier to cite or link to this item:
https://ah.lib.nccu.edu.tw/handle/140.119/87367
題名: | 凸多邊形的三角化與二元樹的一對一證明 A Bijective Proof from Triangulated Convex Polygons to Binary Trees |
作者: | 李世仁 Lee, Shih-Jen |
貢獻者: | 李陽明 Li, Young-Ming 李世仁 Lee, Shih-Jen |
關鍵詞: | 凸多邊的三角形化 | 日期: | 1996 | 上傳時間: | 28-Apr-2016 | 摘要: | 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)). | 參考文獻: | [1] Ralph P. Grimaldi. Discrete and Combinatorial Mathematics: A n Applied Introduction.3rd ed .Addison- Wesley, 1994.\r\n[2] Ellis Horowit.z and Sartaj Sahni . Fundamentals of Data Struchlres. Computer Science Press,Inc., 1982.\r\n[3] Richard A. Brualdi. Introductory Combinatorics. Elsevier North-Holland; Inc., 1977.\r\n[4] Jean-Paul Tremblay and Richard B. Bunt. An Introduction to Computer Science: An Algorithmic Approach.McGraw-Hill: Inc. , 1979.\r\n[5] C. L. Liu . Introduction to Combinatorial 111athcmatics. McGraw-Hill; Inc., 1968. | 描述: | 碩士 國立政治大學 應用數學系 82155003 |
資料來源: | http://thesis.lib.nccu.edu.tw/record/#B2002002892 | 資料類型: | thesis |
Appears in Collections: | 學位論文 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
index.html | 115 B | HTML2 | View/Open |
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.