Sorbonne Université, UMR 7589, LPTHE, F-75005, Paris, France
& CNRS, UMR 7589, LPTHE, F-75005, Paris, France
<EMAIL_ADDRESS>

The counting of partitions according to their genus is revisited. The case of
genus 0 –non-crossing partitions– is well known. Our approach relies on two
pillars : first a functional equation between generating functions, originally
written in genus 0 and interpreted graphically by Cvitanovic, is generalized
to higher genus; secondly, we show that all partitions may be reconstructed
from the “(semi)-primitive” ones introduced by Cori and Hetyei. Explicit
results for the generating functions of all types of partitions are obtained
in genus 1 and 2. This gives a second order interpolation between expansions
on ordinary or on free cumulants.

##  1 Introduction

###  1.1 Genus interpolation between usual and free cumulant expansions

Set partitions, say of the set $[\\![n]\\!]:=\\{1,2\cdots,n\\}$, are
fundamental objects in combinatorics. Let ${\mathcal{P}}(n)$ denote their set.
Their census, subject to different conditions, has been and is still the
subject of an abundant literature. In particular, it is well known, as we
recall below in sect. 2.2, that any partition $\alpha$ may be assigned a genus
$g(\alpha)$ by a formula descending from Euler’s relation. Curiously, the
census of partitions according to their genus is still an open problem, in
spite of several fundamental contributions, [12, 16, 17, 3, 4]. Except for a
few particular cases, only the case of genus 0 is thoroughly known: the non
crossing partitions (or planar) have been enumerated by Kreweras [12], before
reappearing in various contexts, matrix integrals [1], free probability [15,
14]…

The question also arises in probability theory and statistical mechanics.
There, it is common practice to associate cumulants to moments of random
variables. If $X$ is a random variable with moments $m_{n}=\mathbb{E}(X^{n})$
of arbitrary order, we decompose these moments on cumulants $\kappa_{m}$ and
their products associated with partitions $\alpha\in{\mathcal{P}}(n)$

$m_{n}=\sum_{\alpha\in{\mathcal{P}}(n)}\kappa_{\alpha}\,.$ (1)

Thus each term in (1) may be regarded as associated with a splitting of
$[\\![n]\\!]$ into parts described by the partition in statistical mechanics,
the terms $\kappa_{\alpha}$ are dubbed the connected parts of the moment
$m_{n}$.

If $\alpha_{\ell}$ denotes the number of parts of cardinality $\ell$ in the
partition $\alpha$, with $\sum_{\ell=1}^{n}\ell\alpha_{\ell}=n$, then 111I’m
assuming here that the moments and cumulants do not depend on extra variables
like momenta, etc.

$\kappa_{\alpha}:=\prod_{\ell=1}^{n}\kappa_{\ell}^{\alpha_{\ell}}\,.$ (2)

depends only on the type $[\alpha]=[1^{\alpha_{1}}2^{\alpha_{2}}\cdots
n^{\alpha_{n}}]$ of the partition $\alpha$; $[\alpha]$ may be regarded as a
partition of the integer $n$. By a small abuse of notation, we use the same
letter $\kappa$ to denote elementary cumulants $\kappa_{\ell}$,
$\ell\in\mathbb{N}$; compound ones $\kappa_{\alpha}$,
$\alpha\in{\mathcal{P}}(n)$ as in (2); or $\kappa_{[\alpha]}=\kappa_{\alpha}$,
$[\alpha]\vdash n$, and we rewrite

$m_{n}=\sum_{[\alpha]\vdash n}c_{n,[\alpha]}\kappa_{[\alpha]}\,$ (3)

where $c_{n,[\alpha]}$ denotes the number of partitions of type $[\alpha]$ (a
coefficient of a Bell polynomial)

$c_{n,[\alpha]}=\frac{n!}{\prod_{\ell=1}^{n}\alpha_{\ell}!(\ell!)^{\alpha_{\ell}}}\,.$
(4)

Then, making use of the genus $g(\alpha)$ mentioned above, it is natural to
modify the expansion (3) by weighting the various terms acccording to their
genus. Introducing a parameter $\epsilon$, we write

$m_{n}(\epsilon)=\sum_{\alpha\in{\mathcal{P}}(n)}\epsilon^{g(\alpha)}\kappa_{\alpha}$
(5)

or

$m_{n}(\epsilon)=\sum_{[\alpha]\vdash
n}\sum_{g=0}^{g_{{\mathrm{m}ax}}([\alpha])}C^{(g)}_{n,[\alpha]}\epsilon^{g}\kappa_{[\alpha]}\\\
,$ (6)

where $C^{(g)}_{n,[\alpha]}$ counts the number of partitions of type
$[\alpha]$ and of genus $g$.
For example,
$m_{4}(\epsilon)=\kappa_{4}+4\,\kappa_{3}\,\kappa_{1}+(2+\epsilon)\kappa_{2}^{2}+6\,\kappa_{2}\,{\kappa_{1}}^{2}+{\kappa_{1}}^{4}\,,$
see below.

Obviously $\sum_{g}C^{(g)}_{n,[\alpha]}=c_{n,[\alpha]}$, the coefficient in
(4), thus for $\epsilon=1$, we recover the usual expansion (3), whereas for
$\epsilon=0$, we have an expansion on non crossing (or free, or planar)
cumulants. Thus (6) provides an interpolation between the usual cumulant
expansion and that on non crossing ones.

In this paper, we try to determine the numbers $C^{(g)}_{n,[\alpha]}$. Or
alternatively, we strive to find relations between the (ordinary) generating
functions (GF) of the $m_{n}(\epsilon)$ and of the $\kappa_{\ell}$:

$\displaystyle Z(x,\epsilon)$ $\displaystyle=$ $\displaystyle 1+\sum_{n\geq
1}m_{n}(\epsilon)x^{n}$ $\displaystyle=$ $\displaystyle\sum_{g\geq
0}Z^{(g)}(x)\epsilon^{g}$ $\displaystyle W(x)$ $\displaystyle=$
$\displaystyle\sum_{\ell\geq 1}\kappa_{\ell}x^{\ell}\,.$ (8)

This will be achieved for genus 1 and 2, and the corresponding expressions of
$Z^{(g)}(x)$ are given by Theorem 1, (28), and Theorem 2, (45). Extension to
higher genera is in principle feasible, if the list of their primitive
diagrams is known.

###  1.2 Eliminating or reinserting singletons

In a partition, parts of size 1 are called singletons. It is natural and easy
to remove them in the counting, or to relate the countings of partitions with
or without singletons. Let us denote with a hat the GF of partitions without
singletons: $\hat{Z}^{(g)}(x)$, and derive the relation between
$\hat{Z}^{(g)}(x)$ and $Z^{(g)}(x)$. This is particularly easy in the language
of statistics, where discarding singletons amounts to going to a centered
variable: $X=\hat{X}+\mathbb{E}(X)=\hat{X}+m_{1}=\hat{X}+\kappa_{1}$

$m_{n}=\mathbb{E}(X^{n})=\mathbb{E}((\hat{X}+\kappa_{1})^{n})=\sum_{r=0}^{n}{n\choose
r}\,\hat{m}_{n-r}\,\kappa_{1}^{k}$

and, since singletons do not affect the genus, see below sect. 2.6,

$C^{(g)}_{n,[\alpha^{\prime},1^{r}]}={n\choose
r}C^{(g)}_{n-r,[\alpha^{\prime}]}\,$ (9)

where the partition $\alpha^{\prime}$ is singleton free (s.f.). For example,

$\displaystyle\hskip-56.9055ptm_{1}\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!\kappa_{1}$ $\displaystyle m_{2}\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!\kappa_{2}+\kappa_{1}^{2}$ $\displaystyle m_{3}\\!\\!$
$\displaystyle=$
$\displaystyle\\!\\!\kappa_{3}+3\kappa_{2}\kappa_{1}+\kappa_{1}^{3}$
$\displaystyle m_{4}\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!\kappa_{4}+(2+\epsilon)\kappa_{2}^{2}+4\kappa_{3}\kappa_{1}+6\kappa_{2}\kappa_{1}^{2}+\kappa_{1}^{4}$
$\displaystyle m_{5}\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!{\kappa_{5}+5\,\kappa_{4}\,\kappa_{1}+5(1+\epsilon)\kappa_{3}\kappa_{2}+10\,\kappa_{3}\,{\kappa_{1}}^{2}+5(2+\epsilon)\,{\kappa_{2}}^{2}\kappa_{1}+10\,\kappa_{2}\,{\kappa_{1}}^{3}+{\kappa_{1}}^{5}\,,}$

etc.

Then

