C. R. Acad. Sci. Paris, t. 333, Série I, p. 155–160, 2001 Combinatoire/Combinatorics (Géométrie algébrique/Algebraic Geometry)

Démonstration combinatoire de la formule de Harer-Zagier

Bodo LASS

Lehrstuhl II für Mathematik, RWTH Aachen, 52056 Aachen, Allemagne Courriel : lass@math2.rwth-aachen.de

(Reçu le 11 décembre 2000, accepté le 13 juin 2001)

Résumé. On donne une démonstration combinatoire directe de la formule de Harer-Zagier sur les nombres ε_{g}(m) de manières d’obtenir une surface de Riemann de genre g par identification par paires des côtés d’un 2m-gone. Cette formule est la clé combinatoire nécessaire pour le calcul de la caractéristique d’Euler de l’espace de modules des courbes de genre g. La méthode ici développée reprend l’approche combinatoire imaginée par Harer et Zagier et évite d’utiliser l’intégration sur un ensemble gaussien de matrices aléatoires. Notre technique de démonstration repose sur l’énumération des arborescences et des circuits eulériens. ◯^{c} Académie des Sciences/Elsevier, Paris

A combinatorial proof of the Harer-Zagier formula

Abstract. We give a combinatorial and self-contained proof of the Harer-Zagier formula for the numbers ε_{g}(m) of ways of obtaining a Riemann surface of given genus g by identifying in pairs the sides of a 2m-gon. This formula was the key combinatorial fact needed for the calculation of the Euler characteristic of the moduli space of curves of genus g. The method developed here completes the original combinatorial approach imagined by Harer and Zagier and avoids using the integration over a Gaussian ensemble of random matrices. Our derivation is based upon the enumeration of arborescences and Euler circuits. ◯^{c} Académie des Sciences/Elsevier, Paris

Abridged English Version

Harer and Zagier asked in [4] for a combinatorial proof of the following theorem:

Theorem (Harer-Zagier). – Let ε_{g}(m) be the number of ways of obtaining an oriented surface of given genus g by one of the (2m − 1)!! := (2m)!/(2^{m}m!) possible gluings in pairs of the counterclockwisely oriented sides of a 2m-gon, such that two oppositely oriented arcs become an unoriented edge. Then we have for every N ∈ ℕ\{0} (m ∈ ℕ\{0} is fixed):

∑_{g=0}^{⌊m/2⌋} ε_{g}(m) · N^{m+1−2g} = ∑_{n=1}^{N} \binom{N}{n} · (2m − 1)!! · 2^{n−1} · \binom{m}{n−1}.

Proof (sketched). – Every gluing yields a multigraph G = (V, E) with |E| = m edges, some v := |V | = m + 1 − 2g vertices and with a directed Eulerian tour (the 2m-gon after the gluings);

Note présentée par Michèle VERGNE.

B. Lass

and

∑_{g=0}^{⌊m/2⌋} ε_{g}(m) · N^{m+1−2g} = ∑_{g=0}^{⌊m/2⌋} ε_{g}(m) · N^{v}

counts the number of colourations of its vertices with the colours 1, 2, …, N. However, every colouration is surjective onto some subset of {1, 2, …, N} of cardinality n, and it is sufficient to prove:

Theorem. – Let V = {1, 2, …, n} be given and let m ≥ n − 1 be fixed; b := n − 1, s := m − b. Then the number of (really different) directed Eulerian tours on all multigraphs G = (V, E) with |E| = m (undirected) edges is equal to

\frac{(2m)!}{2^{s} · s! · b!} = (2m − 1)!! · 2^{n−1} · \binom{m}{n − 1}.

Proof (sketched). – By the so-called BEST Theorem it is possible for every directed Eulerian tour to distinguish between b edges forming an arborescence a : V \r → V (r ∈ V) on the one hand and the other s supplementary edges on the other hand. Therefore, the desired number can be expressed with the help of the variables x_{1}, …, x_{n} as follows:

∑_{{i_{1}+...+i_{n}=b+2s \atop i_{1},...,i_{n}≥0}} ∂_{x_{1}}^{i_{1}} … ∂_{x_{n}}^{i_{n}} ∑_{r∈V} ∑_{a:V \r→V} [ ∏_{v∈V \r} x_{a(v)}] · [(x_{1} + … + x_{n})^{2}/2]^{s}/s!

