Đ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 ngành toán học tạp chí toán học quốc tế đề tài: Descents in Noncrossing Trees. | Descents in Noncrossing Trees. David S. Hough Department of Mathematics Howard University Washington DC USA david.hough@verizon.net Submitted Jun 18 2002 Accepted Oct 6 2003 Published Oct 13 2003 MR Subject Classifications 05C30 05A15 Abstract The generating function for descents in noncrossing trees is found. A bijection shows combinatorially why the descent generating function with descents set equal to 2 is the generating function for connected noncrossing graphs. 1 Introduction A noncrossing tree is a tree drawn on n points numbered in counterclockwise order on a circle such that the edges lie entirely within the circle and do not cross. A descent is an edge from a higher to a lower label along a path from the root 1. We frequently use g.f. to stand for generating function . In Section 2 we find the descent g.f. for noncrossing trees. In Section 3 we show a bijection between noncrossing trees and connected noncrossing graphs that explains combinatorially why the g.f. for connected noncrossing graphs equals the descent g.f. evaluated at 2. 2 Descents in Noncrossing Trees Consider as in 2 a noncrossing tree as a sequence of butterflies. Let T z u v X z ud T 1 T where the sum is over all trees T the size tI is the number of edges d r is the number of descents and a T is the number of ascents. A butterfly is an ordered pair of subtrees T and T that lie on either side of an edge 1 i from the root to point i T on points Thanks to Louis W. Shapiro and Frank W. Schmidt for useful discussions and to the anonymous referee for an alternative proof that also proved a conjecture in the original paper. THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 N13 1 greater than or equal to i and T on points less than or equal to i not including 1. Then we have T z u v 1 - vzT z u v T z v u 2 Figure 1 A butterfly diagram of noncrossing trees where T stands for T z u v and T for T z v u . This is because when the tree is rooted at 1 every edge from 1 contributes one to the size and one
