Counting non isomorphic chord diagrams

Robert Cori Michel Marcus

Labri, Université Bordeaux 1, 351 Cours de la Libération 33405 Talence Cedex, France,

cori@labri.u-bordeaux.fr
marcus@labri.u-bordeaux.fr

January 1997

To Marcel-Paul Schützenberger, in memoriam Running head :

Non isomorphic chord diagrams

Mail should be sent to:

Robert Cori Labri, Université Bordeaux 1, 351 Cours de la Libération 33405 Talence Cedex, France

Abstract

Different formulas counting families of non isomorphic chord diagrams are given : planar and toroidal ones and those of maximal genus. These formulas are obtained establishing results on the structure of the automorphism group of diagrams of a given genus.

1 Introduction

A chord diagram consists of 2n points on a circle joined pairwise by chords. The genus of the diagram is that of the surface in which it can be imbedded in such a way that the circle is homeomorphic to a disk, the chords are not intersecting Jordan curves outside the disk, and all the domains limited by the chords are simply connected. Many different combinatorial objects equivalent to diagrams were considered by various authors, for instance one-vertex maps [13](or one-face maps) and polygons where sides are identified pairwise [6].

The number of chord diagrams with n chords and genus g was first computed by Walsh and Lehman [13], an elegant recursion formula was established by Harer and Zagier [6], and Jackson [7] has shown the relationship between the enumeration of chord diagrams and the determination of some connection coefficients in the algebra of the symmetric group.

Two diagrams are isomorphic if one is obtained from the other by a rotation of the circle. Few is known about the number of non isomorphic diagrams, the results reported above concern rooted diagrams : two isomorphic diagrams are both counted in these enumerations. The enumeration of non isomorphic diagrams was shown to be of interest in the context of Vassiliev invariants of knots [1].

We give here exact formulas for the number of non isomorphic diagrams of genus 1 and of those of maximal genus. To obtain these formulas we have established precise results on the structure of the automorphism group of a digram of given genus : we make use of the notion of quotient of a diagram by a subgroup of its automorphism group. The two following facts are crucial for establishing the enumeration formulas, we consider them as the main results of this paper :

- The number of different diagrams of genus 1 with n chords having a given quotient depends only on some simple parameters of this quotient.

- A diagram with an even number of chords is of maximal genus if and only if it admits a quotient of maximal genus.

In the rest of the paper we consider a diagram combinatorially as an involution, its genus is a simple function of the number of cycles of the product of this involution by a circular permutation. For a description of the relationship between the topological definitions of maps and combinatorial ones the reader can consult [5].

2 Definitions and notation

2.1 Diagrams and their genus

In all the paper we denote by [p] the set {1, 2, …, p − 1, p} which elements are called points, ζ_{p} is the circular permutation (1, 2, …, p), which will also be denoted by ζ if p is implicit. A chord diagram is a fixed point free involution α, on the set of p = 2n points, each cycle of α (consisting of two points) is called a chord.

1  2 3 4 5 6 7 8

Figure 1: A planar diagram α = (1, 2)(3, 4)(5, 8)(6, 7)

The faces of the diagram are the cycles of the product αζ_{2n}. The genus of the diagram α is the non negative integer g given by (Euler Formula) :

2g = n − z(αζ_{2n}) + 1

where z(θ) denotes the number of cycles of the permutation θ, and n = z(α) is the number of chords.

A quasi-diagram β is an involution on a a set of points, a cycle of length 2 of β is a chord, and a cycle of length 1 is an isolated point. The genus γ of a quasi-diagram β with m chords and s isolated points is given by :

2γ = m + s − z(βζ) + 1

In this formula ζ = ζ_{2m+s}. The orbits of βζ are the faces of the quasi-diagram β.

1  2 3 4 5 6 7 8  _{1} _{2}_{3}_{4}_{5}_{6}_{7}_{8}

Figure 2: A toroidal diagram, drawn in the plane, and in the torus.

The cyclic group generated by ζ_{2n} (denoted ζ in the sequel) acts on the set of diagrams with n chords by conjugation. Two diagrams α and α′ are isomorphic if and only if one is obtained from the other by some rotation, i.e. if one is conjugated of the other by some power ζ^{k} of the circular permutation ζ, that is : α = ζ^{−k}α′ζ^{k}. The permutation ζ^{k} is an automorphism of α if :

α = ζ^{−k}αζ^{k}

Recall that in the cyclic group < ζ > generated by ζ, all the elements are regular permutations: for any integer k, all the orbits of ζ^{k} have the same length, and the common length q of these orbits divides 2n. In a finite cyclic group, for any integer q dividing its order the number of elements of order q is independent of the group and is equal to ϕ(q), where ϕ is the Euler arithmetic function: ϕ(q) is the number of integers less than q which are relatively prime with q, it is also the number of different generators of the cyclic group of order q.

2.2 Quotients and liftings

Let n be a positive integer, k be a divisor of 2n, (2n = kq), denote ζ = ζ_{2n} and let α be a diagram with n chords for which ζ^{k} is an automorphism. The quotient \overline{α} of α by the group < ζ^{k} > generated by ζ^{k} is the permutation \overline{α}, acting on the orbits ω_{1}, …, ω_{k} of ζ^{k}, given by:

\overline{α}(ω_{i}) = ω_{j} if and only if ∀x ∈ ω_{i}, α(x) ∈ ω_{j}

If \overline{α} is a quotient of α, then α is a lifting of \overline{α}.

Note that the quotient of a diagram is a quasi-diagram. We denote by π the mapping of the set of points [2n] onto the set of orbits Ω = {ω_{1}, …, ω_{k}} given by:

π(i) = ω_{j} ⇔ ∃a ≥ 0, i = ak + j

We will also use the inverse:

π^{−1}(ω_{i}) = {i, i + k, i + 2k, …, i + (q − 1)k}

3 Enumeration scheme

3.1 Main tool

Consider any family D of diagrams and assume D invariant by rotations. Let D_{n} be the subset of D consisting of diagrams with n chords, and denote by d_{n} the number of elements of D_{n}; the number d_{n}^{∗} of non isomorphic diagrams of D_{n} is the number of orbits of the action on D_{n} of the cyclic group < ζ_{2n} > generated by ζ_{2n}. For two integers k and n such that k < 2n, we denote by ρ_{D}(n, k) the number of diagrams of D_{n} which are liftings of quasi-diagrams on k points.

The following Lemma will be used for all the counting formulas obtained in the rest of the paper:

Lemma 3.1 The number d_{n}^{∗} is given by:

d_{n}^{∗} = \frac{1}{2n}[d_{n} + ∑_{k|2n,k≠2n} ϕ(\frac{2n}{k})ρ_{D}(n, k)]

Proof: By Burnside Lemma, the number d_{n}^{∗} of non isomorphic diagrams with n chords of any family D is given by :

d_{n}^{∗} = \frac{1}{2n} ∑_{k=1}^{2n} F ix(ζ^{k})

where F ix(ζ^{k}) is the number of diagrams of D_{n} left fixed by the action of ζ^{k}.

Considering identity apart, this can be restated :

d_{n}^{∗} = \frac{1}{2n}[d_{n} + ∑_{k=1}^{2n−1} F ix(ζ^{k})]

Since the number of diagrams fixed by a power ζ^{k} of ζ depends only on the order of ζ^{k}, and the number of elements of < ζ > of order q is ϕ(q) we have :

d_{n}^{∗} = \frac{1}{2n}[d_{n} + ∑_{k|2n,k≠2n} ϕ(\frac{2n}{k})F ix(ζ^{k})]  (1)

But a diagram α is such that ζ^{k}αζ^{−k} = α if and only if it has a quotient which is a quasi-diagram on k points, proving the result. □

3.2 The number of non isomorphic diagrams

Lemma 3.1 shows that the enumeration of non isomorphic diagrams of a family D closed by conjugation reduces to the question: “ given a quasi-diagram β with k points how many liftings of β are there which are diagrams with n chords belonging to the family D?”. The following lemma gives an answer when D is the whole family A of diagrams :

Lemma 3.2 Let β be a quasi-diagram on k points with m chords, β admits a lifting which is a diagram on n chords, if and only if the following two conditions hold :

• k divides 2n

• \frac{2n}{k} is even or k = 2m.

Moreover, if these conditions are satisfied the number of such liftings is (\frac{2n}{k})^{m}.

Proof:

Let ω_{i} be an isolated point of β, then for any j in π^{−1}ω_{i}, α(j) is also in π^{−1}ω_{i}. Thus we must have α(j) = j + ak mod(2n) for a certain integer a such that ak < 2n. But since α is an involution we have:

α(j) + ak = j mod(2n)

Giving 2ak = 0 mod(2n) and 2ak = 2n, hence \frac{2n}{k} is even and α(j) is uniquely determined if π(j) is an isolated point.

For any chord (ω_{i}, ω_{j}) of β, α(i) has to be chosen among all the elements of π^{−1}(ω_{j}). And this choice determines uniquely α(i′) for any i′ in π^{−1}(ω_{i}). Since there are \frac{2n}{k} elements in π^{−1}(ω_{j}), and since β has m chords this ends the proof of the lemma. □

Let (2n − 1)!! = \frac{(2n)!}{2^{n}n!} denote the odd factorial

Corollary 3.3 The number a_{n}^{∗} of non isomorphic diagrams with n chords is given by the formula in Lemma 3.1 where a_{n} = (2n − 1)!! and