= ∑_{{i_{1}+...+i_{n}=b+2s \atop i_{1},...,i_{n}≥0}} ∂_{x_{1}}^{i_{1}} … ∂_{x_{n}}^{i_{n}} [x_{1} + … + x_{n}]^{b} · [x_{1} + … + x_{n}]^{2s}/(2^{s}s!)

= \frac{(b + 2s)!}{2^{s}s!} ∑_{{i_{1}+...+i_{n}=b+2s \atop i_{1},...,i_{n}≥0}} 1 = \frac{(b + 2s)!}{2^{s}s!} · \binom{2b + 2s}{b}, q.e.d.

Remark. – With the help of one of the combinatorial proofs of the identity

∑_{r∈V} ∑_{a:V \r→V} ∏_{v∈V \r} x_{a(v)} = [x_{1} + … + x_{n}]^{b}

as well as of the BEST Theorem one easily gets the promised combinatorial proof.

1. Introduction

Démonstration combinatoire de la formule de Harer-Zagier

Considérons un 2m-gone convexe (régulier), orientons ses 2m côtés dans le sens inverse des aiguilles d’une montre et numérotons les de 1 à 2m suivant cette orientation. Si l’on identifie (i. e. si l’on colle) ces 2m arcs (i. e. les 2m côtés ainsi orientés) par paires de façon que deux arêtes d’orientations opposées forment une arête non-orientée, on obtient une surface de Riemann décomposée en cellules avec une 2-cellule (le 2m-gone), m 1-cellules (les arêtes collées) et v sommets. Chaque identification de deux arcs entraîne l’identification de leurs extrémités; a priori, il n’est pas évident de savoir combien de sommets différents on obtient après ces identifications. Le genre g de la surface est déterminé par la formule d’Euler: v − m + 1 = 2 − 2g ⇔ v + 2g = m + 1. De plus, on a les inégalités: g ≥ 0 ⇒ v ≤ m + 1 et v ≥ 1 ⇒ g ≤ m/2.

Il y a naturellement (2m − 1)!! := (2m)!/(2^{m}m!) identifications possibles. On désigne par ε_{g}(m) le nombre d’identifications qui conduisent à une surface orientée de genre g. Alors on a pour tout N ∈ ℕ\{0} (m ∈ ℕ\{0} étant fixé):

Formule de Harer-Zagier

∑_{g=0}^{⌊m/2⌋} ε_{g}(m) · N^{m+1−2g} = ∑_{n=1}^{N} \binom{N}{n} · (2m − 1)!! · 2^{n−1} · \binom{m}{n−1}.

Harer et Zagier ont commencé leur démonstration par la même approche combinatoire qui sera prise ici. Pour aboutir, cependant, ils ont dû utiliser l’intégration sur un ensemble gaussien de matrices aléatoires. La présente Note se veut une réponse à la suggestion faite dans leur article ([4], page 460): ^{⟨⟨} It would be nice to have a direct (geometrical/combinatorial) proof.^{⟩⟩}

On fait appel, en effet, à deux théorèmes combinatoires classiques qu’il est utile de reformuler et de redémontrer dans le présent contexte, à savoir le calcul des arborescences et le théorème dit BEST sur les circuits eulériens. Un troisième théorème est le chaînon essentiel de notre démonstration. On verra que le dernier paragraphe reprend l’argument combinatoire développé dans [4].

Signalons que Itzykson et Zuber [5] ont simplifié l’intégration sur les matrices aléatoires à l’aide des oscillateurs harmoniques et de la formule de Baker-Campbell-Hausdorff. Si l’on s’appuie, en revanche, sur les polynômes de couplages (voir [9], VI-34, remarque 21, ou [3], chapitre 1), on peut résoudre l’intégrale (3.5) de [5] directement, réduisant ainsi cette démonstration de moitié.

Jackson [6] a aussi démontré la formule de Harer-Zagier par un calcul sur les caractères du groupe symétrique, méthode qui a été ensuite reprise et simplifiée par Itzykson et Zuber [5] et Zagier [10].

2. Dénombrement des arborescences et des circuits eulériens

Soient n ∈ ℕ\{0} et V = {1, 2, …, n} un ensemble fini. Un élément r ∈ V ayant été fixé, on appelle arborescence de racine r une fonction acyclique a : V \r → V (de manière équivalente, une fonction a : V \r → V telle que, pour tout v ∈ V \r, il existe i ∈ {1, …, n − 1} avec a^{i}(v) = r, c’est-à-dire en itérant la fonction au plus n − 1 fois on arrive à la racine, voir [2] page 61). Pour mieux distinguer les arborescences des fonctions quelconques on va écrire a : V \r ⇝ V dans la suite. Soient x_{1}, …, x_{n} des variables. Posons a(x) := ∏_{v∈V \r} x_{a(v)}. Alors (voir [8], chapitre 5.3):

