%-----------------------------------------------------------------------
% Beginning of article.tex
%-----------------------------------------------------------------------
%
% AMS-LaTeX 1.2 sample file for book proceedings, based on amsproc.cls.
%
\input amssymb.sty
\documentclass[12pt]{amsproc}
\usepackage{graphicx}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{xca}[theorem]{Exercise}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

%\numberwithin{equation}{section}

%First page headline in AmS Proceedings style 
%for S\'eminaire Lotharingien de Combinatoire
%--first part
%\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
%\def\thepage{}
%
%
\catcode`\@=11
\def\ps@firstpage{\ps@plain
  \def\@oddfoot{\normalfont\scriptsize \hfil\thepage\hfil
     \global\topskip\normaltopskip}%
  \let\@evenfoot\@oddfoot
  \def\@oddhead{\its S\'eminaire Lotharingien de
Combinatoire \bfs 51 \rms (2004), Article~B51a\hss}%
  \let\@evenhead\@oddhead % in case an article starts on a left-hand page
}
\catcode`\@=12

%    Absolute value notation
\newcommand{\abs}[1]{\lvert#1\rvert}

%    Blank box placeholder for figures (to avoid requiring any
%    particular graphics capabilities for printing this document).
\newcommand{\blankbox}[2]{%
  \parbox{\columnwidth}{\centering
%    Set fboxsep to 0 so that the actual size of the box will match the
%    given measurements more closely.
    \setlength{\fboxsep}{0pt}%
    \fbox{\raisebox{0pt}[#2]{\hspace{#1}}}%
  }%
}

\begin{document}


\title{Nombre de factorisations d'un grand cycle}

%    Information for first author
\author{Philippe Biane}
%    Address of record for the research reported here
\address{CNRS, D\'epartement de Math\'ematiques et Applications,
 \'Ecole Normale Sup\'erieure, 45, rue d'Ulm 75005 paris, FRANCE
}
\email{Philippe.Biane@ens.fr}
%    General info
\subjclass[2000]{Primary 05A15; Secondary 05E05}
\date{}


\def\abstractname{R\'esum\'e}
\begin{abstract}
On donne une d\'emonstration simple d'une formule de Goupil et Schaeffer
qui compte  le nombre de factorisations d'un cycle de longueur maximale dans
$S_n$ en produit de deux permutations de classes de conjugaisons donn\'ees.
\end{abstract}

\maketitle


Dans la suite on utilise les notations du livre 
de Macdonald \cite{M}.

 
Soit $c^n_{\lambda\mu}$ le nombre de factorisations dans $S_n$ 
d'un cycle de longueur $n$
en un produit de deux permutations de classes de conjugaison $\lambda$ et $\mu$.
 La th\'eorie des caract\`eres donne la formule 
 \begin{equation}\label{00}c^{\nu}_{\lambda\mu}=\frac{n!}{
z_{\lambda}z_{\mu}}\sum_{\rho\vdash n}\frac{
\chi_{\lambda}^{\rho}\chi_{\mu}^{\rho}\chi_{\nu}^{\rho}}{\chi^{\rho}_{1^n}}.
\end{equation}
pour le nombre de d\'ecompositions d'une permutation de classe $\nu$ en produit
de deux permutations de classes $\lambda$ et $\nu$. La somme porte sur les
partitions de $n$ et les $\chi^{\rho}$ sont les caract\`eres du groupe
sym\'etrique, tandis que $z_{\lambda}=\prod_i\alpha_i!\,i^{\alpha_i}$
si $\lambda=1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}$.

Lorsque $\nu=(n)$, un cycle de longueur maximale, on a $\chi_\nu^{\rho}=0$ sauf
si $\rho$ est une \'equerre, c'est-\`a-dire un diagramme de la forme
$1^r(n-r)$, et on obtient
\begin{equation}\label{01}
 c^n_{\lambda\mu}=\frac{n}{
z_{\lambda}z_{\mu}}\sum_{r=0}^{n-1}(-1)^rr!\,(n-1-r)!\,
\chi_{\lambda}^{1^r(n-r)}\chi_{\mu}^{1^r(n-r)}.
\end{equation}
qui est la formule (4) de \cite{GS}. Cet article se poursuit par une analyse 
combinatoire de cette formule, pour la transformer en une expression ne
contenant
que des termes positifs.
Nous allons suivre une voie plus alg\'ebrique et
introduire une fonction g\'en\'eratrice pour ces quantit\'es en
utilisant les fonctions sym\'etriques $p_{\lambda}$ (cf.\ \cite{M}). 
L'utilisation
de telles fonctions g\'en\'eratrices est un outil puissant dans ce genre de
probl\`eme, cf.\ par exemple \cite{J} pour des r\'esultats voisins.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
%\addtocounter{page}{1}
\markboth{\SMALL PHILIPPE BIANE}{\SMALL NOMBRE DE FACTORISATIONS D'UN GRAND
CYCLE}

On consid\`ere donc la fonction g\'en\'eratrice
$$\psi(x,y)=\sum_n\frac{1}{n}\sum_{\lambda,\mu\vdash n}
p_{\lambda}(x)p_{\mu}(y)c^n_{\lambda\mu}.$$
D'apr\`es (\ref{01}) elle est donn\'ee par
$$\psi(x,y)=\sum_n\sum_{r=0}^{n-1}(-1)^rr!\,(n-1-r)!\sum_{\lambda,\mu\vdash n}
\frac{p_{\lambda}(x)p_{\mu}(y)}{
z_{\lambda}z_{\mu}}
\chi_{\lambda}^{1^r(n-r)}\chi_{\mu}^{1^r(n-r)}.$$
D'apr\`es \cite[I. (7.6) et I.3 example 9]{M}, on a 
$$\psi(x,y)=\sum_n\sum_{r=0}^{n-1}(-1)^rr!\,(n-1-r)!\,
s_{(n-r-1|r)}(x)s_{(n-r-1|r)}(y).$$
Les $s_{\lambda}$ sont les fonctions de Schur, et $(a|b)=(a+1,1^b)$ suivant la
notation de Frobenius.
D'apr\`es \cite[I.3 example 14]{M}, on a 
$$\prod_i\frac{1+vx_i}{1-ux_i}=1+(u+v)\sum_{a,b\geq 0}s_{(a,b)}u^av^b.$$
Nous allons donner une repr\'esentation int\'egrale de cette expression en
utilisant l'identit\'e
$$\frac{1}{\pi}\int_{\mathbb C}u^k\bar u^le^{-|u|^2}\,du=\delta_{kl}\,k!.$$ 
On obtient 
\begin{eqnarray*}
\psi(x,y)&=&\frac{1}{\pi^2}\int_{\mathbb C}\int_{\mathbb C}
\left(\frac{\prod_i\frac{1-vx_i}{1-ux_i}-1}{u-v}\right)
\left(\frac{\prod_i\frac{1+\bar vy_i}{1-\bar uy_i}-1}{ \bar u+\bar
v}
\right)e^{-|u|^2-|v|^2}\,du\,dv\\
&=&\frac{1}{\pi^2}\int_{\mathbb C}\int_{\mathbb C}
\left(\frac{\exp\left(\sum_{r}\frac{u^r-v^r}{r}p_r(x)\right)-1}
{ u-v}\right)\\
&&\qquad\times
\left(\frac{\exp\left(\sum_{r}\frac{\bar u^r-(-\bar v)^r}{r}p_r(y)\right)-1}
{\bar u+\bar
v}\right)e^{-|u|^2-|v|^2}\,du\,dv.
\end{eqnarray*}
Faisons le changement de variables $u=a+b, v=a-b$.
L'int\'egrale ne converge pas, mais le d\'eveloppement en s\'erie des
$p_{\lambda}$ converge terme \`a terme, et ce changement de variable
est une fa\c con rapide d'obtenir des relations entre les
coefficients de ce d\'eveloppement.
On trouve
\begin{eqnarray*}
\psi(x,y)&=&\frac{2}{\pi^2}\int_{\mathbb C}\int_{\mathbb C}
\left(\frac{\exp\left(\sum_{r}\frac{(a+b)^r-(a-b)^r}{r}p_r(x)\right)-1}
{ 2b}\right)
\\ &&\quad\times
\left(\frac{\exp\left(\sum_{r}\frac{(\bar a+\bar b)^r-(\bar b-\bar a)^r}{
r}p_r(y)\right)-1}{2\bar a}\right)e^{-2|a|^2-2|b|^2}\,da\,db.
\end{eqnarray*}
Or le polyn\^ome $Q_r(a,b)=(a+b)^r-(a-b)^r$ 
a tous ses coefficients positifs, par
cons\'equent quand on d\'eveloppe cette expression en termes des
$p_{\lambda}(x)p_{\mu}(y)$ on trouve des coefficients positifs.
Plus pr\'ecis\'ement, si on note $$R_{\lambda}(a,b)=\frac{1}{b}
\prod_i\frac{
Q_{i}(a,b)^{\alpha_i}}{i^{\alpha_i}\alpha_i!}=\frac{1}{z_{\lambda}b}
\prod_iQ_{\lambda_i}(a,b)$$
pour $\lambda=1^{\alpha_1}2^{\alpha_2}\ldots$, qui est un polyn\^ome homog\`ene 
de degr\'e
$n-1$,  alors on a 
$$c^n_{\lambda,\mu}=\frac{n2^{-n-1}}{\pi^2}
\int_{\mathbb C}\int_{\mathbb C}
R_{\lambda}(a,b)R_{\mu}(\bar b,\bar
a)e^{-|a|^2-|b|^2}\,da\,db,$$
ou encore, en appelant $r_{\lambda}^{kl}$ le coefficient de $a^kb^l$ dans
$R_{\lambda}$, (qui est positif) on obtient l'expression
$$c^n_{\lambda,\mu}
=n2^{-n-1}\sum_{k,l}r_{\lambda}^{kl}r_{\mu}^{lk}k!\,l!,$$
 qui est \'equivalente \`a la formule de Goupil et Schaeffer.
 
\medskip
 Plusieurs questions naturelles sont soulev\'ees par le calcul pr\'ec\'edent.
 Tout d'abord on peut essayer de retrouver la formule plus g\'en\'erale d\^ue
 \`a Poulalhon et  Schaeffer \cite{PS}, qui compte des factorisations 
en un nombre
 arbitraire de facteurs, mais l'int\'egrale qu'on obtient contient plus de
 deux variables  et il ne
 semble pas qu'un simple changement de variable permette de la simplifier
 suffisamment. Une
 autre piste est d'essayer de compter les factorisations de permutations ayant
 deux cyles. Dans le cas de la 
 classe de conjugaison  $1^1(n-1)$ on
  peut mettre la fonction g\'en\'eratrice sous forme d'un int\'egrale double
  mais l'int\'egrand contient un terme polynomial de signe non constant, et je
  ne vois pas comment en tirer une expression avec des termes positifs.
\bibliographystyle{amsalpha}
\def\refname{Bibliographie}
\begin{thebibliography}{A}
\bibitem [GS]{GS}
A. Goupil, G. Schaeffer,
\textit{Factoring $N$-cycles and counting maps of given genus.} 
Eur. J. Combinatorics \textbf{19} (1998), 819--834.
\bibitem [J]{J} D. M. Jackson,\textit{
Counting cycles in permutations by group characters,
 with an application to a topological problem.} 
Trans. Amer. Math. Soc. \textbf{299} (1987), no.~2, 785--801.
\bibitem [M]{M} I. G. Macdonald, \textit{Symmetric functions and Hall
polynomials}, Second Edition, Oxford Univ. Press,  Oxford, 1995.
\bibitem[PS]{PS}D. Poulalhon, G. Schaeffer, \textit{ Factorizations of large 
cycles in the symmetric group.}
 Discrete Math. \textbf{254} (2002), no.~1--3, 433--458.
\end{thebibliography}

\end{document}