tailieunhanh - Báo cáo toán học: "A combinatorial proof of Postnikov’s identity and a generalized enumeration of labeled trees"

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@ 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