tailieunhanh - Báo cáo toán học: "On an identity for the cycle indices of rooted tree automorphism groups"

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: On an identity for the cycle indices of rooted tree automorphism groups. | On an identity for the cycle indices of rooted tree automorphism groups Stephan G. Wagner Institut fur Analysis und Computational Number Theory Technische Universitat Graz Steyrergasse 30 8010 Graz Austria wagner@ Submitted Jul 25 2006 Accepted Sep 15 2006 Published Sep 22 2006 Mathematics Subject Classifications 05A15 05A19 05C30 Abstract This note deals with a formula due to G. Labelle for the summed cycle indices of all rooted trees which resembles the well-known formula for the cycle index of the symmetric group in some way. An elementary proof is provided as well as some immediate corollaries and applications in particular a new application to the enumeration of k-decomposable trees. A tree is called k-decomposable in this context if it has a spanning forest whose components are all of size k. 1 Introduction Polya s enumeration method is widely used for graph enumeration problems - we refer to 6 and the references therein for instance. For the application of this method information on the cycle indices of certain groups is needed - mostly these are comparatively simple examples such as the cyclic group the dihedral group or the symmetric group. A very well-known formula gives the cycle index of the symmetric group Sn we adopt the notation from 6 here n Ik Z Sn X YXi- 1 . kjk jk j1 2j2 njn nk 1 J One has 1 1 X Z Sn tn exp atk an identity which is of importance in various tree counting problems cf. again 6 . The author is supported by project S9611 of the Austrian Science Foundation FWF THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 N14 1 In the past several tree counting problems related to the automorphism groups of trees have been investigated. We state for instance the enumeration of identity trees see 7 and the question of determining the average size of the automorphism group in certain classes of trees see 9 10 . Therefore it is not surprising that so-called cycle index series or indicatrix series 2 8 are of interest in .