Counting Partitions by Genus: a Compendium of Results

Robert Coquereaux

Aix Marseille Univ, Université de Toulon, CNRS, CPT, Marseille, France

                  robert.coquereaux@gmail.com

Jean-Bernard Zuber

Sorbonne Université, CNRS, Laboratoire de Physique Théorique et Hautes

Energies, LPTHE, F-75252 Paris, France

                    zuber@lpthe.jussieu.fr

Abstract

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.

1 Introduction

This is the second paper in a series devoted to the combinatorics of set partitions and their enumeration according to their genus. In a previous paper [?], functional equations were written between generating functions (G.F.) of partitions, enabling one to count partitions in genus 0, 1 and 2. In the present paper, which is completely independent, our goal is different. We wish to collect as much data as possible on that combinatorics. Accordingly, our paper gathers classical and known results as well as new data, obtained by computer “brute force” calculations and a few exact new results. In many cases, these data suggest conjectures and extrapolations, that we mark with the sign =^{?} .

This endeavor has benefited in a tremendous way from the existence of the On-Line Encyclopedia of Integer Sequences [?]. Several unexpected connections and identifications have been made possible thanks to this irreplaceable and unique source.

Our paper is organized as follows. In Section 2, we recall some basic definitions: total numbers of partitions are given by Bell numbers, and by Stirling numbers when the number of parts is fixed. The key notion of genus is also recalled. In Section ??, the Bell numbers are refined by fixing the genus of partitions, and by including partitions with or without singletons. Explicit expressions for their G.F. are given in genus 0 to 2, conjectured in genus 3, and the general form is discussed in higher genus. The same steps are repeated in Section ?? for the Stirling numbers, with again exact or conjectured results for their counting and G.F. The rest of the paper is devoted to the counting of partitions of given cyclic type. In Section ??, we review three families of partitions for which this counting is generically known: the famous non-crossing partitions (i.e., of genus 0); the partitions of genus 1 and 2, [?]; the partitions into pairs, i.e., of type [2^{k}], and arbitrary genus; and the partitions into two parts, for which we obtain a result in arbitrary genus, which is new, to the best of our knowledge. Section ?? gathers data on various types of partitions for which we have only partial results and conjectures: types [p^{k}] for varying p or k and three-part partitions. Finally Tables in Appendix contain the numbers of partitions of the set {1, …, n} of arbitrary genus up to n = 15.

To put the present work in perspective, let us recall some background. For a long time, the census of partitions according to their genus has been confined to two particular cases.

On the one hand, non-crossing partitions, i.e., of genus 0 in the current approach, and of arbitrary type, have been enumerated by Kreweras [?]. His result reappeared in the context of large size matrix integrals and their “planar” limit [?]: there, connected correlation functions (also known as cumulants) were in one-to-one correspondence with non-crossing partitions. The generating function of the latter was shown to satisfy a remarkably simple functional equation, from which Kreweras result followed by use of Lagrange inversion formula. That functional equation in turn received a simple diagrammatic interpretation by Cvitanovic [?]. Non-crossing cumulants associated with non-crossing partitions then appeared in the framework of free probability in the work of Speicher [?].

On the other hand, and in a totally independent vein, the special class of partitions of a set of even cardinality into pairs and of arbitrary genus was treated by Walsh and Lehman [?], and then by Harer-Zagier. See more references in Section ??. It is only recently that general partitions of higher genus were reconsidered by Cori and Hetyei [?, ?], and results on the counting of partitions with a given number of parts and genus 1 and 2 were obtained. Their method relies on a reduction of diagrams to simpler “irreducible” ones, with the same genus, which they proved to be in finite number for given genus. They were able to list these irreducible diagrams for genus 1 and 2. This enabled them to determine the G.F. of partitions with a given number of parts, for genus 1 and 2. See (??)-(??). This method was pushed one step further in [?], using the same reduction to irreducible diagrams, followed by a reconstruction of all partitions from those irreducible diagrams by use of functional identities generalizing Cvitanovic’s one in higher genus. That method is limited in genus by the increasing complexity in first listing all irreducible diagrams in genus greater or equal to 3 and then in “dressing” them.

As this short review shows, there is ample room for further progress and we hope the present work will stimulate the curiosity and imagination of some readers.

2 Bell, Stirling, and Faà di Bruno numbers

2.1 Equivalence relations on a set with n elements

Any equivalence relation on a set is specified by a partition α of this set (or set-partition, for short), and conversely, an equivalence relation defines a partition.

The number of equivalence relations on a set with n elements is given by the Bell numbers, which obey the recurrence:

B_{n+1} = ∑_{p=0}^{n} \binom{n}{p}B_{p}, with B_{1} = 1 ,  (1)

hence

B_{n} = \frac{1}{e} ∑_{ℓ=0}^{∞} \frac{ℓ^{n}}{ℓ!} ,  OEIS sequence \underline{A000110} .  (2)

The exponential generating function of the Bell numbers is

B(x) = ∑_{n=0}^{∞} \frac{B_{n}}{n!} x^{n} = e^{e^{x}−1}.  (3)

2.2 Equivalence relations on a set with n elements, with k equivalence classes

One may impose that the equivalence relations have a given number, say k, of equivalence classes, i.e., that the partition has k parts.

The number of such relations is given by the Stirling number of the second kind, S_{n,k}, which obeys the recurrence relation:

S_{n,k} = k S_{n−1,k} + S_{n−1,k−1}, n > 1, with S_{1,k} = 0, k > 1, and S_{1,1} = 1 .  (4)

Explicit form

S_{n,k} = \frac{1}{k!} ∑_{s=0}^{k}(−1)^{k−s}\binom{k}{s} s^{n} ,  OEIS sequence \underline{A008277} .  (5)

The exponential generating function of the Stirling numbers S_{n,k} is

S(x, y) = e^{y (e^{x}−1)}  (6)

with the following “sum rule” expressing their sum over k as a Bell number

B_{n} = ∑_{k=0}^{n} S_{n,k} .  (7)