zbMATH — the first resource for mathematics

Closed expressions for averages of set partition statistics. (English) Zbl 1339.15019
Summary: In studying the enumerative theory of super characters of the group of upper triangular matrices over a finite field, we found that the moments (mean, variance, and higher moments) of novel statistics on set partitions of \([n]=\{1,2,\dots,n\}\) have simple closed expressions as linear combinations of shifted Bell numbers. It is shown here that families of other statistics have similar moments. The coefficients in the linear combinations are polynomials in \(n\). This allows exact enumeration of the moments for small \(n\) to determine exact formulae for all \(n\).

15B33 Matrices over special rings (quaternions, finite fields, etc.)
05A15 Exact enumeration problems, generating functions
11B73 Bell and Stirling numbers
15A30 Algebraic systems of matrices
PDF BibTeX Cite
Full Text: DOI arXiv
[1] Chern B, Diaconis P, Kane DM, Rhoades RC: Asymptotic normality of set partition statistics associated with supercharacters. in press · Zbl 0835.20052
[2] Chen, WYC; Deng, EYP; Du, RRX; Stanley, RP, Crossings and nestings of matchings and partition, Trans. Amer. Math. Soc, 359, 1555-1575, (2007) · Zbl 1108.05012
[3] Stanley RP: Enumerative Combinatorics. Volume 2. Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge; 1999.
[4] Kreweras, G, Sur LES partitions noncroisées d’un cycle, Discrete Math, 1, 333-350, (1972) · Zbl 0231.05014
[5] Simion, R, Noncrossing partitions, Discrete Math, 217, 367-409, (2000) · Zbl 0959.05009
[6] Marberg E: Crossings and nestings in colored set partitions.Electron. J. Combin 2013.,20(4): Research Paper 6
[7] Mansour T: Combinatorics of Set Partitions. Discrete Mathematics and its Applications. CRC Press, Boca Raton, FL; 2013.
[8] Shattuck, M, Recounting the number of rises, levels, and descents in finite set partitions, Integers, 10, 179-185, (2010) · Zbl 1239.05023
[9] Kasraoui, A, Average values of some z-parameters in a random set partition, Electron. J. Combinatorics, 18, 42, (2011) · Zbl 1243.05033
[10] Mansour, T; Shattuck, M, Enumerating finite set partitions according to the number of connectors, Online J. Anal. Combinatorics, 6, 17, (2011) · Zbl 1292.05048
[11] Knopfmacher, A; Mansour, T; Wagne, S, Records in set partitions, Electron. J. Combinatorics, 17, 14, (2010) · Zbl 1193.05024
[12] Graham RL, Knuth DE, Patashnik O: Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley Publishing Company, Reading, MA; 1994. · Zbl 0836.00001
[13] Knuth D: The Art of Computer Programming vol. 4a: Combinatorial Algorithms. Part I. Addison-Wesley, Upper Saddle River, New Jersey; 2011.
[14] Stanley RP: Enumerative Combinatorics. Volume 1, 2nd edn. Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge; 2012.
[15] Riordan J: An Introduction to Combinatory Analysis. Wiley, New York; 1958. · Zbl 0078.00805
[16] Pitman J: Combinatorial Stochastic Processes. Springer, Berlin; 2006. · Zbl 1103.60004
[17] Garsia, A, An expose of the Mullin-Rota theory of polynomials of binomial type, Linear Multilinear Algebra, 1, 47-65, (1973) · Zbl 0287.05008
[18] Knuth D: Convolution polynomials. Math. J. 1992, 2:67-78.
[19] Halverson, T; Ram, A, Partition algebras, Eur. J. Combin, 26, 869-921, (2005) · Zbl 1112.20010
[20] Aguiar M, Mahajan S: Monoidal functors, species and Hopf Algebras. CRM monograph series. American Mathematical Society, Providence, RI; 2010. · Zbl 1209.18002
[21] Kasraoui A, Zeng J: Distribution of crossings, nestings and alignments of two edges in matchings and partitions.Electron. J. Combinatorics 2006.,12(1): Paper 33 · Zbl 1096.05006
[22] Kasraoui A: On the limiting distribution of some numbers of crossings in set partitions. arXiv:1301.6540 [math.CO] · Zbl 0906.60024
[23] Fristedt B: The structure of random partitions of large sets. Technical report. 1987.
[24] Hwang, HK, On convergence rates in the central limit theorems for combinatorial structures, Eur. J. Combin, 19, 329-343, (1998) · Zbl 0906.60024
[25] Stam, AJ, Generation of random partitions of a set by an urn model, J. Combin. Theory Series A, 35, 231-240, (1983) · Zbl 0513.05007
[26] Pitman, J, Some probabilistic aspects of set partitions, Amer. Math. Mon, 104, 201-209, (1997) · Zbl 0876.05005
[27] Erdös, P; Turán, P, On some problems of statistical group theory, I. Z, Whhr. Verw. Gebiete, 4, 151-163, (1965) · Zbl 0189.31302
[28] Erdös, P; Turán, P, On some problems of statistical group theory, II, Acta Math. Acad. Sci. Hun, 18, 151-163, (1967) · Zbl 0189.31302
[29] Erdös, P; Turán, P, On some problems of statistical group theory, III, Acta Math. Acad. Sci. Hun, 18, 309-320, (1967) · Zbl 0235.20003
[30] Erdös, P; Turán, P, On some problems of statistical group theory, IV, Acta Math. Acad. Sci. Hun, 19, 413-435, (1968) · Zbl 0235.20004
[31] Erdös, P; Turán, P, On some problems of statistical group theory, V. Periodica Math. Hung, 1, 5-13, (1971) · Zbl 0223.10005
[32] Erdös, P; Turán, P, On some problems of statistical group theory, VI, J. Ind. Math. Soc, 34, 175-192, (1970) · Zbl 0235.10008
[33] Erdös, P; Turán, P, On some problems of statistical group theory, VII, Periodica Math. Hung, 2, 149-163, (1972) · Zbl 0247.20008
[34] Fulman, J, Random matrix theory over finite fields, Bull. Amer. Math. Soc, 34, 51-85, (2002) · Zbl 0984.60017
[35] Diaconis, P; Fulman, J; Guralnick, R, On fixed points of random permutations, J. Alg. Comb, 28, 189-218, (2008) · Zbl 1192.20001
[36] Newman, MF; Kov’acs, LG (ed.), Groups of prime-power order, (1990), Berlin · Zbl 0726.20011
[37] Kerov, S, Asymptotic representation theory of the symmetric group and its applications in analysis, (2003), RI · Zbl 1031.20007
[38] Turán, P, Remarks on the characters belonging to the irreducible representations of the symmetric group \(S\)_{\(n\)} of \(n\) letters. Fourier analysis and approximation theory (proc. colloq., Budapest, 1976, vol. ii, (1978)
[39] Stanley, RP, Increasing and decreasing subsequences and their variants, (2006)
[40] Kerov, S; Vershik, A, Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tableaux, Docl. Akad. Nauk, 233, 1024-1027, (1977) · Zbl 0406.05008
[41] Logan, B; Shepp, L, A variational problem for random Young tableaux, Adv. Math, 26, 206-222, (1977) · Zbl 0363.62068
[42] Baik, J; Deift, P; Johansson, K, On the distribution of the length of the longest increasing subsequence of random permutations, J. Amer. Math. Soc, 12, 1119-1178, (1999) · Zbl 0932.05001
[43] Anderson GW, Guionnet A, Zeitouni O: Introduction to Random Matrices. Cambridge Press, Cambridge; 2009.
[44] Forrester P: Log-gases and Random Matrices. Princeton University Press, Princeton; 2010. · Zbl 1217.82003
[45] Arias-Castro, E; Diaconis, P; Stanley, R, A super-class walk on upper-triangular matrices, J. Algebra, 278, 739-765, (2004) · Zbl 1056.60006
[46] André, C, Basic characters of unitriangular group, J. Algebra, 175, 287-319, (1995) · Zbl 0835.20052
[47] André, C; Santana, AP (ed.); Duarte, ALJFQ (ed.), Irreducible characters of finite algebra groups, (1998), Coimbra
[48] André C: Basic characters of the unitriangular group (for arbitrary primes). 2002. · Zbl 1005.20034
[49] Yan, N, Representation theory of the finite unipotent linear group. phd thesis, pennsylvania state university, (2001)
[50] Aguiar, M; André, C; Benedetti, C; Bergeron, N; Chen, Z; Diaconis, P; Hendrickson, A; Hsiao, S; Isaacs, IM; Jedwab, A; Johnson, K; Karaali, G; Lauve, A; Le, T; Lewis, S; Li, H; Magaard, K; Marberg, E; Novelli, J-C; Pang, A; Saliola, F; Tevlin, L; Thibon, JY; Thiem, N; Venkateswaran, V; Vinroot, CR; Yan, N; Zabrocki, M, Supercharacters, symmetric functions in noncommuting variables, and related Hopf algebras, Adv. Math, 229, 2310-2337, (2012) · Zbl 1237.05208
[51] Aguiar, M; Bergeron, N; Thiem, N, Hopf monoids from class functions on unitriangular matrices, Algebra and Number Theory,, 7-7, 1743-1779, (2013) · Zbl 1276.05127
[52] Diaconis, P; Isaacs, IM, Supercharacters and superclasses for algebra groups, Trans. Amer. Math. Soc, 360, 2359-2392, (2008) · Zbl 1137.20008
[53] Diaconis, P; Thiem, N, Supercharacter formulas for pattern groups, Trans. Amer. Math. Soc, 361, 3501-3533, (2009) · Zbl 1205.20006
[54] Marberg, E, Actions and identities on set partitions, Electron. J. Combinatorics, 19, 31, (2013) · Zbl 1243.05035
[55] Rhoades RC 2013.http://math.stanford.edu/ rhoades/RESEARCH/papers.html · Zbl 0408.10006
[56] Bergeron, N; Thiem, N, A supercharacter table decomposition via power-sum symmetric functions, Int. J. Algebra Comput. (IJAC), 23-4, 763-778, (2013) · Zbl 1283.20004
[57] Lunnon, WF; Pleasants, PAB; Stephens, NM, Arithmetic properties of Bell numbers to a composite modulus i, Acta Arith, 35, 1-16, (1979) · Zbl 0408.10006
[58] Montgomery, PL; Nahm, SJr, SSW: the period of the Bell numbers modulo a prime, Math. Comp, 79, 1793-1800, (2010) · Zbl 1216.11028
[59] Nijenhuis A, Wilf HS: Combinatorial Algorithms. For Computers and Calculators. Computer Science and Applied Mathematics. Academic Press, Inc, New York-London; 1978. · Zbl 0476.68047
[60] Ruskey F: Combinatorial Object Server. 2013.http://www.theory.csc.uvic.ca/ cos/
[61] Bruijn de: NG. Asymptotic Methods in Analysis.Dover, New York; 1981. · Zbl 0556.41021
[62] Sloane N: Online Encyclopedia of Integer Sequences. 2013.http://oeis.org/
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.