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í Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: A simple bijection between binary trees and colored ternary trees. | A simple bijection between binary trees and colored ternary trees Yidong Sun Department of Mathematics Dalian Maritime University 116026 Dalian . China sydmath@ Submitted Feb 25 2009 Accepted Mar 28 2010 Published Apr 5 2010 Mathematics Subject Classification 05C05 05A19 Abstract In this short note we first present a simple bijection between binary trees and colored ternary trees and then derive a new identity related to generalized Catalan numbers. Keywords Binary tree Ternary tree Generalized Catalan number. 1 Introduction Recently Mansour and the author 2 obtained an identity involving 2-Catalan numbers Cn2 TC-W 2n l and 3-Catalan numbers C n 2 2n l k nJ tA A 1 . 3n l n y2 1 3p 1Wn p A 3P A p A 3P 1 f2n 1 2n 1 n J 1-1 In this short note we first present a simple bijection between complete binary trees and colored complete ternary trees and then derive the following generalized identity n 2 m i3p m in p m 1 3p m p J n 2p m i2n m 2n m n 2 A bijective algorithm for binary and ternary trees A colored ternary trees is a complete ternary tree such that all its vertices are signed a nonnegative integer called color number. Let Tn p denote the set of colored ternary trees THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 N20 1 T with p internal vertices such that the sum of all the color numbers of T is n 2p. Define Tn U Tn . Let Bn denote the set of complete binary trees with n internal vertices. For any B G Bn let P V1V2 Vk be a path of length k of B viewed from the root of B . P is called a R-path if 1 Vi is the right child of Vi-1 for 2 i k and 2 the left child of Vi is a leaf for 1 i k. In addition P is called a maximal R-path if there exists no vertex u such that uP or Pu forms a R-path. P is called an L-path if k 2 and Vi is the left child of vi-1 for 2 i k. P is called a maximal L-path if there exists no vertex u such that uP or Pu forms an L-path. Clearly a leaf can never be R-path or L-path. Note that the definition of L-path is different .
