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:
|
All items in 學術集成 are protected by copyright, with all rights reserved.
| 社群 sharing |