Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Asymptotics for the Probability of Connectedness and the Distribution of Number of Components Jason P. Bell Department of Mathema. | Asymptotics for the Probability of Connectedness and the Distribution of Number of Components Jason P. Bell Department of Mathematics University of California San Diego La Jolla CA 92903-0112 USA email jbell@ Edward A. Bender Department of Mathematics University of California San Diego La Jolla CA 92903-0112 USA email ebender@ Peter J. Cameron School of Mathematical Sciences Queen Mary and Westfield College Mile End Road London E1 4NS England email L. Bruce Richmond Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario N2L 3G1 Canada email lbrichmond@ .ca Submitted January 21 2000 Accepted May 30 2000 Abstract Let pn be the fraction of structures of size n which are connected . a the fraction of labeled or unlabeled n-vertex graphs having one component b the fraction of partitions of n or of an n-set having a single part or block or c the fraction of n-vertex forests that contain only one tree. Various authors have considered limpn provided it exists. It is convenient to distinguish three cases depending on the nature of the power series for the structures purely formal convergent on the circle of convergence and other. We determine all possible values for the pair liminf pn limsuppn in these cases. Only in the convergent case can one have 0 lim pn 1. We study the existence of lim pn in this case. AMS-MOS Subject Classification 1990 05A16 Secondary 05C30 05C40 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 7 2000 R33 2 1. Introduction Throughout An will denote the number of structures of size n Cn will denote the number that are connected and pn Cn An whenever An 0. We consider two situations either the objects are labeled and the exponential generating functions are related by A x exp C x or the objects are unlabeled and the ordinary generating functions are related by A x exp C xk k 1 2 Perhaps the most interesting omissions are objects with noncrossing parts which lead to .
