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.html0KbHTML142View/Open


All items in 學術集成 are protected by copyright, with all rights reserved.


社群 sharing