Théorème 1 (Cayley).

∑_{r∈V} ∑_{a:V \r⇝V} a(x) = (x_{1} + … + x_{n})^{n−1}.

Démonstration (Prüfer-Foata). – Il est naturel de coder une fonction a : V \r ⇝ V par la suite de ses n−1 valeurs prises: a(v_{1}), a(v_{2}), …, a(v_{n−1}). Pour v_{1} on peut prendre v_{1} := min [V \ a(V \r)]. Comme a′ := a|_{V \v_{1}} est encore une arborescence, on peut appliquer la même procédure à a′. On obtient ainsi une bijection entre arborescences a : V \r ⇝ V et suites de nombres a(v_{1}) ∈ V, …, a(v_{n−1}) ∈ V telle que a(x) = x_{a(v_{1})} · . . . · x_{a(v_{n−1})}, ce qui achève la démonstration.

Soit D = (V, A), A : V × V → ℕ, un multigraphe orienté, où A(u, v) désigne la multiplicité de l’arc (u, v) ∈ V ×V. Notons que A est un (multi)ensemble de cardinalité |A| = ∑_{(u,v)∈V ×V} A(u, v). Posons i(u, v) := u et t(u, v) := v (pour distinguer l’extrémité initiale et terminale de chaque arc) ainsi que d_{D}^{+}(v) := ∑_{u∈V} A(v, u) et d_{D}^{−}(v) := ∑_{u∈V} A(u, v) (pour les demi-degrés).

Un circuit eulérien de D est une bijection c : {1, 2, …, |A|} → A telle que t(c(k)) = i(c(k + 1)) pour tout k ∈ {1, 2, …, |A| − 1} et t(c(|A|)) = i(c(1)). Ce dernier sommet est appelé racine r du circuit eulérien c. En outre, pour tout k ∈ {1, 2, …, |A|}, l’arc c(k) s’appelle départ du sommet i(c(k)) et arrivée au sommet t(c(k)). Le nombre des arrivées de c à v ∈ V est égal à d_{D}^{−}(v), et d_{D}^{+}(v) est le nombre des départs de v. Naturellement, d_{D}^{+}(v) = d_{D}^{−}(v) pour tout v ∈ V est une condition nécessaire pour l’existence d’un circuit eulérien, condition qu’on supposera satisfaite dans tout ce qui suit.

Alors, soit c : {1, 2, …, |A|} → A un circuit eulérien de racine r ∈ V. Regardons pour tout v ∈ V \r le plus grand k ∈ {1, 2, …, |A|} tel que i(c(k)) = v ainsi que l’arc c(k). Ces arcs forment le graphe d’une fonction a : V \r → V, qui est même une arborescence, parce qu’on arrive bien à la racine par itération. Cette arborescence des ^{⟨⟨} derniers départs^{⟩⟩} de c est appelé arborescence-balai. Or, chaque circuit eulérien c a une arborescence-balai unique et fournit, pour tout v ∈ V, un ordre linéaire des autres arcs a ∈ A avec i(a) = v: l’ordre des autres départs de c. Réciproquement, étant donnés ces seuls ordres linéaires et l’arborescence-balai, alors on reconstruit c automatiquement. La bijection ainsi construite implique le théorème suivant (voir [8], théorème 5.6.2, ou [1], chapitre 11.3, théorème 8):

Théorème 2 (BEST). – Soit D = (V, A) tel que d_{D}^{+}(v) = d_{D}^{−}(v) pour tout v ∈ V, et soit r ∈ V fixé. Si ϵ(D, r) désigne le nombre des circuits eulériens de racine r de D et α(D, r) désigne le nombre des arborescences de racine r de D, alors:

ϵ(D, r) = α(D, r) · d_{D}^{+}(r)! ∏_{v∈V \r}(d_{D}^{+}(v) − 1)!.

