Random set partitions: Asymptotics of subset counts. (English) Zbl 0895.60008
Summary: We study the asymptotics of subset counts for the uniformly random partition of the set \([n]\). It is known that typically most of the subsets of the random partition are of size \(r\), with \(re^r=n\). Confirming a conjecture formulated by R. Arratia and S. Tavaré [Adv. Math. 104, No. 1, 90-154 (1994; Zbl 0802.60008)], we prove that the counts of other subsets are close, in terms of the total variation distance, to the corresponding segments of a sequence \(\{Z_j\}\) of independent, Poisson \((r^j/j!)\) distributed random variables. J. M. DeLaurentis and B. G. Pittel [Stochastic Processes Appl. 15, 155-167 (1983; Zbl 0507.60007)] had proved that the finite-dimensional distributions of a continuous time process that counts the typical size subsets converge to those of the Brownian bridge process. Combining the two results allows to prove a functional limit theorem which covers a broad class of the integral functionals. Among illustrations, we prove that the total number of refinements of a random partition is asymptotically lognormal.
Keywords:
subset counts for the uniformly random partition; Brownian bridge process; integral functionals; random partitionReferences:
| [1] | Arratia, R.; Tavaré, S., Independent process approximations for random combinatorial structures, Adv. in Math., 104, 90-154 (1994) · Zbl 0802.60008 |
| [2] | Canfield, E. R.; Harper, L. H., Large antichains in the partition lattice, Random Structures and Algorithms, 6, 89-104 (1995) · Zbl 0813.06002 |
| [3] | DeLaurentis, J. M.; Pittel, B. G., Counting subsets of the random partition and the “Brownian Bridge” process, Stochastic Processes Appl., 15, 155-167 (1983) · Zbl 0507.60007 |
| [4] | Durrett, R., Probability: Theory and Examples (1991), Wadsworth & Brooks/Cole: Wadsworth & Brooks/Cole Belmont · Zbl 0709.60002 |
| [5] | Fristedt, B., The structure of random partitions of large integers, Trans. Amer. Math. Soc., 337, 703-735 (1993) · Zbl 0795.05009 |
| [6] | Gihman, I. I.; Skorohod, A. V., The Theory of Stochastic Processes (1974), Springer-Verlag: Springer-Verlag New York · Zbl 0291.60019 |
| [7] | Goh, W. M.Y.; Schmutz, E., Gap-free set partitions, Random Structures and Algorithms, 3, 9-18 (1992) · Zbl 0744.05003 |
| [8] | Harper, L. H., Stirling behavior is asymptotically normal, Ann. Math. Statist., 38, 410-414 (1967) · Zbl 0154.43703 |
| [9] | Moser, L.; Wyman, M., An asymptotic for the Bell numbers, Trans. Roy. Soc. Can., 49, 49-54 (1955) · Zbl 0066.31001 |
| [10] | Odlyzko, A. M.; Richmond, L. B., On the number of distinct block sizes in partitions of a set, J. Combin. Theory Ser. A, 38, 170-181 (1985) · Zbl 0575.05005 |
| [11] | Pittel, B., On a likely shape of the random Ferrers diagram, Adv. Appl. Math., 18, 432-488 (1997) · Zbl 0894.11039 |
| [12] | Sachkov, V., Random partitions of sets, Theory Probab. Appl., 19, 184-190 (1974) · Zbl 0326.60023 |
| [13] | Sachkov, V. N., Probabilistic Methods in Combinatorial Analysis (1978), Nauka: Nauka Moscow · Zbl 0517.05001 |
| [14] | Rota, G. C., The number of partitions of a set, Amer. Math. Monthly, 71, 498-504 (1964) · Zbl 0121.01803 |
| [15] | Shepp, L. A.; Lloyd, S. P., Ordered cycle lengths in a random permutation, Trans. Amer. Math. Soc., 121, 340-357 (1966) · Zbl 0156.18705 |
| [16] | Stanley, R. P., Enumerative Combinatorics (1986), Wadsworth & Brooks/Cole: Wadsworth & Brooks/Cole Belmont · Zbl 0608.05001 |
| [17] | Wilf, H., Generatingfunctionology (1990), Academic Press: Academic Press New York · Zbl 0689.05001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
