Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-27T00:09:18.402Z Has data issue: false hasContentIssue false
  • English
  • Français

Part Sizes of Smooth Supercritical Compositional Structures

Published online by Cambridge University Press:  09 July 2014

EDWARD A. BENDER  and
ZHICHENG GAO
EDWARD A. BENDER
Affiliation:
Department of Mathematics, UCSD, La Jolla, CA 92093-0112, USA (e-mail: [email protected])
ZHICHENG GAO
Affiliation:
School of Mathematics and Statistics, Carleton University, Ottawa, Ontario K1S5B6, Canada (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We define the notion of smooth supercritical compositional structures. Two well-known examples are compositions and graphs of given genus. The ‘parts’ of a graph are the subgraphs that are maximal trees. We show that large part sizes have asymptotically geometric distributions. This leads to asymptotically independent Poisson variables for numbers of various large parts. In many cases this leads to asymptotic formulas for the probability of being gap-free and for the expected values of the largest part sizes, number of distinct parts and number of parts of multiplicity k.

Keywords

Primary 05A16Secondary 05A1505A0505C0505C1005C30
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 5: Honouring the Memory of Philippe Flajolet - Part 1 , September 2014 , pp. 686 - 716
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Apostol, T. (1976) Introduction to Analytic Number Theory, Undergraduate Texts in Mathematics, Springer.Google Scholar
[2]Banderier, C., Flajolet, P., Schaeffer, G. and Soria, M. (2001) Random maps, coalescing saddles, singularity analysis and Airy phenomena. Random Struct. Alg. 19 194–246.Google Scholar
[3]Bender, E. A. (1974) Convex n-ominoes. Discrete Math. 8 219–226. (The value of f in (11) is incorrect. The correct value, f = 2.67564, is in the abstract.)CrossRefGoogle Scholar
[4]Bender, E. A. (1974) Asymptotic methods in enumeration. SIAM Review 16 485–515.CrossRefGoogle Scholar
[5]Bender, E. A. and Canfield, E. R. (2009) Locally restricted compositions II: General restrictions and infinite matrices. Electron. J. Combin. 16 R108.CrossRefGoogle Scholar
[6]Bender, E. A., Canfield, E. R. and Gao, Z. C. (2012) Locally restricted compositions IV: Nearly free large parts and gap-freeness. Electron. J. Combin. 19 #14.Google Scholar
[7]Bender, E. A., Canfield, E. R. and Richmond, L. B. (2008) Coefficients of functional composition often grow smoothly. Electron. J. Combin. 15 R21.CrossRefGoogle Scholar
[8]Bender, E. A. and Gao, Z. C. (2011) Asymptotic enumeration of labelled graphs by genus. Electron. J. Combin. 18 #13.Google Scholar
[9]Bender, E. A. and Gao, Z. C. Locally restricted compositions V: Convex polyomino support. In preparation.Google Scholar
[10]Bhatia, D. P., Prasad, M. A. and Arora, D. (1997) Asymptotic results for the number of multidimensional partitions of an integer and directed compact lattice animals. J. Phys. A: Math. Gen. 30 2281–2285.Google Scholar
[11]Bousquet-Mélou, M. and Rechnitzer, A. (2002) Lattice animals and heaps of dimers. Discrete Math. 258 235–274.Google Scholar
[12]Chapuy, G., Fusy, É., Giménez, O., Mohar, B. and Noy, M. (2011) Asymptotic enumeration and limit laws for graphs of fixed genus. J. Combin. Theory Ser. A 118 748–777.Google Scholar
[13]Drmota, M. (1994) A bivariate asymptotic expansion of coefficients of powers of generating functions. Europ. J. Combin. 15 139–152.Google Scholar
[14]Flajolet, P. and Odlyzko, A. (1990) Singularity analysis of generating functions. SIAM J. Discrete Math. 3 216–240.Google Scholar
[15]Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.Google Scholar
[16]Gao, Z. C. and Wormald, N. C. (2000) The distribution of the maximum vertex degree in random planar maps. J. Combin. Theory, Ser. A 89 201–230.Google Scholar
[17]Gourdon, X. (1998) Largest component in random combinatorial structures. Discrete Math. 180 185–209.Google Scholar
[18]Hitczenko, P. and Knopfmacher, A. (2005) Gap-free compositions and gap-free samples of geometric random variables. Discrete Math. 294 225–239.Google Scholar
[19]Klarner, D. A. and Rivest, R. L. (1974) Asymptotic bounds for the number of convex $n$-ominoes. Discrete Math. 8 31–40.Google Scholar
[20]Louchard, G. (2003) The number of distinct part sizes of some multiplicity in compositions of an integer: A probabilistic analysis. In Discrete Random Walks: Paris 2003, pp. 155–170 (electronic).Google Scholar
[21]Louchard, G. (2008) Matrix compositions: A probabilistic analysis. Pure Math. Appl. 19 127–146.Google Scholar
[22]Munarini, E., Poneti, M. and Rinaldi, S. (2009) Matrix compositions. J. Integer Seq. 12 #09.4.8.Google Scholar
[23]Olver, F. W. J. (1974) Asymptotics and Special Functions, Academic Press.Google Scholar
[24]Prodinger, H. and Wagner, S. Bootstrapping and double-exponential limit laws. http://mathsci.sun.ac.za~swagner/pub.html.Google Scholar