Set partitions and m-excedances

Toufik Mansour and Mark Shattuck
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 22, 2016, Number 1, Pages 42–54
Full paper (PDF, 206 Kb)

Details

Authors and affiliations

Toufik Mansour
Department of Mathematics, University of Haifa
3498838 Haifa, Israel

Mark Shattuck
Department of Mathematics, University of Haifa
3498838 Haifa, Israel

Abstract

In this paper, we consider a generalized m-excedance statistic on set partitions which is analogous to the usual excedance statistic on permutations when m = 0. We study it from a probabilistic perspective in which set partitions are regarded as geometrically distributed words satisfying a so-called restricted growth property. We derive a general set of recurrences satisfied by the relevant generating functions and, in the m = 0 and m = 1 cases, find an explicit formula for the distribution of the statistic recording the number of m-excedances in partitions having a fixed number of blocks. When m = 0, one can also determine the joint distribution for the number of excedances with the major index statistic on set partitions. Further recurrences may be given in this case as well as formulas for the mean number of excedances and the variance.

Keywords

• Set partition
• Geometric random variable
• Excedance
• q-generalization

AMS Classification

• 05A15
• 05A18
• 60C05

References

1. Archibald, M., & Knopfmacher A. (2009) The average position of the d-th maximum in a sample of geometric random variables, Statist. Probab. Lett., 79, 864–872.
2. Archibald, M., & Knopfmacher A. (2014) The largest missing value in a sample of geometric random variables, Combin. Probab. Comput., 23(5), 670–685.
3. Baril, J.-L. (2013) Statistics-preserving bijections between classical and cyclic permutations, Inform. Process. Lett., 113(1–2), 17–22.
4. Brennan, C., & Knopfmacher, A. (2013) Descent variation of samples of geometric random variables, Discrete Math. Theor. Comput. Sci., 15:2, 1–12.
5. Elizalde, S. (2011-2) Fixed points and excedances in restricted permutations, Electron. J. Combin., 18(2), #P29.
6. Goyt, A. (2008) Avoidance of partitions of a three element set, Adv. in Appl. Math., 41, 95–114.
7. MacMahon, P. A. (1913) The indices of permutations and derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects, Amer. J. Math., 35(3), 281–322.
8. MacMahon, P. A. (1960) Combinatory Analysis, Vol. 2, Cambridge University Press, 1915–1916. Reprinted by Chelsea, New York.
9. Mansour, T. (2012) Combinatorics of Set Partitions, CRC Press, Boca Raton.
10. Mansour, T., & Shattuck, M. (2012) Set partitions as geometric words, Australas. J. Combin.,53, 31–39.
11. Mantaci, R. & Rakotondrajao, F. (2003) Exceedingly deranging!, Adv. in Appl. Math.,30(1–2), 177–188.
12. Milne, S. (1978) A q-analog of restricted growth functions, Dobinski’s equality, and Charlier polynomials, Trans. Amer. Math. Soc., 245, 89–118.
13. Ross, S. (2010) A First Course in Probability, 8-th edition, Prentice Hall, Upper Saddle River, N.J.
14. Sagan, B. E. (1991) A maj statistic for set partitions, European J. Combin., 12, 69–79.
15. Shareshian, J. & Wachs, M. L. (2010) Eulerian quasisymmetric functions, Adv. Math., 225, 2921–2966.
16. Sloane, N. J. (2010) The On-line Encyclopedia of Integer Sequences, http://oeis.org.
17. Stanton, D. & White, D. (1986) Constructive Combinatorics, Springer, New York.
18. Wachs, M. & White, D. (1991) p; q-Stirling numbers and set partition statistics, J. Combin. Theory Ser. A, 6, 27–46.
19. Wagner, C. G. (1996) Generalized Stirling and Lah numbers, Discrete Math., 160, 199–218.