Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-20T00:04:52.644Z Has data issue: false hasContentIssue false
  • English
  • Français

A General Asymptotic Scheme for the Analysis of Partition Statistics

Published online by Cambridge University Press:  08 September 2014

PETER J. GRABNER ,
ARNOLD KNOPFMACHER  and
STEPHAN WAGNER
PETER J. GRABNER
Affiliation:
Institut für Analysis und Computational Number Theory, Technische Universität Graz, Steyrergasse 30, 8010 Graz, Austria (e-mail: [email protected])
ARNOLD KNOPFMACHER
Affiliation:
The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, PO Wits, 2050 Johannesburg, South Africa (e-mail: [email protected])
STEPHAN WAGNER
Affiliation:
Department of Mathematical Sciences, Stellenbosch University, 7602 Stellenbosch, South Africa (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider statistical properties of random integer partitions. In order to compute means, variances and higher moments of various partition statistics, one often has to study generating functions of the form P(x)F(x), where P(x) is the generating function for the number of partitions. In this paper, we show how asymptotic expansions can be obtained in a quasi-automatic way from expansions of F(x) around x = 1, which parallels the classical singularity analysis of Flajolet and Odlyzko in many ways. Numerous examples from the literature, as well as some new statistics, are treated via this methodology. In addition, we show how to compute further terms in the asymptotic expansions of previously studied partition statistics.

Keywords

Primary 11P82Secondary 05A1605A17
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 6: Honouring the Memory of Philippe Flajolet - Part 2 , November 2014 , pp. 1057 - 1086
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]Andrews, G. E. (1998) The Theory of Partitions, Cambridge Mathematical Library, Cambridge University Press.Google Scholar
[2]Apostol, T. M. (1990) Modular Functions and Dirichlet Series in Number Theory, second edition, Vol. 41 of Graduate Texts in Mathematics, Springer.Google Scholar
[3]Brennan, C., Knopfmacher, A. and Wagner, S. (2008) The distribution of ascents of size d or more in partitions of n. Combin. Probab. Comput. 17 495–509.Google Scholar
[4]Corteel, S., Pittel, B., Savage, C. and Wilf, H. (1999) On the multiplicity of parts in a random partition. Random Struct. Alg. 14 185–197.Google Scholar
[5]Erdős, P. and Lehner, J. (1941) The distribution of the number of summands in the partitions of a positive integer. Duke Math. J. 8 335–345.Google Scholar
[6]Flajolet, P., Gourdon, X. and Dumas, P. (1995) Mellin transforms and asymptotics: Harmonic sums. Theoret. Comput. Sci. 144 3–58.Google Scholar
[7]Flajolet, P. and Odlyzko, A. (1990) Singularity analysis of generating functions. SIAM J. Discrete Math. 3 216–240.Google Scholar
[8]Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.Google Scholar
[9]Goh, W. M. Y. and Schmutz, E. (1995) The number of distinct part sizes in a random integer partition. J. Combin. Theory Ser. A 69 149–158.Google Scholar
[10]Grabner, P. J. and Knopfmacher, A. (2006) Analysis of some new partition statistics. Ramanujan J. 12 439–454.CrossRefGoogle Scholar
[11]Han, G.-N. (2008) An explicit expansion formula for the powers of the Euler product in terms of partition hook lengths. arXiv:0804.1849v3 [math.CO]Google Scholar
[12]Husimi, K. (1938) Partitio numerorum as occurring in a problem of nuclear physics. In Proc. Physico-Mathematical Society of Japan 20 912–925.Google Scholar
[13]Hwang, H.-K. and Yeh, Y.-N. (1997) Measures of distinctness for random partitions and compositions of an integer. Adv. Appl. Math. 19 378–414.CrossRefGoogle Scholar
[14]Kessler, I. and Livingston, M. (1976) The expected number of parts in a partition of n. Monatsh. Math. 81 203–212.Google Scholar
[15]Knopfmacher, A. and Munagi, A. O. (2009) Successions in integer partitions. Ramanujan J. 18 239–255.Google Scholar
[16]Knopfmacher, A. and Warlimont, R. (2006) Gaps in integer partitions. Util. Math. 71 257–267.Google Scholar
[17]Mutafchiev, L. R. (2005) On the maximal multiplicity of parts in a random integer partition. Rama-nu-jan J. 9 305–316.Google Scholar
[18]Rademacher, H. (1973) Topics in Analytic Number Theory (Grosswald, E., Lehner, J. and Newman, M., eds), Vol. 169 of Die Grundlehren der Mathematischen Wissenschaften, Springer.Google Scholar
[19]Ralaivaosaona, D. (2012) On the distribution of multiplicities in integer partitions. Ann. Combin. 16 871–889.CrossRefGoogle Scholar
[20]Richmond, L. B. (1974/75) The moments of partitions I. Acta Arith. 26 411–425.Google Scholar
[21]Stanley, R. P. (1997) Enumerative Combinatorics 1, Vol. 49 of Cambridge Studies in Advanced Mathematics, Cambridge University Press.Google Scholar
[22]Szekeres, G. (1990) Asymptotic distribution of partitions by number and size of parts. In Number Theory I: Budapest 1987, Vol. 51 of Colloq. Math. Soc. János Bolyai, North-Holland, pp. 527–538.Google Scholar
[23]Szpankowski, W. (2001) Average Case Analysis of Algorithms on Sequences, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience.Google Scholar
[24]Wagner, S. (2006) A class of trees and its Wiener index. Acta Appl. Math. 91 119–132.Google Scholar
[25]Wagner, S. (2009) On the distribution of the longest run in number partitions. Ramanujan J. 20 189–206.CrossRefGoogle Scholar
[26]Wagner, S. (2011) Limit distributions of smallest gap and largest repeated part in integer partitions. Ramanujan J. 25 229–246.Google Scholar
[27]Watson, G. N. (1995) A Treatise on the Theory of Bessel Functions, Cambridge Mathematical Library. Cambridge University Press. Reprint of the second (1944) edition.Google Scholar