Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Noncrossing Trees and Noncrossing Graphs. | Noncrossing Trees and Noncrossing Graphs William Y. C. Chen and Sherry H. F. Yan Center for Combinatorics LPMC Nankai University 300071 Tianjin P.R. China chen@nankai.edu.cn huifangyan@eyou.com Submitted Sep 18 2005 Accepted Nov 30 2005 Published Aug 14 2006 Mathematics Subject Classifications 05A05 05C30 Abstract We give a parity reversing involution on noncrossing trees that leads to a combinatorial interpretation of a formula on noncrossing trees and symmetric ternary trees in answer to a problem proposed by Hough. We use the representation of Panholzer and Prodinger for noncrossing trees and find a correspondence between a class of noncrossing trees called proper noncrossing trees and the set of symmetric ternary trees. The second result of this paper is a parity reversing involution on connected noncrossing graphs which leads to a relation between the number of noncrossing trees with n edges and k descents and the number of connected noncrossing graphs with n 1 vertices and m edges. 1 Introduction A noncrossing graph with n vertices is a graph drawn on n points numbered in counterclockwise order on a circle such that the edges lie entirely within the circle and do not cross each other. Noncrossing trees have been studied by Deutsch Feretic and Noy 2 Deutsch and Noy 3 Flajolet and Noy 4 Noy 6 Panholzer and Prodinger 7 . It is well known that the number of noncrossing trees with n edges equals the generalized Catalan number c ãn ĩCn . In this paper we are concerned with rooted noncrossing trees. We assume that 1 is always the root. A descent is an edge i j such that i j and i is on the path from the root 1 to the vertex j. A ternary tree is either a single node called the root or it is a root associated with three ternary trees. A symmetric ternary tree is a ternary tree which can be decomposed into a ternary left subtree a central symmetric ternary tree and a ternary right subtree that is a reflection of the left subtree as shown in Figure 1. Let Sn be the set
