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: Bijective Proofs of Identities from Colored Binary Trees. | Bijective Proofs of Identities from Colored Binary Trees Sherry . Yan Department of Mathematics Zhejiang Normal University Jinhua 321004 . China hfy@ Submitted May 23 2008 Accepted Jun 6 2008 Published Jun 13 2008 Mathematics Subject Classifications 05A05 05C30 Abstract This note provides bijective proofs of two combinatorial identities involving generalized Catalan number Cm 5 n - co recently proposed by Sun. 1 Introduction Recently by using generating functions and Lagrange inversion formula Sun 2 deduced the following identity involving generalized Catalan number Cm 5 n 5n m 5nfm . n 4j Em 5p m n p m 1 5p m p n 4p p 0 bn 2j E 1 p m m n p-1 m 2n-2p-1 1 m n p n 2p p 0 which in the case m 1 leads to Ln 4j 1 n Ln 2j XJ 1 i5p 1J n p Ị XJ _1 p 1 5p 1 p 7 n Ip n 1 p 0 p 0 2n 2p n 2p n p p In this note we give a parity reversing involution on colored binary trees which leads to a combinatorial interpretation of Formula . We make a simple variation of the bijection between colored ternary trees and binary trees proposed by Sun 2 and find a correspondence between a certain class of binary trees and the set of colored 5-ary trees. The generalization of the parity reversing involution and the bijection to forests of colored binary trees and forests of colored 5-ary trees leads to a bijective proof of Formula . THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 N20 1 2 A parity reversing involution on colored binary trees In this section we provide a parity reversing involution on a class of colored binary trees. Before introducing the involution we recall some definitions and notations. An internal vertex of a binary tree is a vertex that has children. Let Bn denote the set of full binary trees with n internal vertices. Let B 2 Bn and P v0v1 Vk be a path of length k of B viewing from the root . P is called a L-path if v is a left child of vi_1 for 1 i k. P is called a maximal L-path if there exists no vertex such that uP or Pu forms a L-path. .