Soit G = (V, E), E : V ∪ \binom{V}{2} → ℕ, un multigraphe non-orienté, où E(v) désigne le nombre de boucles autour de v ∈ V et où E({u, v}) désigne le nombre d’arêtes entre deux sommets distincts u et v. On peut considérer E comme un (multi)ensemble de cardinalité |E| = ∑_{v∈V} E(v) + ∑_{\{u,v\}∈\binom{V}{2}} E(\{u, v\}), et l’on pose d_{G}(v) := 2 · E(v) + ∑_{u∈V \v} E(\{u, v\}) pour les degrés.

Suivant la suggestion de Berge (voir [1], préface), un circuit eulérien de G = (V, E) est un circuit eulérien du multigraphe orienté G⃗ = (V, E⃗) obtenu à partir de G en remplaçant chaque arête (et boucle) de G par deux arcs d’orientations opposées, de sorte que |E⃗| = 2|E|. Puisque la condition d+ ; G⃗(v) = d− ; G⃗(v) pour tout v ∈ V est toujours satisfaite, G contient un circuit eulérien si et seulement si G est connexe (notons que les circuits eulériens de G ne sont pas ses cycles eulériens considérés par Euler dans le cadre des ^{⟨⟨} ponts de Königsberg^{⟩⟩}).

Le nombre minimal d’arêtes nécessaires pour que G soit connexe est égal à n − 1 (|V | = n), et, dans ce cas-là, G est connexe si et seulement s’il s’agit d’un arbre, ^{⟨⟨} transformé^{⟩⟩} en arborescence a : V \r ⇝ V en choisissant une racine r ∈ V. D’après la définition du monôme a(x) de degré n − 1 on a a(x) = x_{r}^{d_{G}(r)} ∏_{v∈V \r} x_{v}^{d_{G}(v)−1}, et le théorème 2 donne le nombre des circuits eulériens de racine r de G:

d_{G}(r)! ∏_{v∈V \r}(d_{G}(v) − 1)! = ∑_{{i_{1}+...+i_{n}=n−1 \atop i_{1},...,i_{n}≥0}} ∂_{x_{1}}^{i_{1}} … ∂_{x_{n}}^{i_{n}} a(x).

Dans le cas général, c’est-à-dire G = (V, E) connexe et m := |E| ≥ n − 1, chaque circuit eulérien de racine r de G définit b := n − 1 arêtes ^{⟨⟨} de base^{⟩⟩} par son arborescence-balai a : V \r ⇝ V d’une part et s autres arêtes supplémentaires d’autre part, b + s = m.

Deux circuits eulériens ne sont pas vraiment différents s’ils s’obtiennent l’un de l’autre en permutant les deux arcs d’une boucle ou en permutant les arêtes ou les boucles multiples (i. e. de multiplicité ≥ 2).

Théorème 3. – Soit V = {1, 2, …, n} et soit m ≥ n − 1 fixé. Alors le nombre des circuits eulériens (orientés) vraiment différents sur tous les multigraphes G = (V, E) avec |E| = m arêtes (non-orientés) est égal à

\frac{(2m)!}{2^{s} · s! · b!} = (2m − 1)!! · 2^{n−1} · \binom{m}{n − 1}.

Démonstration. – Codons les arêtes de base par a : V \r ⇝ V et les arêtes supplémentaires par E^{∗} : V ∪ \binom{V}{2} → ℕ, |E^{∗}| = s. D’après le théorème 2, le nombre des circuits eulériens vraiment différents du graphe obtenu (l’arborescence-balai étant choisi d’avance) est égal à

∑_{{i_{1}+...+i_{n}=b+2s \atop i_{1},...,i_{n}≥0}} ∂_{x_{1}}^{i_{1}} … ∂_{x_{n}}^{i_{n}} a(x) · ∏_{v∈V} \frac{(x_{v}^{2}/2)^{E^{∗}(v)}}{E^{∗}(v)!} ∏_{\{u,v\}∈\binom{V}{2}} \frac{(x_{u}x_{v})^{E^{∗}(\{u,v\})}}{E^{∗}(\{u, v\})!} ,

et il suffit de sommer cette expression sur toutes les fonctions E^{∗} : V ∪ \binom{V}{2} → ℕ avec |E^{∗}| = s et sur toutes les arborescences a : V \r ⇝ V (et sur r ∈ V). Mais la dernière sommation fait l’objet du théorème 1 et la première sommation donne