$\displaystyle Z^{(g)}(x)$ $\displaystyle=$ $\displaystyle\sum_{n\geq
0}x^{n}\sum_{[\alpha]\atop\alpha\in{\mathcal{P}}(n)}C^{(g)}_{n,[\alpha]}\kappa_{[\alpha]}$
(10) $\displaystyle=$ $\displaystyle\sum_{n\geq
0}x^{n}\sum_{r=0}^{n}\sum_{[\alpha^{\prime}]\atop\alpha^{\prime}\in{\mathcal{P}}(n-r),\,\mathrm{s.f.}}C^{(g)}_{n,[1^{r},\alpha^{\prime}]}\kappa_{[\alpha^{\prime}]}\kappa_{1}^{r}$
$\displaystyle=$ $\displaystyle\sum_{n^{\prime}\geq
0}x^{n^{\prime}}\sum_{[\alpha^{\prime}]\atop\alpha^{\prime}\in{\mathcal{P}}(n^{\prime}),\,\mathrm{s.f.}}C^{(g)}_{n^{\prime},[\alpha^{\prime}]}\kappa_{[\alpha^{\prime}]}\sum_{r\geq
0}{n^{\prime}+r\choose r}\kappa_{1}^{r}x^{r}$ $\displaystyle=$
$\displaystyle\sum_{n^{\prime}\geq
0}\sum_{[\alpha^{\prime}]\atop\alpha^{\prime}\in{\mathcal{P}}(n^{\prime}),\,\mathrm{s.f.}}C^{(g)}_{n^{\prime},[\alpha^{\prime}]}\kappa_{[\alpha^{\prime}]}\frac{x^{n^{\prime}}}{(1-\kappa_{1}x)^{n^{\prime}+1}}$
$\displaystyle=$
$\displaystyle\frac{1}{1-\kappa_{1}x}\,\hat{Z}^{(g)}\big{(}\frac{x}{1-\kappa_{1}x}\big{)}\,,$

and conversely

$\hat{Z}^{(g)}(u)=\frac{1}{1+\kappa_{1}u}\,Z^{(g)}\big{(}\frac{u}{1+\kappa_{1}u}\big{)}\,.$
(11)

##  2 Partitions and their genus

In this section, we recall some standard notions on partitions, show how to
associate a graphical representation to a partition and introduce its genus in
a natural way.

###  2.1 Parts of a partition

As explained in sect. 1, we are interested in partitions of the set
$[\\![n]\\!]$.
Note that when listing the parts of a partition
$\alpha=(\\{i_{1}\\},\cdots\\{i_{\alpha_{1}}\\},\\{j_{1},j_{2}\\}.\cdots)$,
(i) the ordering of elements in each part is immaterial, and we thus choose to
write them in increasing order;
(ii) the relative position of parts is immaterial.

For example, consider the partition
$(\\{1,3,4,6,7\\},\\{2,5,9\\},\\{8\\},\\{10\\})$ of $[\\![10]\\!]$. It is of
type $[1^{2},3,5]$ with two singletons $\\{8\\}$ and $\\{10\\}$. Clearly the
order of elements within each part is irrelevant, e.g. parts $\\{1,3,4,6,7\\}$
and $\\{3,4,1,7,6\\}$ describe the same subset of $[\\![10]\\!]$. One may thus
order the elements of each part. Likewise the relative order of the parts is
immaterial:
$(\\{1,3,4,6,7\\},\\{2,5,9\\},\\{8\\},\\{10\\})$ and
$(\\{2,5,9\\},\\{8\\},\\{1,3,4,6,7\\},\\{10\\})$ describe the same partition.

Figure 1: The partition $(\\{1,3,4,6,7\\},\\{2,5,9\\},\\{8\\},\\{10\\})$ of
$[\\![10]\\!]$. (a) and (b): two equivalent representations of the 10-vertex;
(c) the four other vertices; (d) a contribution to
$C^{(g)}_{10,[1^{2}\,3\,5]}$; (e) the double line version of (d), with three
faces and thus genus $g=$ 2; (f) the linear version of (d).

###  2.2 Combinatorial and graphical representations of a partition and its
genus

A general partition $\alpha$ of ${\mathcal{P}}(n)$ may be described in terms
of a pair of permutations $\sigma$ and $\tau$, both in $\mathcal{S}_{n}$:
$\sigma$ is the cyclic permutation $(1,2,\cdots,n)$; $\tau$ belongs to the
class $[\alpha]$ of $\mathcal{S}_{n}$, and its cycles are described by the
parts of $\alpha$, thus subject to the condition (i) above: each cycle is an
increasing list of integers.
The genus $g$ of the partition is then defined by [10]

$n+2-2g=\\#\mathrm{cy}(\tau)+\\#\mathrm{cy}(\sigma)+\\#\mathrm{cy}(\sigma\circ\tau^{-1})\,$
(12)

or in the present case,

$-2g=\sum\alpha_{\ell}-1-n+\\#\mathrm{cy}(\sigma\circ\tau^{-1})\,.$ (13)

since here $\\#\mathrm{cy}(\sigma)=1$ and
$\\#\mathrm{cy}(\tau)=\sum\alpha_{k}$. Since
$\\#\mathrm{cy}(\sigma\circ\tau^{-1})\geq 1$, we find an upper bound on $g$

$g\leq
g_{\mathrm{max}}:=\bigg{\lfloor}\frac{1}{2}(n-\sum\alpha_{k})\bigg{\rfloor}\,,$
(14)

see also [18]. We recall below why this definition of the genus is natural.
Example.
For the above partition of $[\\![10]\\!]$, $\sigma=(1,2,\cdots,10)$,
$\tau=(1,3,4,6,7)(2,5,9)(8)(10)$,
$\sigma\circ\tau^{-1}=(1,8,9,6,5,3,2,10)(4)(7)$. Thus $2g=11-4-3=4$, $g=2$,
while $g_{\mathrm{max}}=3$.

To a given partition, we may also attach a map: it has $\alpha_{\ell}$
$\ell$-valent vertices, in short $\ell$-vertices 222Remember that
$\alpha_{\ell}$ are the multiplicities introduced in (2), for
$\ell=1,2,\cdots$, whose edges are numbered clockwise by the elements of the
partition, and a special $n$-valent vertex, with its $n$ edges numbered anti-
clockwise from 1 to $n$, see Fig. 1a,c. Edges are connected pairwise by
matching their indices. Two maps are regarded as topologically equivalent if
they encode the same partition. In fact it is topologically equivalent and
more handy to attach $n$ points clockwise on a circle, and to connect them
pairwise by arcs of the circle, see Fig. 1b. Now the permutation $\sigma$
describes the connectivity of the $n$ points on the circle, while $\tau$
describes how these points are connected through the other vertices. It is
readily seen that the permutation $\sigma\circ\tau^{-1}$ describes the
circuits bounding clockwise the faces of the map. This is even more clearly
seen if one adopts a double line notation for each edge [9], thus transforming
the map into a “fat graph”, see Fig. 1e . Thus the number of cycles of
$\sigma\circ\tau^{-1}$ is the number $f$ of faces of the map. Since each face
is homeomorphic to a disk, gluing a disk to each face transforms the map into
a closed Riemann surface, to which we may apply Euler’s formula

$2-2g=\\#(\mathrm{vertices})-\\#(\mathrm{edges})+\\#(\mathrm{faces})=1+\sum_{\ell}\alpha_{\ell}-n+f$
(15)

with $f=\\#\mathrm{cy}(\sigma\circ\tau^{-1})$, and we have reproduced (13).

Remark 1. This coding of a map, or here of a partition, by a pair of
permutations, with a resulting expression of its genus, is an old idea
originating in the work of Jacques, Walsh and Lehman [10, 16, 17] and
rediscovered and used with variants by many authors since then [6].

Remark 2. The diagrammatic representation that we adopt here differs from that
of other authors [18, 4]: in fact it is the dual picture, with our vertices
corresponding to faces of these authors. Our preference for the former is due
to its analogy with Feynman diagrams…

###  2.3 Glossary

It may be useful to list some elements of terminology used below.
It is convenient to represent a partition of ${\mathcal{P}}(n)$ by a diagram.
It may be a circular diagram, with $n$ points equidistributed clockwise, as on
Fig. 1-d, and it has a genus as explained above. We distinguish the points on
the circle from the vertices which lie inside the disk.
Occasionally we use a linear diagram, with $n$ points labelled from 1 to $n$
on a line (or an arc), and vertices above the line.
Note that if we give each point of the circle a weight $x$ and each $k$-vertex
the weight $\kappa_{k}$, the sum of diagrams of genus $g$ builds the GF
$Z^{(g)}(x)$.
In a (circular) diagram, we call 2-line a pair of edges attached to a
2-vertex. In the following, the middle 2-vertex will be omitted on 2-lines, to
avoid overloading the figures. A 2-line is then just a straight line between
two points of the circle.
In a diagram, we call adjacent a pair of edges joining a vertex to adjacent
points on the circle. For example, on Fig. 2, the edges ending at 1 and 3 are
not adjacent, those ending at 3 and 4 are.
In the following discussion, it will be important to focus on a point on the
circle, say point 1, and see what it is connected to. We shall refer to it as
the marked point.
If $\alpha$ is a partition of ${\mathcal{P}}(n)$ of a given type, all its
conjugates by powers of the cyclic permutation $\sigma$ have the same type.
Counting partitions of a given type thus amounts to counting orbits of
diagrams under the action of $\sigma$, while recording the length
(cardinality) of each orbit. Diagrammatically, the point 1 being marked, we
list orbits under rotations of the inner pattern of vertices and edges by the
cyclic group $\mathbb{Z}_{n}$, and record the length of each orbit. An orbit
has a weight equal to its length $n/{\mathfrak{s}}$, where ${\mathfrak{s}}$ is
the order of the stabilizer of the diagram – a subgroup of the rotation group.
For example, the left-most diagram of Fig. 8 has ${\mathfrak{s}}=2$, the
right-most ${\mathfrak{s}}=8$, the others have ${\mathfrak{s}}=1$.

