# zbMATH — the first resource for mathematics

Central limit theorems for patterns in multiset permutations and set partitions. (English) Zbl 1434.60040
Summary: We use the recently developed method of weighted dependency graphs to prove central limit theorems for the number of occurrences of any fixed pattern in multiset permutations and in set partitions. This generalizes results for patterns of size 2 in both settings, obtained by E. R. Canfield et al. [Adv. Appl. Math. 46, No. 1–4, 109–124 (2011; Zbl 1227.05009)] and B. Chern et al. [Adv. Appl. Math. 70, 92–105 (2015; Zbl 1327.60030)], respectively.
##### MSC:
 60C05 Combinatorial probability 60F05 Central limit and other weak theorems 05A05 Permutations, words, matrices 05A18 Partitions of sets
MahonianStat
Full Text:
##### References:
  Albert, M. H., Aldred, R. E. L., Atkinson, M. D., Handley, C. and Holton, D. (2001). Permutations of a multiset avoiding permutations of length 3. European J. Combin. 22 1021-1031. · Zbl 0988.05005  Bóna, M. (2010). On three different notions of monotone subsequences. In Permutation Patterns. London Mathematical Society Lecture Note Series 376 89-114. Cambridge Univ. Press, Cambridge. · Zbl 1217.05007  Brillinger, D. (1969). The calculation of cumulants via conditioning. Ann. Inst. Statist. Math. 21 215-218. · Zbl 0181.46103  Canfield, E. R. (1995). Engel’s inequality for Bell numbers. J. Combin. Theory Ser. A 72 184-187. · Zbl 0830.11010  Canfield, E. R., Janson, S. and Zeilberger, D. (2011). The Mahonian probability distribution on words is asymptotically normal. Adv. in Appl. Math. 46 109-124. · Zbl 1227.05009  Chatterjee, S. (2008). A new method of normal approximation. Ann. Probab. 36 1584-1610. · Zbl 1159.62009  Chern, B., Diaconis, P., Kane, D. M. and Rhoades, R. C. (2014). Closed expressions for averages of set partition statistics. Res. Math. Sci. 1 Art. 2, 32. · Zbl 1339.15019  Chern, B., Diaconis, P., Kane, D. M. and Rhoades, R. C. (2015). Central limit theorems for some set partition statistics. Adv. in Appl. Math. 70 92-105. · Zbl 1327.60030  Crane, H., DeSalvo, S. and Elizalde, S. (2018). The probability of avoiding consecutive patterns in the Mallows distribution. Random Structures Algorithms 53 417-447. · Zbl 1401.05010  Féray, V. (2013). Asymptotic behavior of some statistics in Ewens random permutations. Electron. J. Probab. 18 no. 76, 32. · Zbl 1314.05016  Féray, V. (2018). Weighted dependency graphs. Electron. J. Probab. 23 Paper No. 93, 65. · Zbl 1414.60014  Féray, V., Méliot, P.-L. and Nikeghbali, A. (2016). Mod-$$\varphi$$ Convergence: Normality Zones and Precise Deviations. SpringerBriefs in Probability and Mathematical Statistics. Springer, Cham. · Zbl 1387.60003  Flajolet, P., Szpankowski, W. and Vallée, B. (2006). Hidden word statistics. J. ACM 53 147-183. · Zbl 1316.68111  Fulman, J. (2004). Stein’s method and non-reversible Markov chains. In Stein’s Method: Expository Lectures and Applications. Institute of Mathematical Statistics Lecture Notes—Monograph Series 46 69-77. IMS, Beachwood, OH.  Goldstein, L. (2005). Berry-Esseen bounds for combinatorial central limit theorems and pattern occurrences, using zero and size biasing. J. Appl. Probab. 42 661-683. · Zbl 1087.60021  Harper, L. H. (1967). Stirling behavior is asymptotically normal. Ann. Math. Stat. 38 410-414. · Zbl 0154.43703  Hoeffding, W. (1948). A class of statistics with asymptotically normal distribution. Ann. Math. Stat. 19 293-325. · Zbl 0032.04101  Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 13-30. · Zbl 0127.10602  Hofer, L. (2017). A central limit theorem for vincular permutation patterns. Discrete Math. Theor. Comput. Sci. 19 Paper No. 9, 26. · Zbl 1401.05013  Janson, S. (1988). Normal convergence by higher semi-invariants with applications to sums of dependent random variables and random graphs. Ann. Probab. 16 305-312. · Zbl 0639.60029  Janson, S. (1994). Orthogonal decompositions and functional limit theorems for random graph statistics. Mem. Amer. Math. Soc. 111 vi+78. · Zbl 0810.05001  Janson, S. (1997). Gaussian Hilbert Spaces. Cambridge Tracts in Mathematics 129. Cambridge Univ. Press, Cambridge.  Janson, S., Łuczak, T. and Rucinski, A. (2000). Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley Interscience, New York.  Janson, S., Nakamura, B. and Zeilberger, D. (2015). On the asymptotic statistics of the number of occurrences of multiple permutation patterns. J. Comb. 6 117-143. · Zbl 1312.05011  Leonov, V. P. and Sirjaev, A. N. (1959). On a method of calculation of semi-invariants. Theory Probab. Appl. 4 319-329. · Zbl 0087.33701  Mikhaĭlov, V. G. (1991). On a theorem of Janson. Theory Probab. Appl. 36 173-176. · Zbl 0751.60021  Mitzenmacher, M. and Upfal, E. (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge Univ. Press, Cambridge. · Zbl 1092.60001  Rota, G.-C. (1964). The number of partitions of a set. Amer. Math. Monthly 71 498-504. · Zbl 0121.01803  Ruciński, A. (1988). When are small subgraphs of a random graph normally distributed? Probab. Theory Related Fields 78 1-10. · Zbl 0627.60045  Schutzenberger, M.-P. (1947). Sur certains paramètres caractéristiques des systèmes d’événements compatibles et dépendants et leur application au calcul des cumulants de la répétition. C. R. Math. Acad. Sci. Paris 225 277-278. · Zbl 0029.36901  Stam, A. J. (1983). Generation of a random partition of a finite set by an urn model. J. Combin. Theory Ser. A 35 231-240. · Zbl 0513.05007  Thiel, M. (2016). The inversion number and the major index are asymptotically jointly normally distributed on words. Combin. Probab. Comput. 25 470-483. · Zbl 1372.05005  Ursell, H. D. (1927). The evaluation of Gibbs’ phase-integral for imperfect gases. Math. Proc. Cambridge Philos. Soc. 23 685-697. · JFM 53.0868.01
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.