Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "A combinatorial proof of Postnikov’s identity and a generalized enumeration of labeled trees"
Đ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 trên tạp chí toán học quốc tế đề tài: A combinatorial proof of Postnikov’s identity and a generalized enumeration of labeled trees. | A combinatorial proof of Postnikov s identity and a generalized enumeration of labeled trees Seunghyun Seo Department of Mathematics Brandeis University Waltham MA 02454 USA shseo@brandeis.edu Submitted Sep 16 2004 Accepted Dec 16 2004 Published Jan 24 2005 Mathematics Subject Classifications 05A15 05C05 05C30 Abstract In this paper we give a simple combinatorial explanation of a formula of A. Postnikov relating bicolored rooted trees to bicolored binary trees. We also present generalized formulas for the number of labeled k-ary trees rooted labeled trees and labeled plane trees. 1 Introduction In Stanley s 60th Birthday Conference Postnikov 3 p. 21 showed the following identity n 1 -1 X n n 1 v V b h v J 1 where the sum is over unlabeled binary trees b on n vertices and h v denotes the number of descendants of v including v . The figure below illustrates all five unlabeled binary trees on 3 vertices with the value of h v assigned to each vertex v. In this case identity 1 says that 3 1 2 3 3 4 3 3. 1 2 1 1 2 1 Research supported by the Post-doctoral Fellowship Program of Korea Research Foundation KRF . THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2 2005 N3 1 Postnikov derived this identity from the study of a combinatorial interpretation for mixed Eulerian numbers which are coefficients of certain reparametrized volume polynomials which introduced in 3 . For more information see 2 3 . In the same talk he also asked for a combinatorial proof of identity 1 . Multiplying both sides of 1 by 2n and expanding the product in the right-hand side yields 2n n 1 n-1 E nE . b aCV b v2a v 7 2 Let LHSn resp. RHSn denote the left-hand resp. right-hand side of 2 . The aim of this paper is to hnd a combinatorial proof of 2 . In Section 2 we construct the sets F of labeled bicolored forests on n and Dn of certain labeled bicolored binary trees where the cardinalities equal LHSn and RHSn respectively. In Section 3 we give a bijection between F and Dn which completes the bijective proof