Multivariate asymptotic analysis of set partitions: Focus on blocks of fixed size

Year 2017, , 75 - 91, 11.01.2017

Guy Louchard

https://doi.org/10.13069/jacodesmath.37019

Abstract

Using the Saddle point method and multiseries expansions, we obtain from the exponential formula and Cauchy's integral formula,
asymptotic results for the number $T(n,m,k)$ of partitions of $n$ labeled objects with $m$ blocks of fixed size $k$. We analyze the central and non-central region. In the region $m=n/k-n^\al,\quad 1>\al>1/2$, we analyze the dependence of $T(n,m,k)$ on $\al$. This paper fits within the framework of Analytic Combinatorics.

Keywords

Set partitions, Bell numbers, Asymptotics, Saddle point method, Multiseries expansions, Analytic combinatorics

References

• [1] B. Chern, P. Diaconis, D. M. Kane, R. C. Rhoades, Closed expressions for set partition statistics, Res. Math. Sci. 1(2) (2014) 1–32.
• [2] B. Chern, P. Diaconis, D. M. Kane, R. C. Rhoades, Central limit theorems for some set partitions, Adv. Appl. Math. 70 (2015) 92–105.
• [3] R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, D. E. Knuth, On the LambertW function, Adv. Comput. Math. 5 (1996) 329–359.
• [4] P. Flajolet, R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.
• [5] B. Fristedt, The structure of random partitions of large sets, Technical report, University of Minnesota, 1987.
• [6] I. J. Good, Saddle–point methods for the multinomial distribution, Ann. Math. Statist. 28(4) (1957) 861–881.
• [7] R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Second Edition, Addison Wesley, 1994.
• [8] H. K. Hwang, On convergence rates in the central limit theorems for combinatorial structures, European J. Combin. 19(3) (1998) 329–343.
• [9] D. E. Knuth, The Art of Computer Programming, vol. 4a: Combinatorial Algorithms. Part I, Addison–Wesley, Upper Saddle River, New Jersey, 2011.
• [10] G. Louchard, Asymptotics of the Stirling numbers of the first kind revisited: A saddle point approach, Discrete Math. Theor. Comput. Sci. 12(2) (2010) 167–184.
• [11] G. Louchard, Asymptotics of the Stirling numbers of the second kind revisited: A saddle point approach, Appl. Anal. Discrete Math. 7(2) (2013) 193–210.
• [12] G. Louchard, Asymptotics of the Eulerian numbers revisited: A large deviation analysis, Online J. Anal. Comb. 10 (2015) 1–11.
• [13] T. Mansour, Combinatorics of Set Partitions, Discrete Mathematics and Its Applications Series, CRC Press, Boca Raton, FL, 2013.
• [14] B. Salvy, J. Shackell, Symbolic asymptotics: Multiseries of inverse functions, J. Symbolic Comput. 20(6) (1999) 543–563.
• [15] R. P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edn, Cambridge Studies in Advanced Mathematics, Vol. 49. Cambridge University Press, Cambridge, 2012.