%%%%%%%%%%%%%%%%%%%%%%%%% %% FICHIER PLAIN TEX %% %%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%% %% COMMENTAIRES %% %%%%%%%%%%%%%%%%%%%% % % Pour les th\'eor\`emes, propositions, lemmes, % corollaires, assertions, conjectures, probl\`emes, % ... et d\'efinitions, en Fran\c{c}ais ou en Anglais, % les taper en "petites capitales" (small capitals) % et leurs textes en italique, sauf pour les % d\'efinitions o\`u il est en romain, avec, % \'eventuellement, l'objet ou le concept \`a % d\'efinir en italique. Les faire pr\'ec\'eder % par un "\medskip" et suivre par un "\smallskip". % Les remarques, exemples, cas etc... sont \`a % taper en italique et leurs textes en romain. % % Exemple : % % \medskip % % {\sc Th\'eor\`eme~2.1.~--~}{\it \'Enonc\'e du % th\'eor\`eme.} % % \smallskip % % {\it Remarque\/}~2.2.~--~}Texte de la remarque % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \magnification=1100 \overfullrule=0pt %%%%%%%%%%%%%%% %\catcode`@=11 %---> FOURTEENPOINT %\newfam\gothfam %\newfam\gothbfam %\newfam\bbfam %\newskip\ttglue %\def\twelvepoint{\def\rm{\fam0\twelverm}% %\textfont0=\fourteenrm \scriptfont0=\twelverm \scriptscriptfont0=\ninerm %\textfont1=\fourteeni \scriptfont1=\twelvei \scriptscriptfont1=\ninei %\textfont2=\fourteensy \scriptfont2=\twelvesy \scriptscriptfont2=\ninesy %\textfont3=\tenex \scriptfont3=\tenex \scriptscriptfont3=\tenex %\textfont\itfam=\fourteenit \def\it{\fam\itfam\fourteenit}% %\textfont\slfam=\fourteensl \def\sl{\fam\slfam\fourteensl}% %\textfont\ttfam=\fourteentt \def\tt{\fam\ttfam\fourteentt}% %\textfont\bffam=\fourteenbf \scriptfont\bffam=\twelvebf \scriptscriptfont\bffam=\ninebf % \def\bf{\fam\bffam\fourteenbf}% %\textfont\gothfam=\fourteeneufm \scriptfont\gothfam=\twelveeufm \scriptscriptfont\gothfam=\nineeufm % \def\goth{\fam\gothfam\fourteeneufm}% %\textfont\gothbfam=\fourteeneufb \scriptfont\gothbfam=\twelveeufb \scriptscriptfont\gothbfam=\nineeufb % \def\gthb{\fam\gothbfam\fourteeneufb}% %\textfont\bbfam=\fourteenbb \scriptfont\bbfam=\twelvebb \scriptscriptfont\bbfam=\ninebb % \def\bb{\fam\bbfam\fourteenbb}% %\tt\ttglue=0.8em plus .5em minus .3em %\normalbaselineskip=18pt %\setbox\strutbox=\hbox{\vrule height15pt depth6pt width0pt}% %\font\sc=cmcsc10 scaled\magstep2 %\normalbaselines\rm}%\fourteenpoint %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % MACRO % \font\eighttt=cmtt8 % \font\eightsl=cmsl8 % \font\eightex=cmex10 at 8pt %%%%%%%%%%%%%%%% %% FONT CMR %% %%%%%%%%%%%%%%%% % \font\fiverm=cmr5 % \font\sixrm=cmr6 \font\seventeenrm=cmr17 \font\fourteenrm=cmr12 at 14pt \font\twelverm=cmr12 \font\ninerm=cmr10 at 9pt \font\eightrm=cmr8 \font\sixrm=cmr10 at 6pt % \textfont0=\tenrm \scriptfont0=\sevenrm \scriptscriptfont0=\fiverm \def\rm{\fam0\tenrm} %%%%%%%%%%%%%%%% %% FONT CMM %% %%%%%%%%%%%%%%%% % % \font\sixi=cmmi6 % \font\eighti=cmmi8 % \font\ninei=cmmi9 % \font\twelvei=cmmi12 % \font\fourteeni=cmmi10 at 14pt % \font\teni=cmmi10 \font\seveni=cmmi7 \font\fivei=cmmi5 \textfont1=\teni \scriptfont1=\seveni \scriptscriptfont1=\fivei \def\mit{\fam1} \def\oldstyle{\fam1\teni} %%%%%%%%%%%%%%%%% %% FONT CMSY %% %%%%%%%%%%%%%%%%% % \font\fivesy=cmsy6 at 5pt \font\sixsy=cmsy6 \font\sevensy=cmsy7 \font\eightsy=cmsy8 \font\ninesy=cmsy9 \font\tensy=cmsy10 \font\twelvesy=cmsy10 at 12pt \font\fourteensy=cmsy10 at 14pt %%%%%%%%%%%%%%%%% %% FONT CMTI %% %%%%%%%%%%%%%%%%% % \font\nineit=cmti10 at 9pt \font\eightit=cmti8 \font\sevenit=cmti7 %%%%%%%%%%%%%%%%%%% %% FONT CMBFTI %% %%%%%%%%%%%%%%%%%%% % \font\eightbfti=cmbxti10 at 8pt \font\bfti=cmbxti10 \font\twelvebfti=cmbxti10 at 12pt \font\fourteenbfti=cmbxti10 at 14pt %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% FONT CMCSC (Petites capitales) %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \font\sc=cmcsc10 %%%%%%%%%%%%%%%%% %% FONT MSBM %% %%%%%%%%%%%%%%%%% \font\sixbboard=msbm7 at 6pt % \font\ninebb=msbm9 % msbm10 at 9pt % \font\eightbb=msbm8 % msbm10 at 8pt % \font\sixbb=msbm6 % msbm10 at 6pt % \font\sixbboard=msbm7 at 6pt % \font\tenbb=msbm10 \font\sevenbb=msbm7 \font\fivebb=msbm5 \newfam\bbfam \textfont\bbfam=\tenbb \scriptfont\bbfam=\sevenbb \scriptscriptfont\bbfam=\fivebb \def\bb{\fam\bbfam\tenbb} \let\oldbb=\bb \def\bb #1{{\oldbb #1}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% FONT EUFM (Gothique) %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \font\sixgoth=eufm5 at 6pt \font\eightgoth=eufm7 at 8pt % \font\tengoth=eufm10 \font\sevengoth=eufm7 \font\fivegoth=eufm5 \newfam\gothfam \textfont\gothfam=\tengoth \scriptfont\gothfam=\sevengoth \scriptscriptfont\gothfam=\fivegoth \def\goth{\fam\gothfam\tengoth} % %%%%%%%%%%%%%%%%% %% FONT CMBX %% %%%%%%%%%%%%%%%%% % % \font\eightbf=cmbx10 at 8pt \font\twelvebf=cmbx12 \font\fourteenbf=cmbx10 at 14pt % \font\ninebf=cmbx9 \font\eightbf=cmbx8 % \font\sevenbf=cmbx10 at 7pt \font\sixbf=cmbx5 at 6pt % \font\sixbf=cmbx5 % \font\fivebf=cmbx10 at 5pt \font\tenbf=cmbx10 \font\sevenbf=cmbx7 \font\fivebf=cmbx5 \newfam\bffam \textfont\bffam=\tenbf \scriptfont\bffam=\sevenbf \scriptscriptfont\bffam=\fivebf \def\bf{\fam\bffam\tenbf} % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% HAUT-DE-PAGE (EX. : AUTEUR COURANT ET TITRE COURANT) %% %% BAS-DE-BAGE %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newif\ifpagetitre \pagetitretrue \newtoks\hautpagetitre \hautpagetitre={\hfil} \newtoks\baspagetitre \baspagetitre={\hfil} \newtoks\auteurcourant \auteurcourant={\hfil} \newtoks\titrecourant \titrecourant={\hfil} \newtoks\hautpagegauche \hautpagegauche={\hfil\the\auteurcourant\hfil} \newtoks\hautpagedroite \hautpagedroite={\hfil\the\titrecourant\hfil} \newtoks\baspagegauche \baspagegauche={\hfil\tenrm\folio\hfil} \newtoks\baspagedroite \baspagedroite={\hfil\tenrm\folio\hfil} \headline={\ifpagetitre\the\hautpagetitre \else\ifodd\pageno\the\hautpagedroite \else\the\hautpagegauche\fi\fi } \footline={\ifpagetitre\the\baspagetitre \global\pagetitrefalse \else\ifodd\pageno\the\baspagedroite \else\the\baspagegauche\fi\fi } \def\nopagenumbers{\def\folio{\hfil}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% UN SEMBLANT DES GUILLEMETS FRANCAIS %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\og{\leavevmode\raise.3ex \hbox{$\scriptscriptstyle\langle\!\langle$~}} \def\fg{\leavevmode\raise.3ex \hbox{~$\!\scriptscriptstyle\,\rangle\!\rangle$}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% TRUC AVEC MACHIN AU-DESSUS ET BIDULE AU-DESSOUS %% %% (MODE MATHEMATIQUE) %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\build #1_#2^#3{\mathrel{\mathop{\kern 0pt #1} \limits_{#2}^{#3}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\scs{\scriptstyle} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% FLECHES HORIZONTALES ET VERTICALES AVEC TRUC %% %% AU-DESSUS ET MACHIN AU-DESSOUS (MODE MATH) %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\hfl[#1][#2][#3]#4#5{\kern -#1 \sumdim=#2 \advance\sumdim by #1 \advance\sumdim by #3 \smash{\mathop{\hbox to \sumdim {\rightarrowfill}} \limits^{\scriptstyle#4}_{\scriptstyle#5}} \kern-#3} \def\vfl[#1][#2][#3]#4#5% {\sumdim=#1 \advance\sumdim by #2 \advance\sumdim by #3 \setbox1=\hbox{$\left\downarrow\vbox to .5\sumdim {}\right.$} \setbox1=\hbox{\llap{$\scriptstyle #4$}\box1 \rlap{$\scriptstyle #5$}} \vcenter{\kern -#1\box1\kern -#3}} \def\Hfl #1#2{\hfl[0mm][12mm][0mm]{#1}{#2}} \def\Vfl #1#2{\vfl[0mm][12mm][0mm]{#1}{#2}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% DIAGRAMMES COMMUTATIFS %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newdimen\sumdim \def\diagram#1\enddiagram {\vcenter{\offinterlineskip \def\tvi{\vrule height 10pt depth 10pt width 0pt} \halign{&\tvi\kern 5pt\hfil$\displaystyle##$\hfil\kern 5pt \crcr #1\crcr}}} %% SYNTAXE %% $$ %% \diagram %% ... & & ... & \cr %% ... & & ... & \cr %% ................. %% ... & & ... & \cr %% \enddiagram %% $$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\def\Doteq{\build{=}_{\scriptscriptstyle\bullet}^{\scriptscriptstyle\bullet}} \def\Doteq{\build{=}_{\hbox{\bf .}}^{\hbox{\bf .}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% ESPACE VERTICAL EN MODE MATH %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\vspace[#1]{\noalign{\vskip #1}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%% %% ENCADREMENT %% %%%%%%%%%%%%%%%%%%% \def\boxit [#1]#2{\vbox{\hrule\hbox{\vrule \vbox spread #1{\vss\hbox spread #1{\hss #2\hss}\vss}% \vrule}\hrule}} \def\carre{\boxit[5pt]{}} %% INDIQUE LA FIN D'UNE PREUVE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \catcode`\@=11 \def\Eqalign #1{\null\,\vcenter{\openup\jot\m@th\ialign{ \strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil &&\quad\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$ \hfil\crcr #1\crcr}}\,} \catcode`\@=12 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\font\tengoth=eufm10 \font\tenbboard=msbm10 %\font\eightrm=cmr8 \font\eighti=cmmi8 %\font\eightsy=cmsy8 \font\eightbf=cmbx8 % \font\eighttt=cmtt8 \font\eightit=cmti8 % \font\eightsl=cmsl8 \font\eightgoth=eufm7 % \font\eightbboard=msbm7 \font\eightex=cmex10 at 8pt %\font\eightgoth=eufm7 \font\sevenbboard=msbm7 % \font\sixrm=cmr6 \font\sixi=cmmi6 %\font\sixsy=cmsy6 \font\sixbf=cmbx6 % \font\sixgoth=eufm5 at 6pt \font\sixbboard=msbm7 at 6pt %\font\fivegoth=eufm5 \font\fivebboard=msbm5 \vsize= 20.5cm \hsize=15cm \hoffset=3mm \voffset=3mm %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% DEBUT DE DEFINITIONS PROPRES A CE FICHIER %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\arti#1#2{\setbox50=\null\ht50=#1\dp50=#2\box50} \def\tend_#1^#2{\mathrel{ \mathop{\kern 0pt\hbox to 1cm{\rightarrowfill}} \limits_{#1}^{#2}}} \def\tendps{\tend_{n\to\infty}^{\hbox{p.s.}}} \def\lfq{\leavevmode\raise.3ex\hbox{$\scriptscriptstyle \langle\!\langle$}\thinspace} \def\rfq{\leavevmode\thinspace\raise.3ex\hbox{$\scriptscriptstyle \rangle\!\rangle$}} \font\msamten=msam10 \font\msamseven=msam7 \newfam\msamfam \textfont\msamfam=\msamten \scriptfont\msamfam=\msamseven \def\ams {\fam\msamfam\msamten} \def\hexnumber #1% {\ifcase #1 0\or 1\or 2\or 3\or 4\or 5 \or 6\or 7\or 8\or 9\or A\or B\or C\or D\or E\or F \fi} \mathchardef\leadsto="3\hexnumber\msamfam 20 \def\frac #1#2{{#1\over #2}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% FIN DE DEFINITIONS PROPRES A CE FICHIER %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% AUTEUR(S) COURANT(S) SUR PAGES PAIRES %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \auteurcourant{\eightbf B.~Lass \hfill} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% TITRE COURANT SUR PAGES IMPAIRES %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \titrecourant{\hfill\eightbf D\'emonstration combinatoire de la formule de Harer-Zagier} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% {\parindent=0pt\eightbf C. R. Acad. Sci. Paris, t.~333, S\'erie~I, p.~155--160, 2001 %%%%%%%%%%%%%%%%% %% RUBRIQUE(S) %% %%%%%%%%%%%%%%%%% Combinatoire/\hskip -.5mm{\eightbfti Combinatorics} (G\'eom\'etrie alg\'ebrique/\hskip -.5mm{\eightbfti Algebraic Geometry}) \vskip 1.5cm %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% TITRE IN EXTENSO EN FRAN\C{C}AIS %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% {\fourteenbf D\'emonstration combinatoire de la formule de Harer-Zagier } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% MENTION "NOTE PR\'ESENT\'EE PAR ... %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \parindent=-1mm\footnote{}{ Note pr\'esent\'ee par Mich\`ele V{\sixbf ERGNE.} } \vskip 15pt %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Pr\'enoms NOMS (DES AUTEURS) %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \noindent{\bf Bodo LASS} \vskip 6pt %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% ADRESSES DES AUTEURS ET COURRIEL OU E-MAIL %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% {\parindent=0mm Lehrstuhl II f\"{u}r Mathematik, RWTH Aachen, 52056 Aachen, Allemagne Courriel~: lass@math2.rwth-aachen.de \par} \medskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% MENTION "(RE\C{C}U LE ..., ACCEPT\'E LE ...)" %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% (Re\c{c}u le 11 d\'ecembre 2000, accept\'e le 13 juin 2001) } \vskip3pt \line{\hbox to 2cm{}\hrulefill\hbox to 1.5cm{}} \vskip3pt %%%%%%%%%%%%%%%%%% %% R\'ESUM\'E %% %%%%%%%%%%%%%%%%%% {\parindent=2cm\rightskip 1.5cm\baselineskip=9pt \item{\bf R\'esum\'e.~}{\eightrm On donne une d\'emonstration combinatoire directe de la formule de Harer-Zagier sur les nombres~$\scs \varepsilon_g(m)$ de mani\`eres d'obtenir une surface de Riemann de genre~$\scs g$ par identification par paires des c\^ot\'es d'un $\scs 2m$-gone. Cette formule est la cl\'e combinatoire n\'ecessaire pour le calcul de la caract\'eristique d'Euler de l'espace de modules des courbes de genre~$\scs g$. La m\'ethode ici d\'evelopp\'ee reprend l'approche combinatoire imagin\'ee par Harer et Zagier et \'evite d'utiliser l'int\'egration sur un ensemble gaussien de matrices al\'eatoires. Notre technique de d\'emonstration repose sur l'\'enum\'eration des arborescences et des circuits eul\'eriens.~\copyright~Acad\'emie des Sciences/Elsevier, Paris} \par} \vskip 10pt %%%%%%%%%%%%%%%%%%%%%%%% %% TITRE EN ANGLAIS %% %%%%%%%%%%%%%%%%%%%%%%%% {\parindent=2cm\rightskip 1.5cm {\bfti A combinatorial proof of the Harer-Zagier formula} \par} \vskip 10pt %%%%%%%%%%%%%%%% %% ABSTRACT %% %%%%%%%%%%%%%%%% {\parindent=2cm\rightskip 1.5cm\baselineskip=9pt \item{\bf Abstract.~}{\eightit We give a combinatorial and self-contained proof of the Harer-Zagier formula for the numbers~$\scs \varepsilon_g(m)$ of ways of obtaining a Riemann surface of given genus~$\scs g$ by identifying in pairs the sides of a $\scs 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~$\scs 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.~}{\eightrm\copyright~Acad\'emie des Sciences/Elsevier, Paris} \par} \vskip1.5pt \line{\hbox to 2cm{}\hrulefill\hbox to 1.5cm{}} \medskip \parindent=3mm \vskip 5mm %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% ABRIDGED ENGLISH VERSION %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \noindent {\bf Abridged English Version} \bigskip \noindent Harer and Zagier asked in~[4] for a combinatorial proof of the following theorem: \medskip {\sc Theorem~(Harer-Zagier).~--~} {\it Let $\varepsilon_g(m)$ be the number of ways of obtaining an oriented surface of given genus~$g$ by one of the $(2m-1)!! := (2m)!/(2^mm!)$ 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 \in {\bb N} \backslash \{0\}$ ($m \in {\bb N} \backslash \{0\}$ is fixed):} $$ \sum_{g=0}^{\lfloor m/2 \rfloor} \varepsilon_g(m) \cdot N^{m+1-2g} \; = \; \sum_{n=1}^{N} {N \choose n} \cdot (2m-1)!! \cdot 2^{n-1} \cdot \hbox{${m \choose n-1}$}. $$ \smallskip {\it 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); and $$ \sum_{g=0}^{\lfloor m/2 \rfloor} \varepsilon_g(m) \cdot N^{m+1-2g} \; = \; \sum_{g=0}^{\lfloor m/2 \rfloor} \varepsilon_g(m) \cdot N^v $$ counts the number of colourations of its vertices with the colours $1, 2, \dots, N$. However, every colouration is surjective onto some subset of $\{1,2,\dots,N\}$ of cardinality $n$, and it is sufficient to prove: \medskip {\sc Theorem.~--~} {\it Let $V = \{1,2,\dots,n\}$ be given and let $m \ge 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 \cdot s! \cdot b!} \; = \; (2m-1)!! \cdot 2^{n-1} \cdot {m \choose n-1}. $$ \smallskip {\it 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 \backslash r \to V$ ($r \in 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$, \dots, $x_n$ as follows: $$ \sum_{\scriptstyle i_1 + \dots + i_n = b+2s \atop \scriptstyle i_1, \dots, i_n \ge 0} \partial_{x_1}^{i_1} \dots \partial_{x_n}^{i_n} \quad \sum_{r \in V} \; \sum_{a: V \backslash r \to V} \Bigl[ \prod_{v \in V \backslash r} x_{a(v)} \Bigr] \cdot \Bigl[ (x_1 + \dots + x_n)^2/2 \Bigr]^s/s! $$ $$ = \quad \sum_{\scriptstyle i_1 + \dots + i_n = b+2s \atop \scriptstyle i_1, \dots, i_n \ge 0} \partial_{x_1}^{i_1} \dots \partial_{x_n}^{i_n} \quad \bigl[ x_1 + \dots + x_n \bigr]^b \cdot \bigl[ x_1 + \dots + x_n \bigr]^{2s}/(2^ss!) $$ $$ = \quad \frac{(b+2s)!}{2^ss!} \sum_{\scriptstyle i_1 + \dots + i_n = b+2s \atop \scriptstyle i_1, \dots, i_n \ge 0} 1 \quad = \quad \frac{(b+2s)!}{2^ss!} \cdot {2b+2s \choose b}, \quad \hbox{q.e.d.} $$ \bigskip \noindent {\it Remark.~--~} With the help of one of the combinatorial proofs of the identity $$ \sum_{r \in V} \; \sum_{a: V \backslash r \to V} \; \prod_{v \in V \backslash r} x_{a(v)} \quad = \quad \bigl[ x_1 + \dots + x_n \bigr]^b $$ as well as of the BEST Theorem one easily gets the promised combinatorial proof. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \vskip 6pt \centerline{\hbox to 2cm{\hrulefill}} \vskip 9pt %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%% %% TEXTE PRINCIPAL %% %%%%%%%%%%%%%%%%%%%%%%% \bigskip \noindent{\bf 1. Introduction} \medskip Consid\'erons un $2m$-gone convexe (r\'egulier), orientons ses $2m$ c\^ot\'es dans le sens inverse des aiguilles d'une montre et num\'erotons les de $1$ \`a $2m$ suivant cette orientation. Si l'on identifie (i. e. si l'on colle) ces $2m$ arcs (i. e. les $2m$ c\^ot\'es ainsi orient\'es) par paires de fa\c{c}on que deux ar\^etes d'orientations oppos\'ees forment une ar\^ete non-orient\'ee, on obtient une surface de Riemann d\'ecompos\'ee en cellules avec une 2-cellule (le $2m$-gone), $m$ 1-cellules (les ar\^etes coll\'ees) et $v$ sommets. Chaque identification de deux arcs entra\^{\i}ne l'identification de leurs extr\'emit\'es; a priori, il n'est pas \'evident de savoir combien de sommets diff\'erents on obtient apr\`es ces identifications. Le genre~$g$ de la surface est d\'etermin\'e par la formule d'Euler: $v-m+1 = 2-2g$ $\; \Leftrightarrow \;$ $v+2g = m+1.$ De plus, on a les in\'egalit\'es: $g \ge 0$ $\; \Rightarrow \;$ $v \le m+1 \;$ et $\; v \ge 1$ $\; \Rightarrow \;$ $g \le m/2.$ Il y a naturellement $(2m-1)!! := (2m)!/(2^mm!)$ identifications possibles. On d\'esigne par $\varepsilon_g(m)$ le nombre d'identifications qui conduisent \`a une surface orient\'ee de genre~$g$. Alors on a pour tout $N \in {\bb N} \backslash \{0\}$ ($m \in {\bb N} \backslash \{0\}$ \'etant fix\'e): \bigskip \noindent {\sc Formule de Harer-Zagier} $$ \sum_{g=0}^{\lfloor m/2 \rfloor} \varepsilon_g(m) \cdot N^{m+1-2g} \; = \; \sum_{n=1}^{N} {N \choose n} \cdot (2m-1)!! \cdot 2^{n-1} \cdot \hbox{${m \choose n-1}$}. $$ \medskip Harer et Zagier ont commenc\'e leur d\'emonstration par la m\^eme approche combinatoire qui sera prise ici. Pour aboutir, cependant, ils ont d\^u utiliser l'int\'egration sur un ensemble gaussien de matrices al\'eatoires. La pr\'esente Note se veut une r\'eponse \`a la suggestion faite dans leur article ([4], page 460): \lfq It would be nice to have a direct (geometrical/combinatorial) proof.\rfq On fait appel, en effet, \`a deux th\'eor\`emes combinatoires classiques qu'il est utile de reformuler et de red\'emontrer dans le pr\'esent contexte, \`a savoir le calcul des arborescences et le th\'eor\`eme dit BEST sur les circuits eul\'eriens. Un troisi\`eme th\'eor\`eme est le cha\^\i non essentiel de notre d\'emonstration. On verra que le dernier paragraphe reprend l'argument combinatoire d\'evelopp\'e dans~[4]. \medskip Signalons que Itzykson et Zuber~[5] ont simplifi\'e l'int\'egration sur les matrices al\'eatoires \`a l'aide des oscillateurs harmoniques et de la formule de Baker-Campbell-Hausdorff. Si l'on s'appuie, en revanche, sur les polyn\^omes de couplages (voir~[9], VI-34, remarque 21, ou [3], chapitre 1), on peut r\'esoudre l'int\'egrale (3.5) de~[5] directement, r\'eduisant ainsi cette d\'emonstration de moiti\'e. Jackson~[6] a aussi d\'emontr\'e la formule de Harer-Zagier par un calcul sur les caract\`eres du groupe sym\'etrique, m\'ethode qui a \'et\'e ensuite reprise et simplifi\'ee par Itzykson et Zuber~[5] et Zagier~[10]. \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Arborescences % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bigskip \noindent{\bf 2. D\'enombrement des arborescences et des circuits eul\'eriens} \medskip Soient $n \in {\bb N} \backslash \{0\}$ et $V = \{1,2,\dots,n\}$ un ensemble fini. Un \'el\'ement $r \in V$ ayant \'et\'e fix\'e, on appelle {\it arborescence} de racine $r$ une fonction acyclique $a: V \backslash r \to V$ (de mani\`ere \'equivalente, une fonction $a: V \backslash r \to V$ telle que, pour tout $v \in V \backslash r$, il existe $i \in \{1, \dots, n-1\}$ avec $a^i(v) = r$, c'est-\`a-dire en it\'erant la fonction au plus $n-1$ fois on arrive \`a la racine, voir~[2] page 61). Pour mieux distinguer les arborescences des fonctions quelconques on va \'ecrire $a: V \backslash r \leadsto V$ dans la suite. Soient $x_1, \dots, x_n$ des variables. Posons $ a({\bf x}) := \prod_{v \in V \backslash r} x_{a(v)}. $ Alors (voir~[8], chapitre 5.3): \medskip \noindent {\sc Th\'eor\`eme~1~(Cayley).} \quad $$ \sum_{r \in V} \; \sum_{a: V \backslash r \leadsto V} a({\bf x}) \; = \; (x_1+ \dots + x_n)^{n-1}. $$ \medskip {\it D\'emonstration (Pr\"ufer-Foata). -- } Il est naturel de coder une fonction $a: V \backslash r \leadsto V$ par la suite de ses $n-1$ valeurs prises: $a(v_1)$, $a(v_2)$, \dots, $a(v_{n-1})$. Pour $v_1$ on peut prendre $v_1 := \min \; [V \; \backslash \; a(V \backslash r)]$. Comme $a' := a|_{V \backslash v_1}$ est encore une arborescence, on peut appliquer la m\^eme proc\'edure \`a $a'$. On obtient ainsi une bijection entre arborescences $a: V \backslash r \leadsto V$ et suites de nombres $a(v_1) \in V$, \dots, $a(v_{n-1}) \in V$ telle que $a({\bf x}) = x_{a(v_1)} \cdot \dots \cdot x_{a(v_{n-1})}$, ce qui ach\`eve la d\'emonstration. \eject Soit $D = (V,A)$, $A: V \times V \to {\bb N}$, un multigraphe orient\'e, o\`u $A(u,v)$ d\'esigne la multiplicit\'e de l'arc $(u,v) \in V \times V$. Notons que $A$ est un (multi)ensemble de cardinalit\'e $|A| = \sum_{(u,v) \in V \times V} A(u,v).$ Posons $i(u,v) := u$ et $t(u,v) := v$ (pour distinguer l'extr\'emit\'e initiale et terminale de chaque arc) ainsi que $d_D^+(v) := \sum_{u \in V} A(v,u)$ et $d_D^-(v) := \sum_{u \in V} A(u,v)$ (pour les demi-degr\'es). Un {\it circuit eul\'erien} de $D$ est une bijection $c: \{1,2,\dots,|A|\} \to A$ telle que $t(c(k)) = i(c(k+1))$ pour tout $k \in \{1,2,\dots,|A|-1\}$ et $t(c(|A|)) = i(c(1))$. Ce dernier sommet est appel\'e {\it racine} $r$ du circuit eul\'erien $c$. En outre, pour tout $k \in \{1,2,\dots,|A|\}$, l'arc $c(k)$ s'appelle {\it d\'epart} du sommet $i(c(k))$ et {\it arriv\'ee} au sommet $t(c(k))$. Le nombre des arriv\'ees de $c$ \`a $v \in V$ est \'egal \`a $d_D^-(v)$, et $d_D^+(v)$ est le nombre des d\'eparts de $v$. Naturellement, $d_D^+(v) = d_D^-(v)$ pour tout $v \in V$ est une condition n\'ecessaire pour l'existence d'un circuit eul\'erien, condition qu'on supposera satisfaite dans tout ce qui suit. Alors, soit $c: \{1,2,\dots,|A|\} \to A$ un circuit eul\'erien de racine $r \in V$. Regardons pour tout $v \in V \backslash r$ le plus grand $k \in \{1,2,\dots,|A|\}$ tel que $i(c(k)) = v$ ainsi que l'arc $c(k)$. Ces arcs forment le graphe d'une fonction $a: V \backslash r \to V$, qui est m\^eme une arborescence, parce qu'on arrive bien \`a la racine par it\'eration. Cette arborescence des {\lfq derniers d\'eparts\rfq} de $c$ est appel\'e {\it arborescence-balai.} Or, chaque circuit eul\'erien $c$ a une arborescence-balai unique et fournit, pour tout $v \in V$, un ordre lin\'eaire des autres arcs $a \in A$ avec $i(a) = v$: l'ordre des autres d\'eparts de $c$. R\'eciproquement, \'etant donn\'es ces seuls ordres lin\'eaires et l'arborescence-balai, alors on reconstruit $c$ automatiquement. La bijection ainsi construite implique le th\'eor\`eme suivant (voir~[8], th\'eor\`eme 5.6.2, ou [1], chapitre 11.3, th\'eor\`eme 8): \medskip {\sc Th\'eor\`eme~2~(BEST).~--~} {\it Soit $D = (V,A)$ tel que $d_D^+(v) = d_D^-(v)$ pour tout $v \in V$, et soit $r \in V$ fix\'e. Si $\epsilon(D,r)$ d\'esigne le nombre des circuits eul\'eriens de racine $r$ de $D$ et $\alpha(D,r)$ d\'esigne le nombre des arborescences de racine $r$ de $D$, alors:} $$ \epsilon(D,r) = \alpha(D,r) \cdot d_D^+(r)! \prod_{v \in V \backslash r} (d_D^+(v)-1)!. $$ \bigskip Soit $G = (V,E)$, $E: V \cup {V \choose 2} \to {\bb N}$, un multigraphe non-orient\'e, o\`u $E(v)$ d\'esigne le nombre de boucles autour de $v \in V$ et o\`u $E(\{u,v\})$ d\'esigne le nombre d'ar\^etes entre deux sommets distincts $u$ et $v$. On peut consid\'erer $E$ comme un (multi)ensemble de cardinalit\'e $|E| \; = \; \sum_{v \in V} E(v) \; + \sum_{\{u,v\} \in {V \choose 2}} E(\{u,v\}),$ et l'on pose $d_G(v) \; := \; 2 \cdot E(v) \; + \sum_{u \in V \backslash v} E(\{u,v\})$ pour les degr\'es. \smallskip Suivant la suggestion de Berge (voir~[1], pr\'eface), un circuit eul\'erien de $G = (V,E)$ est un circuit eul\'erien du multigraphe orient\'e $\vec{G} = (V,\vec{E})$ obtenu \`a partir de $G$ en rempla\c cant chaque ar\^ete (et boucle) de $G$ par deux arcs d'orientations oppos\'ees, de sorte que $|\vec{E}| = 2|E|$. Puisque la condition $d_{\vec{G}}^+(v) = d_{\vec{G}}^-(v)$ pour tout $v \in V$ est toujours satisfaite, $G$ contient un circuit eul\'erien si et seulement si $G$ est connexe (notons que les circuits eul\'eriens de $G$ ne sont pas ses cycles eul\'eriens consid\'er\'es par Euler dans le cadre des {\lfq ponts de K\"onigsberg\rfq}). \smallskip Le nombre minimal d'ar\^etes n\'ecessaires pour que $G$ soit connexe est \'egal \`a $n-1$ ($|V| = n$), et, dans ce cas-l\`a, $G$ est connexe si et seulement s'il s'agit d'un arbre, {\lfq transform\'e\rfq} en arborescence $a: V \backslash r \leadsto V$ en choisissant une racine $r \in V$. D'apr\`es la d\'efinition du mon\^ome $a({\bf x})$ de degr\'e $n-1$ on a $a({\bf x}) = x_r^{d_G(r)} \prod_{v \in V \backslash r} x_v^{d_G(v)-1}$, et le th\'eor\`eme 2 donne le nombre des circuits eul\'eriens de racine $r$ de $G$: $$ d_G(r)! \prod_{v \in V \backslash r} (d_G(v)-1)! = \sum_{\scriptstyle i_1 + \dots + i_n = n-1 \atop \scriptstyle i_1, \dots, i_n \ge 0} \partial_{x_1}^{i_1} \dots \partial_{x_n}^{i_n} \quad a({\bf x}). $$ Dans le cas g\'en\'eral, c'est-\`a-dire $G = (V,E)$ connexe et $m:= |E| \ge n-1$, chaque circuit eul\'erien de racine $r$ de $G$ d\'efinit $b := n-1$ ar\^etes {\lfq de base\rfq} par son arborescence-balai $a: V \backslash r \leadsto V$ d'une part et $s$ autres ar\^etes suppl\'ementaires d'autre part, $b+s = m.$ \smallskip Deux circuits eul\'eriens ne sont pas {\it vraiment diff\'erents} s'ils s'obtiennent l'un de l'autre en permutant les deux arcs d'une boucle ou en permutant les ar\^etes ou les boucles multiples (i. e. de multiplicit\'e $\ge 2$). \bigskip {\sc Th\'eor\`eme~3.~--~} {\it Soit $V = \{1,2,\dots,n\}$ et soit $m \ge n-1$ fix\'e. Alors le nombre des circuits eul\'eriens (orient\'es) vraiment diff\'erents sur tous les multigraphes $G = (V,E)$ avec $|E| = m$ ar\^etes (non-orient\'es) est \'egal \`a} $$ \frac{(2m)!}{2^s \cdot s! \cdot b!} \; = \; (2m-1)!! \cdot 2^{n-1} \cdot {m \choose n-1}. $$ \medskip {\it D\'emonstration. -- } Codons les ar\^etes de base par $a: V \backslash r \leadsto V$ et les ar\^etes suppl\'ementaires par $E^*: V \cup {V \choose 2} \to {\bb N}$, $|E^*| = s$. D'apr\`es le th\'eor\`eme 2, le nombre des circuits eul\'eriens vraiment diff\'erents du graphe obtenu (l'arborescence-balai \'etant choisi d'avance) est \'egal \`a $$ \sum_{\scriptstyle i_1 + \dots + i_n = b+2s \atop \scriptstyle i_1, \dots, i_n \ge 0} \partial_{x_1}^{i_1} \dots \partial_{x_n}^{i_n} \quad a({\bf x}) \cdot \prod_{v \in V} \frac{(x_v^2/2)^{E^*(v)}}{E^*(v)!} \prod_{\{u,v\} \in {V \choose 2}} \frac{(x_ux_v)^{E^*(\{u,v\})}}{E^*(\{u,v\})!}, $$ et il suffit de sommer cette expression sur toutes les fonctions $E^*: V \cup {V \choose 2} \to {\bb N}$ avec $|E^*| = s$ et sur toutes les arborescences $a: V \backslash r \leadsto V$ (et sur $r \in V$). Mais la derni\`ere sommation fait l'objet du th\'eor\`eme 1 et la premi\`ere sommation donne $$ \sum_{\scriptstyle E^*: V \cup {V \choose 2} \to {\bb N} \atop \scriptstyle |E^*| = s} \prod_{v \in V} \frac{(x_v^2/2)^{E^*(v)}}{E^*(v)!} \prod_{\{u,v\} \in {V \choose 2}} \frac{(x_ux_v)^{E^*(\{u,v\})}}{E^*(\{u,v\})!} % = \quad \Bigl[ \sum_{v \in V} x_v^2/2 \; + \sum_{\{u,v\} \in {V \choose 2}} x_ux_v \Bigr]^s/s! \quad = \quad \Bigl[ (x_1 + \dots + x_n)^2/2 \Bigr]^s/s!. $$ Par cons\'equent, le nombre cherch\'e est \'egal \`a $$ \sum_{\scriptstyle i_1 + \dots + i_n = b+2s \atop \scriptstyle i_1, \dots, i_n \ge 0} \partial_{x_1}^{i_1} \dots \partial_{x_n}^{i_n} \quad \bigl[ x_1 + \dots + x_n \bigr]^b \cdot \bigl[ x_1 + \dots + x_n \bigr]^{2s}/(2^ss!) $$ $$ = \quad \frac{(b+2s)!}{2^ss!} \sum_{\scriptstyle i_1 + \dots + i_n = b+2s \atop \scriptstyle i_1, \dots, i_n \ge 0} 1 \quad = \quad \frac{(b+2s)!}{2^ss!} \cdot {2b+2s \choose b}, \quad \hbox{C.Q.F.D.} $$ \bigskip {\it Remarque.~--~} De mani\`ere plus combinatoire, $\partial_{x_1}^{i_1} \dots \partial_{x_n}^{i_n}$ signifie qu'il faut choisir $i_1$ fois $x_1$ (dans un ordre lin\'eaire d\'eterminant les d\'eparts du circuit eul\'erien du sommet~1), $i_2$ fois $x_2$, \dots, $i_n$ fois $x_n$. Les choix sont effectu\'es 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\^etes suppl\'ementaires. \eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Harer-Zagier % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \noindent{\bf 3. D\'emonstration de la formule de Harer-Zagier} \medskip Toute identification des arcs du $2m$-gone cr\'ee un multigraphe $G = (V,E)$ avec $|V| = v = m+1-2g$ et $|E| = m$, muni d'un circuit eul\'erien (le $2m$-gone apr\'es les identifications); et $$ \sum_{g=0}^{\lfloor m/2 \rfloor} \varepsilon_g(m) \cdot N^{m+1-2g} \; = \; \sum_{g=0}^{\lfloor m/2 \rfloor} \varepsilon_g(m) \cdot N^v $$ compte le nombre des colorations quelconques de ses sommets avec les couleurs $1, 2, \dots, N$. Cependant, chaque coloration n'utilise qu'un sous-ensemble de cardinalit\'e $n$ de l'ensemble des couleurs $\{1,2,\dots,N\}$ et cr\'ee un circuit eul\'erien sur un multigraphe avec $m$ ar\^etes sur cet ensemble de sommets de cardinalit\'e~$n$. Puisque les circuits eul\'eriens vraiment diff\'erents correspondent de mani\`ere bijective aux identifications des arcs du circuit (via les ar\^etes non-orient\'ees) et aux marquages des sommets conformes aux identifications des arcs, la formule de Harer-Zagier est une cons\'equence directe du th\'eor\`eme 3. \bigskip {\bf Remerciements.} En tout premier lieu, je voudrais remercier vivement D.~Foata d'avoir rendu possible la r\'edaction de ce travail en m'invitant \`a l'IRMA \`a Strasbourg. Son aide et assistance sont au-del\`a 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\'ecouvert le probl\`eme ouvert, qui est r\'esolu dans cette Note. \bigskip %%%%%%%%%%%%%%%%%%%%%%% %% BIBLIOGRAPHIE %% %%%%%%%%%%%%%%%%%%%%%%% \centerline{\bf R\'ef\'erences bibliographiques} \medskip {\baselineskip=9pt\eightrm \item{[1]}Berge C., Graphes, Bordas, 1983. \smallskip \item{[2]}Foata D., Sch\"utzenberger M.-P., Th\'eorie g\'eom\'etrique des polyn\^omes eul\'eriens, Lect.~Notes in Math.~138, Springer-Verlag, 1970. \smallskip \item{[3]}Godsil C.D., Algebraic Combinatorics, Chapman \& Hall, 1993. \smallskip \item{[4]}Harer J., Zagier D., The Euler Characteristic of the Moduli Space of Curves, Invent.~math.~85 (1986) 457-485. \smallskip \item{[5]}Itzykson C., Zuber J.-B., Matrix Integration and Combinatorics of Modular Groups, Comm.~Math.~Phys.~134 (1990) 197-207. \smallskip \item{[6]}Jackson D.M., Counting Cycles in Permutations by Group Characters, with an Application to a Topological Problem, Trans.~AMS 299 (1987) 785-801. \smallskip \item{[7]}Lando S.K., Proizvodyashchie funkcii, NMU. \smallskip \item{[8]}Stanley R., Enumerative Combinatorics, Volume II, Cambridge University Press, 1999. \smallskip \item{[9]}Viennot G., Une th\'eorie combinatoire des polyn\^omes orthogonaux g\'en\'eraux, Notes de conf\'erences donn\'ees \`a l'Universit\'e du Qu\'ebec \`a Montr\'eal, 1983. \smallskip \item{[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. \smallskip } \end