tailieunhanh - Báo cáo khoa học: Colored Pr¨ufer codes for k-edge colored trees

A combinatorial bijection between k-edge colored trees and colored Pr¨ufer codes for labelled trees is established. This bijection gives a simple combinatorial proof for the number k(n − 2)!nk−n n−2 of k-edge colored trees with n k-edge colored tree is a labelled tree whose edges are colored from a set of k colors such that any two edges with a common vertex have different colors | Colored Priifer codes for k-edge colored trees Manwon Cho Dongsu Kim l Seunghyun Seo and Heesung Shin Department of Mathematics KAIST Daejeon 305-701 Korea Submitted Dec 31 2002 Accepted Oct 15 2003 Published Jul 19 2004 MR Subject Classifications 05C05 05C30 Abstract A combinatorial bijection between k-edge colored trees and colored Prufer codes for labelled trees is established. This bijection gives a simple combinatorial proof for the number k n 2 of k-edge colored trees with n vertices. nk n n 2 1 Introduction A k-edge colored tree is a labelled tree whose edges are colored from a set of k colors such that any two edges with a common vertex have different colors 2 p81 . For a pair n k of positive integers let Cn k denote the set of all k-edge colored trees on vertex set n 1 2 . n with color set k . The number of k-edge colored trees in Cn k is already known Theorem 1. The number of k-edge colored trees on vertex set n n 2 is k nk n nk n 1 nk 2n 3 k n 2 Stanley in 2 p124 introduces a proof of the above formula and asks whether there is a simple bijective proof. In this paper we provide a combinatorial bijection between k-edge colored trees and colored Prfifer codes thus establishing a simple bijective proof of the above formula. The Prufer code y T a-1 . an-2 1 of a labelled tree T with vertex set n is obtained from the tree by successively pruning the leaf with the largest label. To obtain the code from T we remove the largest leaf in each step recording its neighbor ai from the tree until the single vertex 1 is left. The inverse of y can be described easily. Let Ơ a1 . an-2 1 be a sequence of positive integers with ai G n for all i. We can find the tree T whose code is Ơ as follows Corresponding author dskim@ tPartially supported by the Korea Research Foundation Grant KRF-2001-015-DP0055 . THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 N10 1 Let V 1 and E 0. For each i from n 2 to 1 if a G V then set bi 1 ữị otherwise set bi 1 min x