ρ_{A}(n, k) = \{ \begin{matrix}(k − 1)!!(\frac{2n}{k})^{k/2} & if \frac{2n}{k} is odd \\ ∑_{m=0}^{⌊ \frac{k}{2} ⌋} \binom{k}{2m}(2m − 1)!!(\frac{2n}{k})^{m} & if \frac{2n}{k} is even \end{matrix}

Proof : The value of a_{n} is the number of fixed points free involutions on 2n which is the odd factorial (2n − 1)!!. If \frac{2n}{k} is odd then k is even and the quasi-diagrams to be lifted are diagrams with \frac{k}{2} chords their number is (k − 1)!!, if \frac{2n}{k} is even, then any quasi-diagram with k points and m ≤ ⌊\frac{k}{2}⌋ chords can be lifted in A_{n}, and there are \binom{k}{2m}(2m − 1)!! such quasi-diagrams. □

4 Liftings of given genus.

When we take for the family D the set of diagrams of given genus, Lemma 3.2 gives very few information about ρ_{D}(n, k) since it says nothing about the genus of the diagram built from a quotient. In order to obtain such information we use Riemann-Hurwitz formula which gives necessary conditions for a quasi-diagram with k points and genus γ to have a lifting which is a digram of genus g with n chords.

4.1 Riemann-Hurwitz formula

Let α be a diagram with n chords and ψ = ζ^{k} be an automorphism of α of order q, (2n = kq). Clearly ψ acts on the chords and on the faces of α. A chord (i, j) of α is fixed by ψ if ψ(i) = j, note that if ψ fixes a chord then it is of order 2. A face of α is fixed by ψ if ψ exchanges its points . Let β be the quotient of α by the automorphism group < ψ > and let s be the number of isolated points of β, if s > 0 then < ψ > is of even order and s is the number of chords fixed by the element of order 2 of < ψ >. Riemann-Hurwitz formula is a relation between the genus g of α, the genus γ of β and the number of fixed faces of the different powers of ψ. This classical result was shown to have a combinatorial setting for maps [10], giving in the case of diagrams :

Theorem 1 With the above notation we have :

(RH) 2g − 1 = (2γ − 1)q + \frac{q}{2}s + ∑_{j=1}^{q−1} χ(ψ^{j})

where χ(ψ^{j}) is the number of faces left fixed by ψ^{j}.

As a consequence we have informations on the quasi-diagrams which are quotients of planar and toroidal diagrams.

Corollary 4.1 If g = 0 then γ = 0. Moreover one of the two following situations holds:

• s = 0 and χ(ψ^{j}) = 1 for j = 1, … q − 1

• s = 1, q = 2 and χ(ψ) = 0

Proof : It is clear from the relation that γ ≠ 0 implies 2g − 1 > 0. For the second part remark that an automorphism ψ cannot fix more than one face since the number of faces fixed by a power of ψ is not less than the number of those fixed by ψ. Then by arithmetic arguments it fixes one face and s = 0 or it fixes no face and then it is of order 2. □

The following corollary may be obtained as a consequence of a more general result on maps of genus 1 for which a combinatorial proof is given in [2], we give here another proof.

Corollary 4.2 The quotient of a toroidal diagram by the group generated by a non trivial automorphism ψ is a planar quasi-diagram. Moreover such ψ satisfies one of the following conditions :

• (A) ψ is of order 2 and s + χ(ψ) = 3

• (B) ψ is of order 3 and χ(ψ) = 2

• (C) ψ is of order 4 and χ(ψ) = 1

• (D) ψ is of order 6 and χ(ψ) = 0

Proof : Let α be a diagram of genus 1, and let ψ be an automorphism of prime order p > 2 of α. Then the automorphisms ψ, ψ^{2}, …, ψ^{p−1} fix the same number f of faces of α. Since for an automorphism whose order is odd we have s = 0, by (RH) we get :

1 = (2γ − 1)p + f(p − 1)

This implies γ = 0 and

p = \frac{f + 1}{f − 1}

since it was supposed p ≠ 2 we get p = 3 and f = 2 which is case (B).

We have thus proved that the only primes dividing the order of an automorphism of a toroidal diagram are 2 and 3, we now prove that an automorphism of a toroidal diagram has an order q ≠ 9, similar arguments give q ≠ 8 and q ≠ 12 so that the possible orders for a non trivial automorphism are 2, 3, 4, 6. Note that if the order of ψ is 2, then (RH) gives s + χ(ψ) = 3 which is case (A).

If ψ is an automorphism of order 9 of a diagram α, then ψ^{3} and ψ^{6} have order 3 hence χ(ψ^{3}) = χ(ψ^{6}) = 2. Let f = χ(ψ) it is also the number of faces fixed by ψ^{2}, ψ^{4}, ψ^{5}, ψ^{7}, ψ^{8}, and (RH) gives : 1 = −9 + 6f + 4, so f = 1. But 9 divides the number n of chords; by the genus formula the number of faces is n − 1 and since one of them is fixed by ψ, 3 divides n − 2, a contradiction.

To end the proof we have to consider the automorphisms of order 4 and 6. If ψ is of order 4, then ψ^{2} is of order 2 and 2s + χ(ψ^{2}) = 3, by (RH) we obtain 5 = χ(ψ) + χ(ψ^{2}) + χ(ψ^{3}) + 2s, since ψ and ψ^{3} fix the same number of faces χ(ψ) = 1. If ψ is of order 6, then then ψ^{3} is of order 2 and 3s + χ(ψ^{3}) = 3, moreover ψ^{2} and ψ^{4} are of order 3 and fix 2 faces, by (RH) we obtain 7 = χ(ψ) + χ(ψ^{5}) + 7, giving χ(ψ) = 0. □

4.2 Weighted quotients

Consider a diagram α and a non trivial automorphism ψ, let \overline{α} be a quotient of α, any face of \overline{α} is the image by π of a set of faces of α. We call weight of a face, in the quotient \overline{α}, the number of faces of α of which it is the image. It is clear that the weight of a face divides the order of the automorphism group, and that the sum of the weights of the faces of \overline{α} is the number of faces of α. A face has weight 1 if and only if it is the image of a face fixed by the automorphisn ψ. A weighted quasi-diagram is a quasi-diagram β together with a function w assigning an integer to any face of β.

The weighted quasi-diagram (β, w) is a weighted quotient of α if \overline{α} = β and if for any face f of β, w(f) is the number of faces of α wich image by π is f, in that case α is a lifting of the weighted quasi-diagram (β, w). In the sequel, for a weighted quasi-diagram (β, w), s denotes the number of its isolated points and for any i > 0, f_{i} the number of its faces weighted i. The two corollaries above translate in terms of weighted quasi-diagrams :

Proposition 4.3 The weighted quotient of a planar diagram by an automorphism group of order k > 1 falls into one of the following classes:

• s = 0, one face has weight 1 and all others weight q

• s = 1, and all faces have weight 2

Proposition 4.4 The weighted quotient of a toroidal diagram by an automorphism group of order q > 1 falls into one of the following classes:

• (A) q = 2, ∀i ≠ 1, 2 : f_{i} = 0 and s + f_{1} = 3

• (B) q = 3, ∀i ≠ 1, 3 : f_{i} = 0, s = 0, f_{1} = 2

• (C) q = 4, ∀i ≠ 1, 2, 4 : f_{i} = 0, f_{1} = 1 and s + f_{2} = 1

• (D) q = 6, ∀i ≠ 2, 3, 6 : f_{i} = 0, f_{2} = 1, and s + f_{3} = 1

Proof : Remark that f_{1} is the number of fixed faces of ψ so that the cases q = 2 and q = 3 are immediate.

If q = 4, then β has one face weighted 1. Two situations arise :

1. β has an isolated point (ω_{i}), it is the image by π of two chords of α which are fixed by ψ^{2}. Since ψ^{2} has order 2, it fixes no more than these two chords and the face also fixed by ψ. Hence s = 1, f_{2} = 0.

2. β has no isolated point. The automorphism ψ^{2} of order 2 fixes 3 faces of α. Since only one of these three faces is also fixed by ψ, one face of β is the image by π of the other two ; thus s = 0, f_{2} = 1

If q = 6, ψ^{2} is of order 3, it fixes two faces of α, which image is a unique face of β ; hence f_{2} = 1. Now, two different situations are considered :

1. If β has an isolated point ω_{i}, it is obviously the image by π of 3 chords. These chords are fixed by ψ^{3}, and ω_{i} is the unique isolated point of β, (if β had more than one isolated point then the automorphism ψ^{3} of order 2, would fix more than 3 cells of α).

2. If β has no fixed point : ψ^{3} fixes 3 faces, and f_{3} = 1. □

4.3 Simplification lemmas.

In this paragraph we consider two operations which allow the computation of the number of diagrams of given genus having a given weighted quasi-diagram as quotient. The first one is the deletion of certain isolated chords, the second one is the transformation of isolated points.

Let (β, w) be a weighted quasi-diagram whose set of points is \{ω_{1}, …, ω_{k}\}, and let \overline{ζ} denote the cyclic permutation (ω_{1}, …, ω_{k}). An isolated chord of β is a chord connecting two consecutive points: (ω_{i}, ω_{i+1}), note that such a chord determines a face of length 1,namely the cycle (ω_{i}) of β\overline{ζ}.

The deletion of an isolated chord gives a weighted quasi-diagram (β′, w′) with one chord and one face less than β. All faces of β′ have the same degrees and weights as those of β except one which degree decreases by 1 from the corresponding face in β, thus β and β′ have the same genus. In what follows, when (β, w) is the weighted quotient of a diagram α by an automorphism of order q we will say that α is a q−lifting of β.

Lemma 4.5 Let (β, w) be a weighted quasi-diagram with n > 1 chords and an isolated chord determining a face of length 1 weighted q. Then (β, w) has as many q−liftings as (β′, w′), moreover to any lifting of (β, w) corresponds a lifting of (β′, w′) with the same genus.

Proof:

If the face (ω_{i}) is weighted q then in any q−lifting α of (β, w) the q faces of α which are liftings of ω_{i} are all of length 1 since π^{−1}i has q elements. Hence α has q isolated chords, deleting them gives a diagram α′ which is a q−lifting of (β′, w′) whose genus is the same as that of α. □

Note that if β has only one chord and no isolated point the above lemma is not applicable since the deletion of this chord would not give a quasi-diagram.

The second operation is the elimination of isolated points. Let β be a weighted quasi-diagram on Ω = {ω_{1}, …, ω_{m}}, assume ω_{i} is an isolated point of β, and let q be an even number, a q−simplification of β consists in inserting a new point ω′ between ω_{i} and ω_{i+1}, joining ω_{i} and ω′ by a chord, and assigning weight q/2 to the new face {ω_{i}}, then renaming all points ω′, ω_{i+1}, … ω_{m} in order to obtain a quasi-diagram with points numbered ω_{1}, …, ω_{m}, ω_{m+1}.

Lemma 4.6 A weighted quasi-diagram (β, w) with isolated point ω_{i} admits as many q-liftings as the weighted quasi-diagram (β′, w′) obtained from β by q−simplification of ω_{i}, moreover to any lifting of (β, w) corresponds a lifting of (β′, w′) with the same genus.

Proof : Denote {ω_{i}, ω′} the new chord in β′, so that we do not take in account the renaming of the points. Let α be a q-lifting of β ; we have for any i of π^{−1}ω_{i}, αi = i + kq/2 ; but on π^{−1}{ω_{i}, ω′}, it is easy to check that β′ admits a unique k-lifting α′ such that α′i = i′ + kq/2 and α′i′ = i + kq/2 ; in other words, while the q-lifting of ω_{i} gives q/2 chords, that of {ω_{i}, ω′} gives q chords. □

A useful consequence of these lemmas is that we can restrict the determination of the number of liftings to diagrams with no isolated points and no isolated chords.

5 Planar and toroidal diagrams.

5.1 Number of planar diagrams

The following result gives as an immediate corollary the number of non-isomorphic planar diagrams.

Proposition 5.1 Let (β, w) be a weighted planar quasi-diagram such that either s = 0, one face has weight 1 and all others weight q or s = 1, and all faces have weight 2. Then (β, w) has exactly one lifting which is a planar diagram.

Proof : A planar diagram with n > 1 chords has at least 2 isolated chords. Lemma 4.5 is applicable if one of these chords determines a face with weight q. Hence by successive deletions of chords there are two quasi-diagrams to consider : β_{1} = (ω_{1}, ω_{2}) where one face has weight 1, the other weight q and β_{2} = (ω_{1}) with q = 2. It is immediate that each one has a unique q−lifting namely : α_{1} = (1, 2)(3, 4) … (2q − 1, 2q) and α_{2} = (1, 2). □

Corollary 5.2 [9][12] The number p_{n}^{∗} of non isomorphic planar diagrams with n edges is given by :

1. if n is even

\frac{1}{2n}[p_{n} + ∑_{k≠n,k|n} ϕ(\frac{n}{k})(k + 1)p_{k}]

2. if n is odd

\frac{1}{2n}[p_{n} + np_{\frac{n−1}{2}} + ∑_{k≠n,k|n} ϕ(\frac{n}{k})(k + 1)p_{k}]

where p_{m} is the Catalan number \frac{(2m)!}{m!(m+1)!}

Proof : Denote by P the family of planar diagrams, we apply Lemma 3.1. A classical result is that

p_{n} = \frac{(2n)!}{n!(n + 1)!}

If n is even a diagram of P_{n} cannot have an automorphism of order 2 fixing exactly one chord, hence ρ_{P}(n, k) is the number of weighted planar diagrams with one face weighted 1 and all others weighted n/k. Since the number of faces of a planar diagram with k/2 chords is k/2 + 1 we obtain ρ_{P}(n, k) = 0 if k is odd and ρ_{P}(n, 2ℓ) = (ℓ + 1)p_{ℓ}

If n is odd we have to add to ρ_{P}(n, n − 1/2 + 1) the number of planar quasi-diagrams with a single isolated point and n − 1/2 chords. There are n possible locations where to add an isolated point in a diagram with n − 1/2 chords giving the result. □

5.2 Toroidal liftings

In this section, we prove :

Proposition 5.3 Any weighted quasi-diagram β belonging to one of the classes A, B, C, D of proposition 4.4 has a unique toroidal q-lifting.

In order to prove this Proposition we use two lemmas. In these lemmas (β, w) is a weighted quasi-diagram on Ω_{2m} and α a lifting of (β, w)

Lemma 5.4 Let c = {ω_{i}, ω_{i+1}} be an isolated chord of β. If α is a 2-lifting then it is uniquely determined on π^{−1}ω_{i} = {i, 2m + i} and π^{−1}ω_{i+1} = {i + 1, 2m + i + 1}.

Proof : Consider the face (ω_{i}) of β ; its weight is either 1 or 2 since q = 2. If the weight is 2 then from lemma 4.5 we have α(i) = i + 1 and α(2m + i) = 2m + i + 1. Now if the weight is 1, α(i) cannot be i + 1 ; hence it must be 2m + i + 1 and α(i + 1) = 2m + i. □

Lemma 5.5 Let {ω_{a}, ω_{b}} be a face of degree 2 and weight q of β. Then for any i in π^{−1}(ω_{a}) we have

α(i + 1) = α(i) − 1

Proof: Since the face is of weight q, then i is in a face of degree 2 of α, hence

ζαζ(i) = α(i)

and

α(i + 1) + 1 = α(i). □

We now go back to the proof of Proposion 5.3. Let f_{d,w} denote the number of faces of degree d, and weight w of a quasi-diagram ; it is easy to check that if β is a quasi-diagram of A, B, C or D, then after deletion of isolated chords and simplification of isolated points we obtain a diagram with m chords belonging to one of the following classes respectively (where f_{d,w} = 0 if not explicitely stated) :

1. A′ :

(a) A′_{1} : f_{1,1} = 3, f_{3,2} = 1, f_{2,2} = m − 3

(b) A′_{2} : f_{1,1} = 2, f_{2,1} = 1, f_{2,2} = m − 2

2. B′ : f_{1,1} = 2, f_{2,3} = m − 1

3. C′ : f_{1,1} = 1, f_{1,2} = 1, f_{2,4} = m − 1

4. D′ : f_{1,3} = 1, f_{1,2} = 1, f_{2,6} = m − 1

2 _{2} _{2} _{1}_{1}_{2}_{2}_{1}  _{ω_{1}}_{ω_{2}}_{ω_{m}}_{ω_{m+1}}  _{ω_{2m}}_{2}_{2}_{2}_{1}  _{1}_{2}_{2}_{1} _{2}_{2}  _{ω_{a}} _{ω_{1}}  _{ω_{2m}}_{ω_{i}}_{ω_{b}}  _{ω_{j}}  _{3} _{3} _{3} _{1}_{3}_{3}_{3}_{1}_{4} _{4} _{4} _{2}_{4}_{4}_{4}_{1}  _{6} _{6} _{6} _{3}_{6}_{6}_{6}_{2} A′_{1}  A′_{2}  B′ C′  D′

Figure 3: The different classes A′_{1}, A′_{2}, B′, C′, D′.

We have to prove that the diagrams of these classes have a unique toroidal lifting. First, note that all the weighted diagrams of A′_{2}, B′, C′ and D′ have the same form, namely

β = (ω_{1}, ω_{2m})(ω_{2}, ω_{2m−1}) … (ω_{m}, ω_{m+1})

We have 5 situations to examine which are represented Figure 3.

1. If β ∈ A′_{1}, then it can be written :

β = (ω_{1}, ω_{2m})(ω_{2}, ω_{2m−1}) … (ω_{a}, ω_{2m−a+1})(ω_{a+1}, ω_{b})(ω_{a+2}, ω_{b−1}) … (ω_{i}, ω_{i+1})(ω_{b+1}, ω_{2m−a})

(ω_{b+2}, ω_{2m−a−1}) … (ω_{j}, ω_{j+1})

The faces {ω_{m}}, {ω_{i}} and {ω_{j}} have weight 1 ; all other faces except {ω_{a}, ω_{b}, ω_{m−a}} have weight 2 and degree 2. From lemma 5.4 we have α1 = m, αi = m + i + 1 and αj = m + j + 1 ; and by applying inductively lemma 5.5, we obtain αa = m − a + 1, αb = m + a + 1 and α(b + 1) = 2m − a. Hence we find two faces of degree 3 : {a, b + m, m − a} and {a + m, b, 2m − a}, and α is uniquely determined.

2. β ∈ A′_{2} : the faces \{ω_{m}\} and \{ω_{\frac{m}{2}} \} have weight 1 ; so has the face \{ω_{i}, ω_{m−i}\}. By lemma 5.4 and 5.5 we find easily that αi = m − i + 1 and α(i + 1) = 2m − i, while α(m + i) = 2m − i + 1 and α(m + i + 1) = m − i ; giving the face {i, 2m − i, m + i, m − i}.

3. β ∈ B′ : the faces (ω_{m}) and (ω_{\frac{m}{2}} ) have weight 1 ; then αm must be one element of π^{−1}ω_{1}, that is either 1, or m + 1, or 2m + 1. Moreover, \{m, 2m, 3m\} must be a face of α, as well as \{\frac{m}{2}, \frac{3m}{2}, \frac{5m}{2}\} ; hence αm cannot be m + 1, thus it is either 1 or 2m + 1. If it is 1, then (m, 2m, 3m) is an orbit of αζ ; but by lemma 5.5, we have α2 = m − 1, α3 = m − 2 … α(\frac{m}{2}) = m − (\frac{m}{2} − 1) = \frac{m+2}{2} ; but (\frac{m}{2}) is then an orbit of αζ, which does not fit. Thus αm = 2m + 1 ; then one verifies that αζ = (m, 3m, 2m)(1, 2m − 1)(2, 2m − 2) … (\frac{m}{2}, \frac{5m}{2}, \frac{3m}{2}).

4. β ∈ C′ : suppose \{ω_{m}\} is the face of weight 2, and \{ω_{\frac{m}{2}} \} the face of weight 1. Clearly, m must belong to a face of α of degree 2, if αm = m+1 then {m} is a face, if αm = 1 then {m, 2m, 3m, 4m} is a face, as well as if αm = 2m + 1 . Then αm = 3m + 1, in that case on π^{−1}ω_{m} we have αζ = (m, 3m)(2m, 4m) ; then, inductively applying to lemma 5.5, we find α = (1, 2m)(2, 2m − 1) … (\frac{m}{2}, \frac{3m+2}{2}) and one verifies that, on π^{−1}ω_{\frac{m}{2}} , αζ has a unique cycle (\frac{m}{2}, \frac{7m}{2}, \frac{5m}{2}, \frac{3m}{2}).

5. β ∈ D′ : suppose \{ω_{m}\} is the face of weight 2, and \{ω_{\frac{m}{2}} \} that of weight 3. Thus m must belong to a face of degree 3 ; hence αm ≠ m + 1. Now if αm = 1, then {m, 2m, 3m, 4m, 5m} is an orbit of αζ as well as if αm = 2m + 1. If αm = 4m + 1 then {m, 4m} is a face of α. If αm = 5m + 1 then we find a face of degree 3 : {m, 3m, 5m} ; but, applying inductively lemma 5.5, one finds α = (1, 2m)(2, 2m − 1) … (\frac{m}{2}, \frac{3m+2}{2}), hence \{\frac{m}{2}, \frac{3m}{2}, \frac{5m}{2}, \frac{7m}{2}, \frac{9m}{2}, \frac{11m}{2}\} is a face of α; thus, the only possible choice is αm = 3m + 1.

5.3 The number of toroidal diagrams

Denote by

u_{p} = \frac{(2p)!}{p!p!}

and define the numbers :

a_{2p} = \frac{p(4p − 1)}{6}u_{p} a_{2p+1} = \frac{p(4p + 2)}{3}u_{p}

b_{2p+1} = 0, b_{2p} = (2p − 1)u_{p−1}

c_{2p} = d_{2p} = pu_{p} c_{2p+1} = d_{2p+1} = (2p + 1)u_{p}

then we have:

Theorem 2 The number t_{n} of non isomorphic toroidal diagrams with n points is

t_{n}^{∗} = \frac{1}{2n}[t_{n} + a_{n} + 2b_{2n/3} + 2c_{n/2} + 2d_{n/3}]

where b_{u}, c_{u}, d_{u} are equal to 0 when u is not an integer.

Proof : The result follows from general formula of Lemma 3.1, where D = T the family of toroidal diagrams. By Proposition 5.4 ρ_{T} (n, k) is the number of weighted quasi-diagrams with m = \frac{2n}{k} points, in the classes A, B, C, D, we will show that these are enumerated by the numbers a_{m}, b_{m}, c_{m} and d_{m}.

The number of planar weighted quasi-diagrams on 2p points, 2q of which being isolated and f_{i} faces being weighted i (i= 1,2,3,4,6) is the product of the number of planar quasi-diagrams by a multinomial coefficients :

\binom{2p}{2q}C_{p−q}\binom{p − q + 1}{f_{1} f_{2} f_{3} f_{4} f_{6}}

The result is obtained for a_{2p} by setting f_{1} = 3, s = 0 and f_{1} = 1, s = 2, for b_{2p} by setting f_{1} = 2. For c_{2p} we have f_{1} = f_{2} = 1 and for d_{2p}, f_{2} = f_{3} = 1.

If m is odd (m = 2p + 1) then s must also be odd (s = 2q + 1), the number of planar weighted quasi-diagrams on 2p+1 points, 2q +1 of which being isolated and f_{i} faces weighted i (i= 1,2,3,4,6) is

\binom{2p + 1}{2q + 1}C_{p−q}\binom{p − q + 1}{f_{1} f_{2} f_{3} f_{4} f_{6}}

Hence we get a_{2p+1} by setting f_{1} = 2 then f_{1} = 0, we remark that b_{2p+1} = 0, and for c_{2p+1} and d_{2p+1} we have respectively f_{1} = 1 and f_{2} = 1.

The result follows since ϕ(2) = 1 and ϕ(3) = ϕ(4) = ϕ(6) = 2. □

See Annex I for the first values of t_{n}.

6 Maximal diagrams

In this section we consider diagrams of maximal genus, that is with one face. By Euler formula the genus g and the number n of chords of such a diagram satisfy the relation : n = 2g. The number of diagrams with n chords and one face and obtained by Walsh and Lehman [13], it is given by :

μ_{g} = \frac{(2n)!}{2^{n}(n + 1)!}  (2)

A quasi-diagram is also maximal if it has only one face. It is easy to check that inserting isolated points in a maximal diagram gives a maximal quasi-diagram. Hence the number of maximal quasidiagrams with m points is

∑_{u=0}^{t} \binom{4t + q}{4u + q}μ_{2(t−u)}

Remark also that the quotient of a maximal diagram is a maximal quasi-diagram, since the image in the quotient of the unique face is necessarily a unique face.

6.1 Main theorem

We wish to prove the following :

Theorem 3 Let β be a maximal quasi-diagram and α a diagram which is a lifting of β having an even number of chords, then α is a maximal diagram.

The proof of this result uses the techniques developped in [4]. We consider β a quasi-diagram with k points, and we suppose that α is a lifting of β with n chords, then k divides 2n and we set 2n = kq. We use a mapping λ of {1, 2, … 2n = kq} into the set of integers mod q :Z/qZ defined by :

λ(x) = ⌊\frac{x}{k}⌋

6.2 Useful lemmas

Lemma 6.1 Let β, α and λ be as above, denote by s the number of isolated points of β, then :

∑_{i=1}^{k} λ(αζ(i)) = \frac{sq}{2} + 2

Proof : Denote by ψ = ζ^{k} the automorphism of α giving β as quotient, by definition of ζ we have :

∑_{i=1}^{k} λ(αζ(i)) = ∑_{i=2}^{k+1} λ(α(i))

Remark that the image by π of the set {2, 3, …, k, k+1} is exactly {ω_{1}, ω_{2}, … ω_{k}}, let us consider an orbit of β {ω_{a}, ω_{b}} of length 2 and let i, j be two elements in {2, 3, … k, k + 1} such that π(i) = ω_{a}, π(j) = ω_{b}. Then there exist integers j and l such that :

α(i) = ψ^{l}(j)

since α and ψ commute we have :

α(j) = ψ^{−l}(i) = ψ^{q−l}(i)

hence

λ(α(i)) = λ(j) + l λ(α(j)) = λ(i) + q − l

and :

λ(α(i)) + λ(α(j)) = λ(i) + λ(j) mod(q)

Let now ω_{a} be a fixed point of β, then q is even and i such that π(i) = ω_{a} satisfies:

α(i) = \frac{kq}{2} + i

Hence :

λ(α(i)) = λ(i) + \frac{q}{2} mod(q)

Adding the contributions of the orbits of length 2 and those of length 1 we obtain :

∑_{i=2}^{k+1} λ(α(i)) = \frac{sq}{2} + ∑_{i=2}^{k+1} λ(i) mod(q)

And the result follows since there are only two values in the sum for which λ(i) ≠ 0, namely i = k and i = k + 1. □

Lemma 6.2 Let β be a maximal quasi-diagram with k points and α a lifting of β. Then the length of each face of α is a multiple of k and can be written :

(x_{1}, x_{2} … x_{k}, y_{1}, y_{2}, … y_{k}, …, z_{1}, z_{2}, …, z_{k})

where the image of {x_{1}, x_{2} … x_{k}} by π is {ω_{1}, ω_{2}, … ω_{k}} and :

∑_{i=1}^{k} λ(αζ(i)) = 1 + λ(y_{1}) − λ(x_{1})

Proof : For any x in {1, 2, … qk}, denote by i the integer such that :

1 ≤ i ≤ k and x = i mod(q)

then we show first that :

λ(αζ(x)) = λ(x) + λ(αζ(i)) − λ(i)

Since i and x are in the same orbit of ψ we have

x = ψ^{l}(i)

and ψ commuting with ζ and α gives :

αζ(x) = ψ^{l}αζ(i)

Applying λ we have :

λ(αζ(x)) = λ(αζ(i)) + l mod(q)

and

λ(x) = λ(i) + l mod(q)

and we obtain our first formula. In order to end the proof of the lemma we apply the preceding relation to x = x_{1}, x_{2}, … x_{k}, denoting i_{1}, i_{2}, … i_{k} the classes of x_{1}, x_{2}, … x_{k} in Z/qZ we get :

λ(x_{2}) = λ(x_{1}) + λ(αζ(i_{1})) − λ(i_{1})
λ(x_{3}) = λ(x_{2}) + λ(αζ(i_{2})) − λ(i_{2})
…
λ(x_{k}) = λ(x_{k−1}) + λ(αζ(i_{k−1})) − λ(i_{k−1})
λ(y_{1}) = λ(x_{k}) + λ(αζ(i_{k})) − λ(i_{k})

Adding these relations gives :

λ(y_{1}) = λ(x_{1}) + ∑_{j=1}^{k} λ(αζ(i_{j})) − ∑_{j=1}^{k} λ(i_{j})

But i_{1}, i_{2}, … i_{k} is a permutation of 1, 2, … k hence we have

λ(y_{1}) = λ(x_{1}) + ∑_{i=1}^{k} λ(αζ(i)) − ∑_{i=1}^{k} λ(i)

Since λ(i) = 0 for 1 ≤ i < k and λ(k) = 1 we obtain the result. □

6.3 Proof of the theorem

Let α be a lifting of a maximal quasi-diagram with k points such that kq is a multiple of 4. Then by lemma 6.2 a face of α can be written :

(x_{1}, x_{2}, … x_{k}, y_{1}, y_{2} … y_{k} …)

we have to prove that this is the only face of α or equivalently there exists an integer l relatively prime with q such that :

y_{1} = ψ^{l}(x_{1})

By lemma 6.1 and 6.2 we have :

λ(y_{1}) = λ(x_{1}) + 1 + \frac{a_{1}q}{2} mod(q)

hence

l = 1 + \frac{a_{1}q}{2} mod(q)

If a_{1} is even we obtain the result, if a_{1} is odd then q is even hence

l = 1 + a_{1} \frac{q}{2} mod(q)

hence q and l are relatively prime. □

From this theorem we obtain the following enumeration formula :

Proposition 6.3 The number μ_{g}^{∗} of non isomorphic maximal diagrams of genus g is given by :

μ_{g}^{∗} = \frac{1}{4g} [μ_{g} + ∑_{qk=4g} ϕ(q) ∑_{γ=0}^{k/4} \binom{k}{4γ}μ_{γ}q^{2γ} + ∑_{qk=4g} ϕ(q)q^{k/2}μ_{k/4}]

Where the first sum is restricted to the even values of q and the second to the odd values.

Proof: By lemma 3.1 we have

μ_{g}^{∗} = \frac{1}{4g} [μ_{g} + ∑_{qk=4g,q≠1} ϕ(q)ρ_{M}(k, q)]

where ρ_{M}(k, q) is the number of maximal diagrams which are q-liftings of quasi-diagrams on k points.

If q is odd, the number of liftings of a quasi-diagram β on k points is non zero if and only if β is a diagram, in that case it is q^{k/2}. By the main theorem, all these liftings are of maximal genus. Thus

ρ_{M}(k, q) = q^{k/2}μ_{k/4}

If q is even the number of liftings of a quasi-diagram β on m points with 2γ chords is q^{2γ}. Since there are \binom{k}{4γ}μ_{γ} such quasi-diagrams and all the liftings are of maximal genus this gives :

ρ_{M}(k, q) = ∑_{γ=0}^{k/4} q^{2γ}\binom{k}{4γ}μ_{γ}

And the result is obtained. □

ANNEX I : number of toroidal diagrams with n chords

1  0 7  87830 13  5202148 19  26509093710
2  1 8  3799 14  21733696 20  109128802274
3  3 9  1630 15  90493272 21  448548845132
4 11 10  69486 16 375691885 22 1841087857280
5 46 11 294350 17 1555771800 23 7547314086884
6 204 12 1240308 18 6428291934 24 30903958827664

ANNEX II : number of maximal diagrams by genus

\begin{matrix}g & M_{g}^{∗} & g & M_{g}^{∗} \\ 1 & 1 & 7 & 508233789579 \\ 2 & 4 & 8 & 352755124921122 \\ 3 & 131 & 9 & 324039613564554401 \\ 4 & 14118 & 10 & 380751174738424280720 \\ 5 & 2976853 & 11 & 557175918657122229139987 \\ 6 & 1013582110 & 12 & 993806827312044893602464496 \end{matrix}

References

[1] D. Bar-Natan, On the Vassiliev node invaraints, Topology 34 (1995), 423-472.

[2] L. Bessis, Harvey-Wiman hypermaps, Proceedings of Conference FPSAC94, Rutgers university (1994).

[3] J. Bétréma, R. Cori, A. Sossinsky, Diagrammes de cordes et courbes de Gauss, unpublished manuscript, Université Bordeaux1, (1994).

[4] G. Bianchi, R. Cori, Colorings of hypermaps and a conjecture of Brenner and Lyndon, Pacific J. of Math. 110 (1984), 41-48.

[4] R. Cori, Un code pour les graphes planaires et ses applications, Astérisque, 27 (1975).

[5] R. Cori, A. Machi, Maps, hypermaps and their automorphisms : a survey, I, II, III, Expo. Math. 10 (1992), 403-467.

[6] J. Harer, D. Zagier, The Euler characteristic of the moduli space of curves, Invent. Math. 85 (1986), 457-485.

[7] 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.

[8] G. Labelle, P. Leroux, Enumeration of plane trees according to their degrees distribution Discrete Math, 157 (1996), 227-240.

[9] V.A. Liskovets, Enumeration of non-isomorphic planar maps, Selecta Math. Soviet., 4, No 4, (1985), 303-323.

[10] A. Machi, The Riemann-Hurwitz formula for the centralizer of a pair of permutations , Arch. der Math. 42 (1984), 280-288.

[11] W.T. Tutte, A census of planar maps, Canad. J. Math. 15 (1963), 249-271.

[12] D. W. Walkup, The number of plane trees, Mathematika., 19, (1972), 200-204.

[13] T.R.S. Walsh, A.B. Lehman, Counting rooted maps by genus I, II & III, J. Comb. Theory (B) 13, 1972, 192-218 and 122-141 and (B) 18, 1975, 200-204.