TAILIEUCHUNG - Báo cáo toán học: "Bijective Proofs of Identities from Colored Binary Trees"

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

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.