Counting partitions by genus: a compendium of results. (English) Zbl 1533.05025
Summary: We study the enumeration of set partitions, according to their length, number of parts, cyclic type, and genus. We introduce genus-dependent Bell, Stirling numbers, and Faà di Bruno coefficients. Besides attempting to summarize what is already known on the subject, we obtain new generic results (in particular for partitions into two parts, for arbitrary genus), and present computer generated new data extending the number of terms known for sequences or families of such coefficients; this also leads to new conjectures.
MSC:
| 05A18 | Partitions of sets |
| 05A15 | Exact enumeration problems, generating functions |
| 15B52 | Random matrices (algebraic aspects) |
| 11B73 | Bell and Stirling numbers |
Software:
OEISOnline Encyclopedia of Integer Sequences:
Number of genus 2 rooted maps with 1 face with n vertices.Table read by rows. Number of set partitions of [n] with respect to genus g.
Triangle read by rows: T(n, k) is the number of partitions of genus 1 and k parts of the n-set (n >= 4, 2 <= k <= n-2).
Number of genus 1 partitions of the set [3n] into n blocks of length 3.
Number of genus 2 partitions of the set [3n] into n blocks of length 3.
References:
| [1] | É. Brézin, C. Itzykson, G. Parisi, and J.-B. Zuber, Planar diagrams, Comm. Math. Phys. 59 (1978) 35-51. · Zbl 0997.81548 |
| [2] | J. B. Caicedo, V. H. Moll, J. L. Ramirez, and D. Villamizar, Extensions of set partitions and permutations, Electron. J. Combin. 25 (2019), #P2.20. · Zbl 1439.11079 |
| [3] | G. Chapuy, Combinatoire bijective des cartes de genre supérieur, PhD thesis, École Polytechnique, France, 2009. Available at https://pastel.archives-ouvertes.fr/ pastel-00005289v1. |
| [4] | R. X. F. Chen and C. M. Reidys, Narayana polynomials and some generalizations, arxiv preprint arXiv:1411.2530, 2014. Available at http://arxiv.org/abs/1411.2530. |
| [5] | R. Cori and G. Hetyei, Counting genus one partitions and permutations, Sém. Lothar. Combin. 70 (2013), B70e. Available at http://arxiv.org/abs/1306.4628. · Zbl 1297.05026 |
| [6] | R. Cori and G. Hetyei, Counting partitions of a fixed genus, Electron. J. Combin. 25 (4) (2018), #P4.26. · Zbl 1402.05101 |
| [7] | P. Cvitanovic, Planar perturbation expansion, Phys. Lett. B 99 (1981) 49-52. |
| [8] | A. Goupil and G. Schaeffer, Factoring N -cycles and counting maps of given genus, European J. Comb. 19 (1998) 819-834. · Zbl 0915.05007 |
| [9] | R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd ed., Addison-Wesley, 1994. · Zbl 0836.00001 |
| [10] | J. Harer and D. Zagier, The Euler characteristic of the moduli space of curves, Invent. Math. 85 (1986) 457-485. · Zbl 0616.14017 |
| [11] | A. Hock, Genus permutations and genus partitions, arxiv preprint arXiv:2306.16237, 2023. Available at http://arxiv.org/abs/2306.16237. |
| [12] | G. ’t Hooft, A planar diagram theory for strong interactions, Nucl. Phys. B 72 (1974) 461-473. |
| [13] | D. M. Jackson, Counting cycles in permutations by group characters, with an application to a topological problem, Trans. Amer. Math. Soc. 299 (1987) 785-801. · Zbl 0655.05005 |
| [14] | A. Jacques, Sur le genre d’une paire de substitutions, C. R. Acad. Sci. Paris 267 (1968) 625-627. · Zbl 0187.20902 |
| [15] | G. Kreweras, Sur les partitions non croisées d’un cycle, Discrete Math. 1 (1972) 333-350. · Zbl 0231.05014 |
| [16] | S. K. Lando and A. K. Zvonkin, Graphs on Surfaces and Their Applications, Encycl. of Math. Sci. 141, Springer, 2004. · Zbl 1040.05001 |
| [17] | N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2024. Available at https://oeis.org. |
| [18] | R. Speicher, Multiplicative functions on the lattice of non-crossing partitions and free convolution, Math. Ann. 298 (1994) 611-628. · Zbl 0791.06010 |
| [19] | T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus I, J. Combin. Theory Ser. B 13 (1972) 192-218. · Zbl 0228.05108 |
| [20] | T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus II, J. Combin. Theory Ser. B 13 (1972) 122-141. · Zbl 0228.05109 |
| [21] | M. Yip, Genus one partitions, PhD thesis, University of Waterloo, 2006. Available at https://uwspace.uwaterloo.ca/handle/10012/2933. |
| [22] | J.-B. Zuber, Counting partitions by genus. I. Genus 0 to 2, Enumer. Comb. Appl. 4 (2) (2024) #S2R13. Available at https://doi.org/10.54550/ECA2024V4S2R13 and http://arxiv.org/abs/2303.05875. · doi:10.54550/ECA2024V4S2R13 |
| [23] | 2020 Mathematics Subject Classification: Primary 05A18; Secondary 05A15, 15B52. Keywords: set-partition, genus-dependent enumeration. (Concerned with sequences A000108, A000110, A000292, A000296, A000581, A001263, A001287, A001700, A002411, A002450, A002802, A005043, A008277, A008299, A025035, A025036, A025037, A025038, A025039, A035319, A059260, A103371, A108263, A134991, A144431, A185259, A245551, A275514, A297178, A297179, and A340556.) |
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.
