Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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í toán học quốc tế đề tài: Admissible Functions and Asymptotics for Labelled Structures by Number of Components Edward. | Admissible Functions and Asymptotics for Labelled Structures by Number of Components Edward A. Bender Center for Communications Research 4320 Westerra Court San Diego CA 92121 USA ed@ccrwest.org L. Bruce Richmond Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario N2L 3G1 Canada lbrichmo@watdragon.uwaterloo.ca Submitted August 19 1996 Accepted November 27 1996 Abstract Let a n k denote the number of combinatorial structures of size n with k components. One often has 52n k a n k xnyk n exp yC x where C x is frequently the exponential generating function for connected structures. How does a n k behave as a function of k when n is large and C x is entire or has large singularities on its circle of convergence The Flajolet-Odlyzko singularity analysis does not directly apply in such cases. We extend some of Hayman s work on admissible functions of a single variable to functions of several variables. As applications we obtain asymptotics and local limit theorems for several set partition problems decomposition of vector spaces tagged permutations and various complete graph covering problems. 1991 AMS Classihcation Numbers. Primary 05A16 Secondary 05A18 15A03 41A60 THE ELECTRONIC JOURNAL OF COMBINATORICS 3 1996 R34 2 1. Introduction A variety of combinatorial structures can be decomposed into components so that the generating function for all structures is the exponential of the generating function for components A x eC x . This is a single variable instance of the exponential formula. In this case A X y eyC x is the generating function for structures by number of components and is an ordinary generating function in y. For the present discussion we assume C x is an exponential generating function. One often wishes to study an k xnyk n A x y the number of fe-component structures of size n. In particular one may ask how an k varies with k for hxed large n. From a somewhat different viewpoint one may want to study the probability .
