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: Counting Rooted Trees : The Universal Law t(n) ∼ Cρ−nn−3/2. | Counting Rooted Trees The Universal Law t n Cp n 2 2 Jason P. Bell Department of Mathematics Simon Fraser University 8888 University Dr. Burnaby BC V5A 1S6 Canada jpb@ Stanley N. Burris Department of Pure Mathematics University of Waterloo Waterloo Ontario N2L 3G1 Canada snburris@ Karen A. Yeats Department of Mathematics and Statistics Boston University 111 Cummington Street Boston MA 02215 USA kayeats@ Submitted Jul 19 2004 Accepted Jul 28 2006 Published Aug 3 2006 Mathematics Subject Classifications Primary 05C05 Secondary 05A16 05C30 30D05 Abstract Combinatorial classes T that are recursively defined using combinations of the standard multiset sequence directed cycle and cycle constructions and their restrictions have generating series T z with a positive radius of convergence for most of these a simple test can be used to quickly show that the form of the asymptotics is the same as that for the class of rooted trees Cp nn 3 2 where p is the radius of convergence of T. We are greatly indebted to the referee for bringing up important questions especially regarding the role of Set that led us to thoroughly rework the paper. The second and third authors would like to thank NSERC for support of this research. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R63 1 1 Introduction The class of rooted trees perhaps with additional structure as in the planar case is unique among the well studied classes of structures. It is so easy to find endless possibilities for defining interesting subclasses as the fixpoint of a class construction where the constructions used are combinations of a few standard constructions like sequence multiset and add-a-root. This fortunate situation is based on a simple reconstruction property removing the root from a tree gives a collection of trees called a forest and it is trivial to reconstruct the original tree from the forest by adding a root . Since we will be frequently .