∑_{{E^{∗}:V ∪\binom{V}{2}→ℕ \atop |E^{∗}|=s}} ∏_{v∈V} \frac{(x_{v}^{2}/2)^{E^{∗}(v)}}{E^{∗}(v)!} ∏_{\{u,v\}∈\binom{V}{2}} \frac{(x_{u}x_{v})^{E^{∗}(\{u,v\})}}{E^{∗}(\{u, v\})!} = [(x_{1} + … + x_{n})^{2}/2]^{s}/s!.

Par conséquent, le nombre cherché est égal à

∑_{{i_{1}+...+i_{n}=b+2s \atop i_{1},...,i_{n}≥0}} ∂_{x_{1}}^{i_{1}} … ∂_{x_{n}}^{i_{n}} [x_{1} + … + x_{n}]^{b} · [x_{1} + … + x_{n}]^{2s}/(2^{s}s!)

= \frac{(b + 2s)!}{2^{s}s!} ∑_{{i_{1}+...+i_{n}=b+2s \atop i_{1},...,i_{n}≥0}} 1 = \frac{(b + 2s)!}{2^{s}s!} · \binom{2b + 2s}{b}, C.Q.F.D.

Remarque. – De manière plus combinatoire, ∂_{x_{1}}^{i_{1}} … ∂_{x_{n}}^{i_{n}} signifie qu’il faut choisir i_{1} fois x_{1} (dans un ordre linéaire déterminant les départs du circuit eulérien du sommet 1), i_{2} fois x_{2}, …, i_{n} fois x_{n}. Les choix sont effectués dans un des b+2s facteurs possibles, un choix parmi les premiers b facteurs contribuant au codage de l’arborescence et un choix parmi les derniers 2s facteurs contribuant au codage des arêtes supplémentaires.

3. Démonstration de la formule de Harer-Zagier

Toute identification des arcs du 2m-gone crée un multigraphe G = (V, E) avec |V | = v = m + 1 − 2g et |E| = m, muni d’un circuit eulérien (le 2m-gone aprés les identifications); et

∑_{g=0}^{⌊m/2⌋} ε_{g}(m) · N^{m+1−2g} = ∑_{g=0}^{⌊m/2⌋} ε_{g}(m) · N^{v}

compte le nombre des colorations quelconques de ses sommets avec les couleurs 1, 2, …, N. Cependant, chaque coloration n’utilise qu’un sous-ensemble de cardinalité n de l’ensemble des couleurs {1, 2, …, N} et crée un circuit eulérien sur un multigraphe avec m arêtes sur cet ensemble de sommets de cardinalité n. Puisque les circuits eulériens vraiment différents correspondent de manière bijective aux identifications des arcs du circuit (via les arêtes non-orientées) et aux marquages des sommets conformes aux identifications des arcs, la formule de Harer-Zagier est une conséquence directe du théorème 3.

Remerciements. En tout premier lieu, je voudrais remercier vivement D. Foata d’avoir rendu possible la rédaction de ce travail en m’invitant à l’IRMA à Strasbourg. Son aide et assistance sont au-delà de toute expression. Je remercie aussi Yu. Matiyasevich et V. Dietrich d’avoir rendu l’internet russe accessible pour moi: c’est dans le dernier chapitre du livre [7] que j’ai découvert le problème ouvert, qui est résolu dans cette Note.

Références bibliographiques

[1] Berge C., Graphes, Bordas, 1983.

[2] Foata D., Schützenberger M.-P., Théorie géométrique des polynômes eulériens, Lect. Notes in Math. 138, Springer-Verlag, 1970.

[3] Godsil C.D., Algebraic Combinatorics, Chapman & Hall, 1993.

[4] Harer J., Zagier D., The Euler Characteristic of the Moduli Space of Curves, Invent. math. 85 (1986) 457-485.

[5] Itzykson C., Zuber J.-B., Matrix Integration and Combinatorics of Modular Groups, Comm. Math. Phys. 134 (1990) 197-207.

[6] Jackson D.M., Counting Cycles in Permutations by Group Characters, with an Application to a Topological Problem, Trans. AMS 299 (1987) 785-801.

[7] Lando S.K., Proizvodyashchie funkcii, NMU.

[8] Stanley R., Enumerative Combinatorics, Volume II, Cambridge University Press, 1999.

[9] Viennot G., Une théorie combinatoire des polynômes orthogonaux généraux, Notes de conférences données à l’Université du Québec à Montréal, 1983.

[10] Zagier D., On the Distribution of the Number of Cycles of Elements in Symmetric Groups, Nieuw Archief voor Wiskunde Ser. IV 13 (1995) 489-495.