###  2.4 The coefficients $C_{n,[\alpha]}^{(g)}$

We now return to our problem of determining the coefficients
$C_{n,[\alpha]}^{(g)}$ in (6). From the previous discussion, if we denote
${\mathcal{O}}_{n}([\alpha])\subset{\mathcal{S}}_{n}$ the subset of
permutations of class $[\alpha]$, whose cycles involve only increasing
sequences of integers, we have

$C_{n,[\alpha]}^{(g)}=\\#\left\\{\tau\big{|}\tau\in{\mathcal{O}}_{n}([\alpha]),\
g=\frac{1}{2}\Big{(}n+1-\sum\alpha_{\ell}-\\#\mathrm{cy}(\sigma\circ\tau)\Big{)}\right\\}\,.$
(16)

Alternatively, one may use the diagrammatic language to write

$C_{n,[\alpha]}^{(g)}=\sum_{\mathrm{orbits}}\mathrm{length\ of\
orbit}=n\sum_{\mathrm{orbits}}\frac{1}{{\mathfrak{s}}}\,,$ (17)

with a sum over orbits of diagrams of type $[\alpha]$ and genus $g$.

###  2.5 Remark on matrix integrals

As ’t Hooft’s double line notation [9] suggests, the coefficient

$C_{n,[\alpha]}(\epsilon)=\sum_{g}C_{n,[\alpha]}^{(g)}\epsilon^{g}$ (18)

could be defined and computed in matrix integrals
– (i) as the coefficient of $\prod_{\ell}\kappa_{\ell}^{\alpha_{\ell}}$ in the
computation of $\langle\frac{1}{N}:{\rm tr}\,M^{n}:\rangle_{rc}$ in a matrix
theory with action $S=-\frac{1}{2}N{\rm
tr}\,M^{2}+N\sum_{\ell}\kappa_{\ell}\,{\rm tr}\,M^{\ell}/\ell$; the notation
$:\ :$ and the subscript “rc” will be explained shortly;
– (ii) as the value of $\langle:\frac{1}{N}{\rm
tr}\,M^{n}:\,:\prod_{\ell}\frac{(N{\rm
tr}\,M^{\ell}/\ell)^{\alpha_{\ell}}}{\alpha_{\ell}!}:\rangle_{rc}$ in a
Gaussian matrix theory.
In both cases, $\epsilon=\frac{1}{N^{2}}$, if $N$ is the size of the
(Hermitian) matrices; $C_{n,[\alpha]}(N^{-2})$ is given by a sum of Feynman
diagrams (in fact, of “fat graphs”, or of maps) with
$1+\sum_{\ell}\alpha_{\ell}$ vertices, $n$ edges (“propagators”) joining the
$n$-vertex ${\rm tr}\,M^{n}$ to the other $\ell$-vertices, and $f$ faces
associated with each closed index circuit. The double dots $:\ :$ is a
standard notation in quantum field theory, where it denotes the normal or Wick
product, that forbids edges from a vertex to itself: here it forces all edges
to reach the $n$-vertex. The crucial point is that we impose a restricted
crossing (“rc”) condition: the edges connecting each $\ell$-vertex to the
$n$-vertex cannot cross one another, thus respecting their original cyclicity
and ordering. Only crossings of edges emanating from distinct vertices are
allowed.

It is that constraint, a direct consequence of rule 2.1 (i) above, that makes
the computation of the coefficients $C_{n,[\alpha]}^{(g)}$ by matrix integrals
or group theoretical techniques, , and the writing of recursion formulae
between them, quite non trivial. For partitions into doublets, however, one
deals only with 2-vertices for which the constraint is irrelevant, and
$C_{n=2p,[2^{p}]}^{(g)}$ is computable by these techniques [16, 8, 13].

Figure 2: (a) Diagram for the partition of $[\\![10]\\!]$ into
$(\\{1,3,4,6,7\\},\\{2,5\\},\\{8,9,10\\})$, $f=6$ hence genus
$g=1-(3+1-10+6)/2=1$; (b) after removal of the three adjacent edges coming
from the “centipede” $\\{8,9,10\\}$, here a 3-vertex, now $n^{\prime}=7$,
$f^{\prime}=4$, $g^{\prime}=1$; (c) after reduction of two sets of adjacent
edges to points 3 and 4, and 6, 7 and 1: now $n^{\prime\prime}=4$,
$f^{\prime\prime}=1$, $g^{\prime\prime}=1+(2+1-4+1)/2=1$.  Figure 3: Removing
the blue parallel pair of edges and the light blue face does not affect the
genus: Variations $\Delta n=-2$, $\Delta f=-1$, $\Delta\sum\alpha_{k}=-1$,
hence $\Delta g=0$.

###  2.6 Reducing the diagrams

In this subsection, we show that certain modifications of a diagram associated
with a partition do not modify its genus. This discussion follows closely that
of Cori and Hetyei [4].
(i) Removing singletons.
Removing $p$ singletons changes the number of parts $\sum\alpha_{k}$ by $-p$,
$n$ by $-p$ and the number of faces $f$ is unchanged, hence according to (15)
the genus remains unchanged.
(ii) Removing centipedes.
Definition. A centipede is a planar linear subdiagram made of a $p$-vertex,
all the edges of which are attached in a consecutive way to the outer circle,
Fig. 2. In other words, it corresponds to a part of the partition with
consecutive integers (modulo $n$), $\\{j,j+1,\cdots,j+p\\}$ . Removing it
changes the number of parts $\sum\alpha_{k}$ by $-1$, $n$ by $-p$ and the
number of faces $f$ by $-(p-1)$, see the figure, hence the genus remains
unchanged.
(iii) Removing adjacent edges
If two edges emanating from a vertex go to two consecutive points of the
circle, (adjacent pair), see Fig 2b-c, removing one of them does not change
$\sum\alpha_{k}$ but changes $n$ and $f$ by $-1$, hence does not change the
genus. One may iterate this operation on the same vertex until one meets a
crossing with an edge emanating from another vertex. (If no crossing occurs,
this means that the vertex and its edges formed a centipede in the sense of
(ii) and may be erased without changing the genus.) To allow an unambiguous
reconstruction of all diagrams later in the dressing process, we adopt the
following
Convention 1: in removing such adjacent edges, one keeps the edge attached to
the marked point 1, or the first edge encountered clockwise starting from 1,
and one removes the others.
See Fig. 2 for illustration.
(iv) Removing parallel lines
Definition. Two pairs of edges joining two vertices respectively to points $i$
and $j+1$, and to points $i+1$ and $j$ on the circle are said to be parallel.
Note that this is equivalent to saying that they form a 2-cycle of the
permutation $\sigma\circ\tau^{-1}$. And conversely, any such 2-cycle is
associated with two parallel pairs of edges.
(a) If one of these two vertices is a 2-vertex, one may remove the
corresponding pair of edges and the 2-vertex without changing the genus, since
$\sum\alpha_{\ell}$ and $f$ have decreased by 1 and $n$ by 2, see Fig. 3 for
illustration. If both pairs of edges are attached to 2-vertices, we choose by
Convention 2 to keep the pair attached to the point of the circle of smallest
label. In particular, if one of the pairs is attached to the marked point 1,
it is kept and the other removed.
(b) If both pairs of edges are attached to vertices of valency larger that 2,
we keep them both. See Fig. 13 below for an example.
After carrying these removals of parallel lines, we are left with primitive or
semi-primitive diagrams (or partitions), following Cori–Hetyei’s terminology:
in primitive diagrams, no parallel pair is left; therefore, by the remark
above, all cycles of $\sigma\circ\tau^{-1}$ have length larger than 2. Semi-
primitive diagrams still have parallel pairs of type (b).

Now Cori and Hetyei have proved some fundamental results:
Proposition. To an arbitrary diagram corresponds a unique primitive (or semi-
primitive) diagram obtained by a sequence of reductions as above, and
independent of the order of these reductions.
Our new observation is that, conversely, any diagram may be recovered by
“dressing” a primitive (or semi-primitive) diagram, as we shall see below.

Moreover,
Proposition. [4] For a given genus, there are only a finite number of
primitive diagrams.
This follows from two inequalities:
$f=\\#\mathrm{cy}(\sigma\circ\tau^{-1})\leq\frac{n}{3}$, since in a primitive
diagram all cycles of $\sigma\circ\tau^{-1}$ are of length larger or equal to
three (see above); and $\sum\alpha_{i}\leq n/2$ after eliminating the
singletons. Hence plugging these inequalities in (13), we get for a primitive
diagram

$n\leq 6(2g-1)\,.$ (19)

As for the semi-primitive diagrams, it was shown in [4] that they are all
obtained by a finite number of operations from the primitive ones, hence are
themselves in finite number.

For example
Proposition[4] The irreducible diagrams of genus 1 are the two diagrams of
Fig. 4, that have two, resp. three 2-lines. No semi-primitive occurs in genus
1.
The proof of that statement is given in [4], sect. 8, where the two primitive
partitions or diagrams are referred to as $\beta_{1}$ and $\beta_{2}$.

##  3 From genus 0 to genus 1 …

Figure 4: The two “primitive” diagrams of genus 1. The blue figure in the
middle is the weight of the diagram in (16), namely the length of its orbit.

###  3.1 Non crossing partitions and the genus 0 generating function

Recall first that in genus 0, the formula given by Kreweras [12] on the census
of non crossing partitions may be conveniently encoded in the following
functional relation between the genus 0 GF of moments $Z^{(0)}(x)$ and that of
cumulants $W(x)$ defined above 333 Recall this relation is equivalent to the
functional identity $P\circ G=\mathrm{id}$, where
$G(u):=u^{-1}Z^{(0)}(u^{-1})$ and $P(z):=z^{-1}W(z)$, and
$R(z)=P(z)-\frac{1}{z}$ is the celebrated Voiculescu $R$ function [15, 14].

$Z^{(0)}(x)=1+W(xZ^{(0)}(x))\,.$ (20)

Indeed by application of Lagrange formula, one recovers Kreweras’ result

$C^{(0)}_{n,[\alpha]}=\frac{n!}{(n+1-\sum\alpha_{k})!\
\prod_{k}\alpha_{k}!}\,,$ (21)

as proved in [1].

There is a simple diagrammatical interpretation of the relation (20) due to
Cvitanovic [5], see Fig. 5, which reads: in an arbitrary planar (i.e., non-
crossing) diagram, the marked point 1 on the exterior circle is necessarily
connected to a $n$-vertex, $n\geq 1$, between the $n$ edges of which lie
arbitrary insertions of other (linear) diagrams of $Z^{(0)}$.
Our aim is to extend this kind of relation to higher genus.

Figure 5:  A graphical representation of identity
$Z^{(0)}(j)=W(j\,Z^{(0)}(j))$ Figure 6: Top: A graphical representation of
identity (24). Bottom: a schematic representation of the dressing of the (red)
2-line attached to the marked point 1; or to another (blue) 2-line. In the
latter case, according to Convention 1, additional edges may be “emitted” from
the central vertex to go to clockwise adjacent points on the circle, and their
contribution to the generating function is $X_{2}(x)$. For the red line, these
additional edges may connect to either side of the marked point, and they
contribute $Y_{2}(x)$ to the GF.

###  3.2 Dressing the genus 1 primitive diagrams

We have seen that genus 1 diagrams may be reduced to the two primitive ones of
Fig. 4. We now write a relation à la Cvitanovic between the generating
functions $W$, $Z^{(0)}$ and $Z^{(1)}$, depicted in Fig. 6

$Z^{(1)}(x)=\sum_{n\geq 2}\kappa_{n}nx^{n}(Z^{(0)})^{n-1}Z^{(1)}+\mathrm{sum\
of\ dressed\ diagrams\ of\ Fig.\ \ref{Fig4}}\,,$ (22)

which reads: in a generic diagram of genus 1, the marked point 1 is attached
(a) either to an edge of an $n$-vertex, between the non-crossing edges of
which are inserted one (linear) subdiagram of genus 1 and $(n-1)$ subdiagrams
of genus 0 444Remember that by convention, $Z^{(0)}(x)$ starts with 1, hence
these subdiagrams of genus 0 may be trivial, (b) or to an edge of a dressed
primitive diagram of genus 1.

Let us concentrate on the case (b) and make explicit what is meant by
dressing.

The dressing consists in reinserting the elements removed in steps (iv)–(i) of
sect. 2.6, in that reverse order. First, additional 2-lines are introduced,
“parallel” to the two, resp. three 2-lines of the primitive diagrams of Fig.
4. Each of these 2-lines carries by definition a 2-vertex. Then to reinsert
“adjacent” edges removed in step (iii), each of these 2-vertices may be
transformed into a $k$-vertex, whose $k-2$ additional edges may fall, by
Convention 1, on either of the two arcs of the circle adjacent to the end
points of the 2-line and “clockwise downstream”, and without crossing one
another: there are $k-1$ partitions of $k-2$ into two parts, one of them
possibly empty, hence we attach a weight $X_{2}(x):=\sum_{k\geq
1}(k-1)\kappa_{k}x^{k}$ to each of these parallel lines. Since there is an
arbitrary number $r\geq 0$ of parallel lines, they contribute $X_{2}(x)^{r}$,
and their geometric series sums up to $1/(1-X_{2}(x))$. The same applies to
the original blue 2-lines of the primitive diagram of Fig. 6, which thus gives
each a factor $X_{2}(x)$. The red 2-line, which is the one attached to the
marked point 1,has a different weight, as the $k-2$ edges emanating from its
$k$ vertex may fall on either side of the marked point or on the rightmost
part of the diagram (see Convention 2 above): this is associated with a
partition of the $k-2$ edges into three parts (two of them possibly empty), in
number $k(k-1)/2$, which gives the red 2-line a weight
$Y_{2}(x)=\sum_{k}\frac{k(k-1)}{2}\kappa_{k}x^{k}$, while its dressing by
parallel lines leads to a factor $1/(1-X_{2}(x))^{2}$, because again, parallel
lines above or below the red 2-line are possible. Last step consists in
reinserting “centipedes” and (possibly) singletons, namely in changing
everywhere $x$ into $\tilde{x}=xZ^{(0)}(x)$.
In that way, we have reinstated all features that had been erased in the
reduction to primitive diagrams, and constructed the contribution to the GF
$Z^{(1)}(x)$ of all diagrams in which the marked point 1 is attached to an
edge that belongs to a dressed primitive diagram. Indeed in the resulting
diagrams, the marked point 1 may be attached to any of the edges, as it
should: this is clear whenever that edge is an edge of the primitive diagram;
this is also true if the edge is one of the parallel lines added, or one of
the added adjacent edges: that was the role of the factors in the definition
of $X_{2}$ or $Y_{2}$ to count these cases. It is thus clear that all possible
diagrams of type (b) contributing to $Z^{(1)}$ have been obtained by the
dressing procedure, and that they are generated once and only once, hence with
the right weight. Finally the cases (a) where 1 is not attached to a dressed
primitive, but to some genus 0 subdiagram, are accounted for by the first term
in equ.(22).

###  3.3 The genus 1 generating function

Define

$\tilde{x}=xZ^{(0)}(x)\,.$ (23)

Gathering all the contributions of sect. 3.2 we have

$Z^{(1)}(x)=\sum_{n\geq
2}\kappa_{n}nx^{n}(Z^{(0)}(x))^{n-1}Z^{(1)}(x)+\frac{Y_{2}(\tilde{x})X_{2}(\tilde{x})}{(1-X_{2}(\tilde{x}))^{3}}+\frac{Y_{2}(\tilde{x})X_{2}^{2}(\tilde{x})}{(1-X_{2}(\tilde{x}))^{4}}\,,$
(24)

i.e.,

$(1-V(x))Z^{(1)}(x)=\frac{Y_{2}(\tilde{x})X_{2}(\tilde{x})}{(1-X_{2}(\tilde{x}))^{4}}$

where

$\displaystyle X_{2}(x)$ $\displaystyle=$ $\displaystyle\sum_{k\geq
2}(k-1)\kappa_{k}x^{k}=xW^{\prime}(x)-W(x)\,,$ (25) $\displaystyle Y_{2}(x)$
$\displaystyle=$ $\displaystyle\sum_{k\geq
2}\frac{k(k-1)}{2}\kappa_{k}x^{k}=\frac{1}{2}x^{2}W^{\prime\prime}(x)$ (26)
$\displaystyle V(x)$ $\displaystyle=$
$\displaystyle\sum_{k}k\kappa_{k}x^{k}Z^{(0)\,k-1}=xW^{\prime}(\tilde{x})\,.$
(27)

This is summarized in the following theorem.

Theorem 1. If $\tilde{x}=xZ^{(0)}(x)$, the generating function of genus 1
partitions is given by

$Z^{(1)}(x)=\frac{X_{2}(\tilde{x})Y_{2}(\tilde{x})}{(1-X_{2}(\tilde{x}))^{4}\,(1-V(x))}\,.$
(28)

Alternatively, if we introduce

$\tilde{X}_{2}(x):=\frac{X_{2}(\tilde{x})}{(1-X_{2}(\tilde{x}))}\qquad{\tilde{Y}}_{2}(x):=\frac{Y_{2}(\tilde{x})}{(1-X_{2}(\tilde{x}))^{2}}$
(29)

we have the simple expression

$Z^{(1)}(x)=\frac{\tilde{Y}_{2}(x)\tilde{X}_{2}(x)(1+\tilde{X}_{2}(x))}{(1-V(x))}$
(30)

###  3.4 Examples and applications

####  3.4.1 $n=2p\to[2^{p}]$

If all $\kappa_{i}$ vanish but $\kappa_{2}=1$, i.e., if we consider partitions
of $n=2p$ into $p$ doublets, which is the celebrated case considered in [16,
8], we have $W(x)=x^{2}$, hence

$Z^{(0)}(x;\kappa_{2}=1,\kappa_{i\neq 2}=0)=\frac{1-\sqrt{1-4x^{2}}}{2x^{2}}$
(31)

as the solution of equ. (20). Then following Theorem 1, we find

$Z^{(1)}(x;\kappa_{2}=1,\kappa_{i\neq 2}=0)=\frac{x^{4}}{(1-4x^{2})^{5/2}}\,,$
(32)

in accordance with known results.

####  3.4.2 $n=3p\to[3^{p}]$

In that case, we take $\kappa_{3}=1$, $W(x)=x^{3}$, hence $Z^{(0)}$ satisfies
the third degree equation,

$(xZ)^{3}-Z+1=0$ (33)

and it is the GF of Fuss–Catalan numbers. We may write it as

$Z^{(0)}(x;\kappa_{3}=1,\kappa_{i\neq
3}=0)=\frac{2}{\sqrt{3x^{3}}}\sin\Big{(}\frac{1}{3}\mathrm{Arcsin\,}\big{(}\frac{3}{2}\sqrt{3x^{3}}\big{)}\Big{)}\,.$
(34)

Then following Theorem 1, one finds, after some algebra,

$Z^{(1)}(x;\kappa_{3}=1,\kappa_{i\neq
3}=0)=\frac{1152\,x^{3}\sin^{6}\left(\frac{1}{3}\mathrm{Arcsin\,}\big{(}\frac{3\sqrt{3x^{3}}}{2}\big{)}\right)}{\left(2\cos\left(\frac{1}{3}\mathrm{Arccos\,}\big{(}1-\frac{27x^{3}}{2}\big{)}\right)-1\right)\left(9\sqrt{x^{3}}-4\sqrt{3}\sin\left(\frac{1}{3}\mathrm{Arcsin\,}\big{(}\frac{3\sqrt{3x^{3}}}{2}\big{)}\right)\right)^{4}}$
(35)

with a Taylor expansion

$6x^{6}+102x^{9}+1212x^{12}+12330x^{15}+114888x^{18}+1011486x^{21}+8558712x^{24}+70324884x^{27}+564931230x^{30}+\cdots$

in agreement with direct calculation, see [2]. Note that the closest
singularity of $Z^{(1)}$ is at the vanishing point of the discriminant of
(33), namely $x^{3}=4/27$:

$Z^{(1)}(x;\kappa_{3}=1,\kappa_{i\neq
3}=0)\sim\frac{\mathrm{const.}}{(\frac{4}{27}-x^{3})^{5/2}}\,,$

when $x^{3}\to 4/27$, with the same exponent $5/2$ as in (32).

####  3.4.3 Total number of partitions of genus 0 and 1

Let all $\kappa$ be equal to 1, resp. all $\kappa$’s but $\kappa_{1}=0$. Then
the previous expressions yield the GF of the numbers of partitions of genus 0
or 1, with, resp. without singletons:

$\displaystyle Z^{(0)}(x;\kappa_{i}=1)$ $\displaystyle=$
$\displaystyle\frac{1-\sqrt{1-4x}}{2x}$ (36)
$\displaystyle\hat{Z}^{(0)}(x):=Z^{(0)}(x;\kappa_{1}=0,\kappa_{i\geq 2}=1)$
$\displaystyle=$
$\displaystyle\frac{1-\sqrt{1-\frac{4x}{1+x}}}{2x}=\frac{1+x-\sqrt{1-2x-3x^{2}}}{2x(1+x)}\qquad\mathrm{no\
singleton}$ $\displaystyle Z^{(1)}(x;\kappa_{i}=1)$ $\displaystyle=$
$\displaystyle\frac{x^{4}}{(1-4x)^{5/2}}$ (37)
$\displaystyle\hat{Z}^{(1)}(x):=Z^{(1)}(x;\kappa_{1}=0,\kappa_{i\geq 2}=1)$
$\displaystyle=$
$\displaystyle\frac{x^{4}}{(1-2x-3x^{2})^{5/2}}\qquad\mathrm{no\ singleton}$
(38)

on which we may verify the relations (10-11) above.

Proof. If all $\kappa_{i}=1$, $W(x)=x/(1-x)$ as a formal series, and
$Z^{(0)}(x)$, solution of $Z^{(0)}(x)=W(xZ^{(0)}(x))$ as a formal series, is
given by (36), (the GF of the Catalan numbers). Likewise, if $\kappa_{1}=0$,
the others equal to 1, $W(x)=x^{2}/(1-x)$, etc. For genus 1, we then make use
of Theorem 1 to derive (37-38). ∎

####  3.4.4 Number of partitions with a fixed number of parts, in genus 0 and
1

Let all $\kappa$ be equal to $y$, then $W(x)=xy/(1-x)$, and
$Z^{(g)}(x,y)=\sum_{n,k}p^{(g)}(n,k)x^{n}y^{k}$ is the GF of the numbers
$p^{(g)}(n,k)$ of genus $g$ partitions of $n$ with $k$ parts. $Z^{(0)}$ is the
solution of equ. (20)

$Z^{(0)}(x,y)=\frac{1+x-xy-\sqrt{(1+x-xy)^{2}-4x}}{2x}\,.$ (39)

which is the GF of Narayana numbers, and then we compute by (28)

$Z^{(1)}(x,y)=\frac{x^{4}y^{2}}{((1+x-xy)^{2}-4x)^{5/2}}$ (40)

which is the expression given by Yip [18], and Cori and Hetyei [3].

If we exclude singletons, $W(x;\kappa_{1}=0)=x^{2}y/(1-x)$, and the GF read
now

$\displaystyle\hat{Z}^{(0)}(x,y):=Z^{(0)}(x,y;\kappa_{1}=0)$ $\displaystyle=$
$\displaystyle\frac{{1+x}-\sqrt{(1-x)^{2}-4x^{2}y}}{2x(1+xy)}$ (41)
$\displaystyle\hat{Z}^{(1)}(x,y):=Z^{(1)}(x,y;\kappa_{1}=0)$ $\displaystyle=$
$\displaystyle\frac{x^{4}y^{2}}{((1-x)^{2}-4x^{2}y)^{5/2}}\,.$

##  4 …to genus 2

###  4.1 Primitive and semi-primitive diagrams of genus 2

The list of primitive and semi-primitive diagrams of genus 2 is known, thanks
to the work of Cori and Hetyei [4]. This has been confirmed independently, in
the present work, by generating on the computer all partitions of genus 2 of a
given type, and then eliminating all those that involve adjacent or parallel
edges. By inequality (19) these primitive diagrams have at most 18 points
(i.e., $n\leq 18$), and either up to 9 2-vertices, or one or two 3-vertices,
or one 4-vertex. In Table 1, are listed their number for increasing total
number of points $n$. 555In Table 1 of [4] there is the unfortunate omission
of the 175 primitive diagrams with one 3-vertex (a 3-cycle in their
terminology), while those diagrams are properly taken into account in the
ensuing formulae. These missing diagrams are listed in Fig. 10.

| 2-vertices | one 3-vertex | two 3-vertices | two 3-vertices | one 4-vertex
---|---|---|---|---|---
$n$ |  |  |  | semi-prim. |
6 | 0 | 0 | 1 | 0 | 0
7 | 0 | 14 | 0 | 0 | 0
8 | 21 | 0 | 20 | 0 | 6
9 | 0 | 141 | 0 | 0 | 0
10 | 168 | 0 | 65 | 15 | 15
11 | 0 | 407 | 0 | 0 | 0
12 | 483 | 0 | 52 | 36 | 9
13 | 0 | 455 | 0 | 0 | 0
14 | 651 | 0 | 0 | 21 | 0
15 | 0 | 175 | 0 | 0 | 0
16 | 420 | 0 | 0 | 0 | 0
17 | 0 | 0 | 0 | 0 | 0
18 | 105 | 0 | 0 | 0 | 0

Table 1. Number of (semi-)primitive diagrams of genus 2.

Based on this list of primitive diagrams, we may now write an equation similar
to (24)

$\displaystyle Z^{(2)}(x)$ $\displaystyle=$
$\displaystyle\sum_{n}n\kappa_{n}x^{n}(Z^{(0)}(x))^{n-1}Z^{(2)}(x)$
$\displaystyle+$ $\displaystyle\quad\mathrm{dressing\ of\ (semi-)primitive\
diagrams\ of\ genus\ 2}$

as illustrated in Fig. 7.
Remark. It might seem natural to also have in the r.h.s. of (4.1 ) a term with
two insertions of genus 1 subdiagrams. In fact such diagrams will be included
in the set of primitives and their dressings. An example is given by the first
diagram of Fig. 8.

Figure 7:  A graphical representation of relation (4.1)

###  4.2 Dressing of primitive diagrams of genus 2

The dressing of primitive diagrams with only 2-lines (Column 2 of Table 1)
involves the same functions $\tilde{X}_{2}$ and $\tilde{Y}_{2}$ defined above
in sect. 3.3: $\tilde{Y}_{2}$ is assigned to the line attached to point 1,
while the other lines carry the weight $\tilde{X}_{2}$. Hence their
contribution to the r.h.s. of equ.(4.1) reads

$z_{2}=\tilde{Y}_{2}(x)\Big{(}21\tilde{X}_{2}^{3}(x)+168\tilde{X}_{2}^{4}(x)+483\tilde{X}_{2}^{5}(x)+651\tilde{X}_{2}^{6}(x)+420\tilde{X}_{2}^{7}(x)+105\tilde{X}_{2}^{8}(x)\Big{)}$

with the notations of (29).

For the dressing of primitive diagrams with 3- or 4-vertices, we must
introduce new functions that generalize $X_{2}$ and $Y_{2}$ defined in (25-26)

$\displaystyle X_{\ell}(x)$ $\displaystyle=$
$\displaystyle\sum_{k\geq\ell}{k-1\choose\ell-1}\kappa_{k}x^{k}$ (43)
$\displaystyle Y_{\ell}(x)$ $\displaystyle=$
$\displaystyle\sum_{k\geq\ell}{k\choose\ell}\kappa_{k}x^{k}$
$\displaystyle\ell>2\qquad\tilde{X}_{\ell}(x):=\frac{X_{\ell}(\tilde{x})}{(1-X_{2}(\tilde{x}))^{\ell}}\quad$
;
$\displaystyle\quad\tilde{Y}_{\ell}(x):=\frac{Y_{\ell}(\tilde{x})}{(1-X_{2}(\tilde{x}))^{\ell}}\,.$

with, as before, $\tilde{x}=xZ^{(0)}(x)$. (Beware that the power of
$(1-X_{2}(\tilde{x}))$ in the denominator of $\tilde{X}_{\ell}$ does not apply
to $\ell=2$, compare with (29).) These functions too may also be expressed in
terms of derivatives of $W$: for example,
$Y_{3}(x)=\frac{1}{6}x^{3}W^{\prime\prime\prime}(x)$, etc.

Consider first a primitive diagram with a 3-vertex, like those depicted in
Fig. 9. Remember that all distinct rotated diagrams must be considered and
hence, the marked point 1 may be attached to the 3-vertex or to any one of the
2-lines.
(i) In the case where the marked point 1 is attached to one of the 2-lines,
its 2-vertex may be changed into a $k$ vertex, $k>2$ and as in sect. 3.2, this
yields a weight $Y_{2}(x)/(1-X_{2}(x))^{2}$, while the lines emanating from
the 3-vertex or parallel to it contribute $X_{3}(x)/(1-X_{2}(x))^{3}$. And
again, a final change of $x$ into $\tilde{x}$ completes the dressing.
(ii) In the former case, 1 attached to the 3-vertex, this 3-vertex may be
promoted to a $k$-vertex, $k>3$, with $k-3$ lines ending on four different
arcs of the circle: there are ${k\choose 3}$ ways of distributing them, whence
a weight $Y_{3}(x)$. Then adding parallel lines may be done in 3 ways, whence
a weight $1/(1-X_{2}(x))^{3}$. The 2-lines, on the other hand, carry a weight
$X_{2}(x)/(1-X_{2}(x))$, just like in sect. 3.2. Finally, again as in sect.
3.2, the variable $x$ has to be substituted for the dressed one
$\tilde{x}=xZ^{(0)}$ to take into account all possible insertions of genus 0
subdiagrams.
(iii) There is, however, a case not yet accounted for by the previous
dressing. When the marked point 1 is attached to a 2-line parallel to a pair
of edges of the 3-vertex, that line has been erased in the reduction process
and must be restored. A weight $2Y_{2}(x)/(1-X_{2}(x))$ is attached to that
new line, with a factor 2 comes from the two ends of the 2-line, and a single
factor $1/(1-X_{2}(x))$ as compared with what we saw in sect. 3.2, because the
counting of parallel lines between the new line and the 3-vertex has already
been taken into account in the term $\tilde{X}_{3}(x)$.

Now each of the previous contributions must be weighted by its number of
occurrences when the diagram is rotated. For example, each of the two diagrams
of Fig. 9 contributes $+\ 4\tilde{Y}_{2}\tilde{X}_{2}\tilde{X}_{3}$ (since
marked point 1 may be at any of the four end-points of the 2-lines) +$\
3\tilde{Y}_{3}\tilde{X}_{2}^{2}$ (3 ways of attaching point 1 to the 3-vertex)
$\ +3\tilde{X}_{3}\tilde{X}_{2}^{2}(2Y_{2}(\tilde{x})/(1-X_{2}(\tilde{x}))$
(when 1 lies on a line parallel to two edges of the 3-vertex). More generally,
for a primitive diagram of an orbit of symmetry order ${\mathfrak{s}}$, with
one 3-vertex and $p$ 2-lines, $n=3+2p$, the weight is

$\frac{1}{{\mathfrak{s}}}\left(2p\tilde{Y}_{2}\tilde{X}_{2}^{p-1}\tilde{X}_{3}+3\tilde{Y}_{3}\tilde{X}_{2}^{p}+3\tilde{X}_{3}\tilde{X}_{2}^{p}(2Y_{2}(\tilde{x})/(1-X_{2}(\tilde{x}))\right)\,,$

where we write $\tilde{X}_{\ell}$ and $\tilde{Y}_{\ell}$ in short for
$\tilde{X}_{\ell}(x)$ and $\tilde{Y}_{\ell}(x)$. Thus the orbits of partitions
of $[\\![n]\\!]$ with a primitive diagram with a single 3-vertex contribute

$\sum_{\mathrm{orbits}}\frac{1}{{\mathfrak{s}}}\left((n-3)\tilde{Y}_{2}\tilde{X}_{2}^{\frac{n-5}{2}}\tilde{X}_{3}+3\tilde{X}_{2}^{\frac{n-3}{2}}\Big{(}\tilde{Y}_{3}+\tilde{X}_{3}\frac{2Y_{2}(\tilde{x})}{(1-X_{2}(\tilde{x}))}\Big{)}\right)\,.$

But as we saw in (17), for a given $n$,
$\sum_{\mathrm{orbits}}\frac{1}{{\mathfrak{s}}}=\frac{N}{n}$, where $N$ is the
number listed in Table 1, column 3, row $n$. In total the diagrams with a
single 3-vertex contribute to the r.h.s. of (4.1) the amount $z_{3}$ listed
below in (4.3).

The dressing of primitive diagrams with two 3-vertices or one 4-vertex
(columns 4 and 6 of Table 1) is done along similar lines. Thus for an orbit of
primitive diagram with two 3-vertices and $p$ 2-lines, with now $n=2p+6$, we
get

$\frac{1}{{\mathfrak{s}}}\left(2p\tilde{Y}_{2}\tilde{X}_{3}^{2}\tilde{X}_{2}^{p-1}+6\tilde{X}_{2}^{p}\tilde{X}_{3}\Big{(}\tilde{Y}_{3}+\tilde{X}_{3}\frac{2Y_{2}(\tilde{x})}{(1-X_{2}(\tilde{x}))}\Big{)}\right)$
(44)

and the total contribution $z_{33}$ of such diagrams is given in (4.3).

For a primitive diagram with one 4-vertex and $p$ 2-lines, (and $n=2p+4$),
likewise, we get

$\frac{1}{{\mathfrak{s}}}\left(2p\tilde{Y}_{2}\tilde{X}_{4}\tilde{X}_{2}^{p-1}+4\tilde{X}_{2}^{p}\Big{(}\tilde{Y}_{4}+\tilde{X}_{4}\frac{2Y_{2}(\tilde{x})}{(1-X_{2}(\tilde{x}))}\Big{)}\right)$

and the total contribution $z_{4}$ is given in (50).

Finally, the dressing of semi-primitive diagrams (see a sample in Fig. 13)
requires special care to avoid double counting. Consider such a semi-primitive
diagram, thus with two 3-vertices and $p$ 2-lines, $n=2p+6$. First, when the
point 1 is attached to one of the 2-lines or one of the two 3-vertices, we
have a contribution like the first two terms in (44), but multiplied by
$(1-X_{2}(\tilde{x}))$ not to count twice the set of lines between the two
parallel lines. Moreover, when the point 1 is attached to an added line
parallel to one of the branches of the two 3-vertices, there are 5 locations
for that line, whence a contribution
$\frac{5}{{\mathfrak{s}}}\tilde{X}_{3}^{2}\tilde{X}_{2}^{p}\times
2Y_{2}(\tilde{x})$, with no further factor $1/(1-X_{2}(\tilde{x}))$. In total,
a semi-primitive diagram contributes

$\frac{1}{{\mathfrak{s}}}\left((1-X_{2}(\tilde{x}))\Big{(}2p\tilde{Y}_{2}\tilde{X}_{3}^{2}\tilde{X}_{2}^{p-1}+6\tilde{Y}_{3}\tilde{X}_{3}\tilde{X}_{2}^{p}\Big{)}+5\tilde{X}_{2}^{p}\tilde{X}_{3}^{2}(2Y_{2}(\tilde{x}))\right)$

and the total from semi-primitive diagrams appears as $z_{33s}$ in (4.3).

Remark. As noticed by Cori and Hetyei [4], the semi-primitive diagrams may be
obtained from the primitive ones by “splitting” a vertex of valency larger
than 3. For example the three diagrams of Fig. 13 may be obtained from those
of Fig. 14 by splitting their 4-vertex as in Fig. 15. One might thus consider
only primitive diagrams and include the splitting operation in the dressing
procedure. The benefit is that primitive diagrams are easy to characterize:
they are such that the permutation $\tau$ has no 1-cycle and
$\sigma\circ\tau^{-1}$ no 2-cycle.

###  4.3 General case of genus 2

Collecting all the contributions of the previous subsection, we can now make
equation (4.1) more explicit in the form of
Theorem 2. The generating function of genus 2 partitions is given by

$\qquad\qquad Z^{(2)}(x)(1-V(x))=z_{2}+z_{3}+z_{33}+z_{33s}+z_{4}$ (45)

where $V(x)$ has been given in (27) and $z_{2},\cdots,z_{4}$ are the
contributions of dressing the (semi-)primitive diagrams listed in Table 1.

$\displaystyle z_{2}$ $\displaystyle=$
$\displaystyle\tilde{Y}_{2}(21\tilde{X}_{2}^{3}+168\tilde{X}_{2}^{4}+483\tilde{X}_{2}^{5}+651\tilde{X}_{2}^{6}+420\tilde{X}_{2}^{7}+105\tilde{X}_{2}^{8})\,;$
(46) $\displaystyle z_{3}$ $\displaystyle=$
$\displaystyle\tilde{X}_{3}\tilde{Y}_{2}(8\tilde{X}_{2}+94\tilde{X}_{2}^{2}+296\tilde{X}_{2}^{3}+350\tilde{X}_{2}^{4}+140\tilde{X}_{2}^{5})$
$\displaystyle\qquad+\tilde{X}_{2}(6\tilde{X}_{2}+47\tilde{X}_{2}^{2}+111\tilde{X}_{2}^{3}+105\tilde{X}_{2}^{4}+35\tilde{X}_{2}^{5})\Big{(}\tilde{Y}_{3}+\tilde{X}_{3}\frac{2Y_{2}(\tilde{x})}{(1-X_{2}(\tilde{x}))}\Big{)}\,;$
$\displaystyle z_{33}$ $\displaystyle=$
$\displaystyle\tilde{X}_{3}^{2}\tilde{Y}_{2}(5+26\tilde{X}_{2}+26\tilde{X}_{2}^{2})$
$\displaystyle\qquad+\tilde{X}_{3}(1+15\tilde{X}_{2}+39\tilde{X}_{2}^{2}+26\tilde{X}_{2}^{3})\Big{(}\tilde{Y}_{3}+\tilde{X}_{3}\frac{2Y_{2}(\tilde{x})}{(1-X_{2}(\tilde{x}))}\Big{)}\,;$
$\displaystyle z_{33s}$ $\displaystyle=$
$\displaystyle\tilde{Y}_{2}\tilde{X}_{3}^{2}\tilde{X}_{2}(6+18\tilde{X}_{2}+12\tilde{X}_{2}^{2})(1-X_{2}(\tilde{x}))$
$\displaystyle\qquad+\tilde{Y}_{3}\tilde{X}_{3}\tilde{X}_{2}^{2}(9+18\tilde{X}_{2}+9\tilde{X}_{2}^{2})(1-(X_{2}(\tilde{x}))+\tilde{X}_{3}^{2}\tilde{X}_{2}^{2}(15+30\tilde{X}_{2}+15\tilde{X}_{2}^{2})Y_{2}(\tilde{x})\,;$
$\displaystyle z_{4}$ $\displaystyle=$
$\displaystyle\tilde{Y}_{2}\tilde{X}_{4}(3\tilde{X}_{2}+9\tilde{X}_{2}^{2}+6\tilde{X}_{2}^{3})+(3\tilde{X}_{2}^{2}+6\tilde{X}_{2}^{3}+3\tilde{X}_{2}^{4})\Big{(}\tilde{Y}_{4}+\tilde{X}_{4}\frac{2Y_{2}(\tilde{x})}{(1-X_{2}(\tilde{x}))}\Big{)}\,,$
(50)

and we recall that $\tilde{X}_{\ell}$ and $\tilde{Y}_{\ell}$ stand for
$\tilde{X}_{\ell}(x)$ and $\tilde{Y}_{\ell}(x)$ defined in (43).

The resulting expressions for the numbers $C_{n,[\alpha]}^{(2)}$ have been
tested up to $n=15$ and all $[\alpha]$ against direct enumeration using
formulae (16) or (17), and for some higher values of $n$ for a few particular
cases.

Figure 8:  The primitive diagrams of order 8, type $[2^{4}]$ and genus 2, with
their weight in blue Figure 9:  The primitive diagrams of order 7, type
$[2^{2}\,3]$ and genus 2, with the sum of weights equal to 14 Figure 10:  The
primitive diagrams of order 15, type $[2^{6}\,3]$ and genus 2, with the sum of
weights equal to $175$ Figure 11: The primitive diagram of order 6, type
$[3^{2}]$ and genus 2, of weight 1 Figure 12:  The primitive diagrams of order
8, type $[2\,3^{2}]$ and genus 2, of total weight 20 Figure 13:  The 3 semi-
primitive diagrams of order 10, type $[2^{2}\,3^{2}]$, and genus 2, with the
sum of weights equal to 15 Figure 14:  The 2 primitive diagrams of order 8,
type $[2^{2}\,4]$, and genus 2, with the sum of weights equal to 6  Figure 15:
The splitting procedure, by which here a 4-vertex is split into two 3-vertices

###  4.4 Particular cases

####  4.4.1 Genus 2 partitions of $n=2p$ into $p$ doublets

In the simplest case where only $\kappa_{2}\neq 0$ (and set equal to 1 with no
loss of generality), the primitive diagrams are of order $n\leq 18$ – a sample
of which is shown in Fig. 8 666All genus 2 primitive and semi-primitive
diagrams may be found on
https://www.lpthe.jussieu.fr/~zuber/Z_UnpubPart.html. They involve only
2-lines and their dressing is given by the expression (46) above. Thus

$\displaystyle Z^{(2)}(x;\kappa_{2}=1,\kappa_{i\neq 2}=0)$ $\displaystyle=$
$\displaystyle\frac{\tilde{Y}_{2}(x)}{(1-2x^{2}Z^{(0)}(x))}\\!\\!\\!\\!\\!\\!\\!\\!$
$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\Big{(}21\tilde{X}_{2}^{3}(x)+168\tilde{X}_{2}^{4}(x)+483\tilde{X}_{2}^{5}(x)+651\tilde{X}_{2}^{6}(x)+420\tilde{X}_{2}^{7}(x)+105\tilde{X}_{2}^{8}(x)\Big{)}$

with the notations of (29). After some substantial algebra (carried out by
Mathematica), one finds

$Z^{(2)}(x;\kappa_{2}=1,\kappa_{i\neq
2}=0)=\frac{21x^{8}(1+x^{2})}{(1-4x^{2})^{11/2}}$ (51)

in agreement with the results of [8].

####  4.4.2 Genus 2 partitions of $n=3p$ into $p$ triplets

We now assume as in sect. 3.4.2 that only $\kappa_{3}\neq 0$ (and equals 1
with no loss of generality). Let
$s:=\sin\left(\frac{1}{3}\sin^{-1}\left(\frac{3}{2}\sqrt{3}x^{3/2}\right)\right)$.
Then, following (45), $Z^{(2)}$ takes the fairly cumbersome form

$\displaystyle Z^{(2)}(x;\kappa_{3}=1;\kappa_{i\neq 3}=0)$ $\displaystyle=$
$\displaystyle\hskip-142.26378pt\frac{192s^{6}x^{6}\left(8s^{3}\left(128\left(11264s^{9}+8676\sqrt{3}s^{6}x^{3/2}+3105s^{3}x^{3}\right)+9315\sqrt{3}x^{9/2}\right)+729x^{6}\right)}{\left(2\cos\left(\frac{1}{3}\mathrm{Arccos\,}\big{(}1-\frac{27x^{3}}{2}\big{)}\right)-1\right)\left(9\sqrt{x^{3}}-4\sqrt{3}\sin\left(\frac{1}{3}\mathrm{Arcsin\,}\big{(}\frac{3\sqrt{3x^{3}}}{2}\big{)}\right)\right)^{10}}$

(compare with the denominator of $Z^{(1)}$ in (35). The first terms of the
series expansion read

$x^{6}+144x^{9}+6046x^{12}+149674x^{15}+2771028x^{18}+42679084x^{21}+\cdots$

One finds again a singular behaviour of the form

$Z^{(2)}(x;\kappa_{3}=1;\kappa_{i\neq
3}=0)\sim\frac{\mathrm{const.}}{(\frac{4}{27}-x^{3})^{11/2}}\,.$

####  4.4.3 Total number of genus 2 partitions

Taking all $\kappa$’s equal to 1 (and possibly $\kappa_{1}=0$), as in sect.
3.4.3, hence $W(x)=x/(1-x)$ or $\widehat{W}(x)=x^{2}/(1-x)$, we compute by (7)
the GF of the total number of genus 2 partitions (with or without singletons),
and we recover the result of Cori and Hetyei [4]

$Z^{(2)}(x;\kappa_{i}=1)=\frac{x^{6}(1+6x-19x^{2}+21x^{3})}{(1-4x)^{11/2}}\,,$

and also

$Z^{(2)}(x;\kappa_{1}=0;\kappa_{i>1}=1)=\frac{x^{6}(1+10x+5x^{2}+5x^{3}+9x^{4})}{(1-2x-3x^{2})^{11/2}}$

in accordance with (10).

####  4.4.4 Genus 2 partitions into $r$ parts

The two-variable GF of the number of genus 2 partitions into a given number of
parts is obtained as in sect. 3.4.4 by setting all $\kappa_{i}=y$. Theorem 2
leads to

$\displaystyle Z^{(2)}(x,y)$ $\displaystyle=$
$\displaystyle\frac{x^{6}y^{2}\,p(x,y)}{((1+x-xy)^{2}-4x)^{11/2}}$ (52)
$\displaystyle p(x,y)$ $\displaystyle=$ $\displaystyle
1-x(4-10y)+x^{2}(6-10y-15y^{2})-x^{3}(4+10y-39y^{2}+4y^{3})$
$\displaystyle\qquad+x^{4}(1+10y-15y^{2}-4y^{3}+8y^{4})$

as first derived by Cori–Hetyei [4].

The counting of genus 2 partitions into $r$ parts is then obtained by
identifying the coefficient of $y^{r}$ in (52). For example, for $r=2$
(partitions into two parts with or without singleton)

$\displaystyle Z^{(2)}(x;r=2)$ $\displaystyle=$
$\displaystyle\frac{x^{6}}{(1-x)^{7}}$ $\displaystyle=$
$\displaystyle\sum_{n\geq 6}{n\choose 6}x^{n}$ $\displaystyle=$
$\displaystyle\sum_{n\geq 6}x^{n}\sum_{p=2}^{n-2}\frac{n}{6}{p-1\choose
2}{n-p-1\choose 2}$

in agreement with a general result for $r=2$ and arbitrary genus [2]. For
$r=3$ (partitions into three parts without singleton)

$Z^{(2)}(x;r=3)=\frac{14x^{7}(1+2x)}{(1-x)^{9}}=14\sum_{n\geq 7}{n\choose
7}\frac{3n-13}{8}x^{n}$

##  5 Conclusion and perspectives

In principle the method could be extended to higher genus, but at the price of
an increasing number of (semi-)primitive diagrams, whose set remains to be
listed, with an Ansatz of the form

$Z^{(g)}(x)=\frac{\sum\mathrm{dressing\ of\ (semi-)primitive\ diagrams\ of\
genus}\ g}{1-\sum_{n}n\kappa_{n}x^{n}(Z^{(0)}(x))^{n-1}}\,.$ (53)

For instance, in genus 3, primitive diagrams may occur up to $n=30$ and they
start at order $n=12$. An Ansatz for partitions into doublets (i.e., of type
$[2^{p}]$), for $g=3$ is thus

$Z^{(3)}(x;\kappa_{2}=1,\kappa_{i\neq
2}=0)=\frac{\tilde{Y}_{2}(x)\tilde{X}_{2}^{5}(x)}{(1-2x^{2}Z^{(0)}(x))}\sum_{j=0}^{9}a_{j}\tilde{X}_{2}^{j}(x)$

in which the numerical coefficients $a_{j}$ count the primitives of type
$[2^{j+6}]$ and may be determined against the known result of [8]

$Z^{(3)}(x;\kappa_{2}=1,\kappa_{i\neq
2}=0)=\frac{11x^{12}(135+558x^{2}+158x^{4})}{(1-4x^{2})^{17/2}}\,.$ (54)

hence

$\displaystyle Z^{(3)}(x;\kappa_{2}=1,\kappa_{i\neq 2}=0)$ $\displaystyle=$
$\displaystyle\frac{11\tilde{Y}_{2}(x)\tilde{X}_{2}^{5}(x)}{(1-2x^{2}Z^{(0)}(x))}\,\Big{(}135+2313\tilde{X}_{2}(x)+15728\tilde{X}_{2}^{2}(x)+57770\tilde{X}_{2}^{3}(x)$
$\displaystyle+128985\tilde{X}_{2}^{4}(x)\\!\\!\\!\\!$ $\displaystyle+$
$\displaystyle\\!\\!\\!\\!183955\tilde{X}_{2}^{5}(x)+169078\tilde{X}_{2}^{6}(x)+97188\tilde{X}_{2}^{7}(x)+31850\tilde{X}_{2}^{8}(x)+4550\tilde{X}_{2}^{9}(x)\Big{)}\,.$

We end this paper with a few remarks on some intriguing issues.
There is some evidence of a universal singular behaviour of all generating
functions,

$Z^{(g)}(x)\sim(x_{0}-x)^{\frac{1}{2}-3g}$ (55)

as can be seen on the partitions into doublets (32,51,54), and for $g=1,2$ on
other cases. This would imply a large $n$ behaviour of coefficients
$C_{n,[\alpha]}^{(g)}$ (for appropriately rescaled patterns $\alpha$) of the
form

$C_{n,[\alpha]}^{(g)}\sim
x_{0}^{-n-3g+\frac{1}{2}}\,n^{3g-\frac{1}{2}}\qquad\mathrm{as}\
n,[\alpha]\mathrm{\ grow\ large}\,.$

The “critical exponent” $\frac{1}{2}-3g$ is familiar to physicists in the
context of boundary loop models and Wilson loops [11]. Such a connection is
natural in the case of partitions into doublets, since it is known that in
that case, the counting amounts to computing the expectation value of ${\rm
tr}\,M^{n}$ in a Gaussian matrix integral, hence for large $n$, of a large
loop. That the same singular or asymptotic behaviour takes place in (all ?)
other cases seems to indicate that an effective Gaussian theory takes place in
that limit.777I’m grateful to Ivan Kostov for discussions on that point
A natural question is whether the Topological Recurrence of Chekhov, Eynard
and Orantin [7] is relevant for the counting of partitions and is related to
or independent of the approach of this paper.
As mentioned in the introduction, the formulae derived in this paper yield an
interpolation between expansions on ordinary and on free cumulants. What is
the relevance of this interpolation? How does it compare with other existing
interpolations ?
All these questions are left for future investigation.

Acknowledgements. It is a pleasure to thank Philippe Di Francesco, Elba
Garcia-Failde and Ivan Kostov for discussions and comments, and Colin
McSwiggen for suggesting amendments of this paper. I’m particularly grateful
to Robert Coquereaux for a careful reading of a first draft of the manuscript
and for providing me with very efficient Mathematica codes.

## References

  * [1] É. Brézin, C. Itzykson, G. Parisi, J.-B. Zuber, Planar diagrams, Comm. Math. Phys. 59 (1978) 35–51
  * [2] R. Coquereaux and J.-B. Zuber, Counting partitions by genus. II. A compendium of results, to appear
  * [3] R. Cori and G. Hetyei, Counting genus one partitions and permutations, Sém. Lothar. Combin. 70 (2013) [B70e], http://arxiv.org/abs/1306.4628
  * [4] R. Cori and G. Hetyei, Counting partitions of a fixed genus, The Electronic Journal of Combinatorics 25 (4) (2018) #P 4.26, http://arxiv.org/abs/1710.09992
  * [5] P. Cvitanovic, Planar perturbation expansion, Phys. Lett. 99B (1981) 49–52
  * [6] J.-M. Drouffe, as cited in D. Bessis, C. Itzykson and J.-B. Zuber, Quantum field theory techniques in graphical enumeration, Adv. Appl. Math. 1 (1980) 109–157
  * [7] B. Eynard, Counting Surfaces, Progress in Mathematical Physics 70, Birkhäuser 2016
  * [8] J. Harer and D. Zagier, The Euler characteristic of the moduli space of curves, Invent. Math. 85 (1986) 457–485
  * [9] G. ’t Hooft, A Planar Diagram Theory for Strong Interactions, Nucl. Phys. B 72 (1974) 461–473
  * [10] A. Jacques, Sur le genre d’une paire de substitutions, C. R. Acad. Sci. Paris 267 (1968), 625–627.
  * [11] I. Kostov, Boundary Loop Models and 2D Quantum Gravity, in Exact Methods in Low-Dimensional Statistical Physics and Quantum Computing, Les Houches Summer School 2008, J. Jacobsen, S. Ouvry, V. Pasquier, D. Serban and L. Cugliandolo edrs, Oxford U. Press
  * [12] G. Kreweras, Sur les partitions non croisées d’un cycle, Discrete Math., 1 (1972) 333–350
  * [13] S.K. Lando and A.K. Zvonkin, Graphs on Surfaces and Applications, with an appendix by D. Zagier, Encycl. of Math. Sci. 141 (2004)
  * [14] R. Speicher, Multiplicative functions on the lattice of non-crossing partitions and free convolution, Math. Annalen, 298 (1994) 611– 628
  * [15] D.V. Voiculescu, Addition of non-commuting random variables, J. Operator Theory 18 (1987) 223–235
  * [16] T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus I, J. Combinatorial Theory B 13 (1972), 192–218
  * [17] T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus II, J. Combinatorial Theory B 13 (1972), 122–141
  * [18] M. Yip, Genus one partitions, PhD thesis, University of Waterloo, 2006