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 . China chen@ huifangyan@ 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
