Séminaire Lotharingien de Combinatoire 51 (2004), Article B51a

Nombre de factorisations d’un grand cycle

Philippe Biane

Résumé. On donne une démonstration 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ées.

Dans la suite on utilise les notations du livre de Macdonald [M]. Soit c_{λμ}^{n} le nombre de factorisations dans S_{n} d’un cycle de longueur

n en un produit de deux permutations de classes de conjugaison λ et μ. La théorie des caractères donne la formule

(1)  c_{λμ}^{ν} = \frac{n!}{z_{λ}z_{μ}} ∑_{ρ⊢n} \frac{χ_{λ}^{ρ}χ_{μ}^{ρ}χ_{ν}^{ρ}}{χ_{1^{n}}^{ρ}} .

pour le nombre de décompositions d’une permutation de classe ν en produit de deux permutations de classes λ et ν. La somme porte sur les partitions de n et les χ^{ρ} sont les caractères du groupe symétrique, tandis que z_{λ} = ∏_{i} α_{i}! i^{α_{i}} si λ = 1^{α_{1}}2^{α_{2}} … n^{α_{n}}.

Lorsque ν = (n), un cycle de longueur maximale, on a χ_{ν}^{ρ} = 0 sauf si ρ est une équerre, c’est-à-dire un diagramme de la forme 1^{r}(n − r), et on obtient

(2)  c_{λμ}^{n} = \frac{n}{z_{λ}z_{μ}} ∑_{r=0}^{n−1}(−1)^{r}r! (n − 1 − r)! χ_{λ}^{1^{r}(n−r)}χ_{μ}^{1^{r}(n−r)}.

qui est la formule (4) de [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ébrique et introduire une fonction génératrice pour ces quantités en utilisant les fonctions symétriques p_{λ} (cf. [M]). L’utilisation de telles fonctions génératrices est un outil puissant dans ce genre de problème, cf. par exemple [J] pour des résultats voisins.

2000 Mathematics Subject Classification. Primary 05A15; Secondary 05E05.

On considère donc la fonction génératrice

ψ(x, y) = ∑_{n} \frac{1}{n} ∑_{λ,μ⊢n} p_{λ}(x)p_{μ}(y)c_{λμ}^{n}.

D’après (2) elle est donnée par

ψ(x, y) = ∑_{n} ∑_{r=0}^{n−1}(−1)^{r}r! (n − 1 − r)! ∑_{λ,μ⊢n} \frac{p_{λ}(x)p_{μ}(y)}{z_{λ}z_{μ}}χ_{λ}^{1^{r}(n−r)}χ_{μ}^{1^{r}(n−r)}.

D’après [M, I. (7.6) et I.3 example 9], on a

ψ(x, y) = ∑_{n} ∑_{r=0}^{n−1}(−1)^{r}r! (n − 1 − r)! s_{(n−r−1|r)}(x)s_{(n−r−1|r)}(y).

Les s_{λ} sont les fonctions de Schur, et (a|b) = (a + 1, 1^{b}) suivant la notation de Frobenius. D’après [M, I.3 example 14], on a

∏_{i} \frac{1 + vx_{i}}{1 − ux_{i}} = 1 + (u + v) ∑_{a,b≥0} s_{(a,b)}u^{a}v^{b}.

Nous allons donner une représentation intégrale de cette expression en utilisant l’identité

\frac{1}{π} ∫_{ℂ} u^{k}ū^{l}e^{−|u|^{2}} du = δ_{kl} k!.

On obtient

ψ(x, y) = \frac{1}{π^{2}} ∫_{ℂ} ∫_{ℂ} (\frac{∏_{i} \frac{1−vx_{i}}{1−ux_{i}} − 1}{u − v}) (\frac{∏_{i} \frac{1+v̄y_{i}}{1−ūy_{i}} − 1}{ū + v̄}) e^{−|u|^{2}−|v|^{2}} du dv

= \frac{1}{π^{2}} ∫_{ℂ} ∫_{ℂ} (\frac{exp (∑_{r} \frac{u^{r}−v^{r}}{r} p_{r}(x)) − 1}{u − v})

× (\frac{exp (∑_{r} \frac{ū^{r}−(−v̄)^{r}}{r} p_{r}(y)) − 1}{ū + v̄}) e^{−|u|^{2}−|v|^{2}} du dv.

Faisons le changement de variables u = a + b, v = a − b. L’intégrale ne converge pas, mais le développement en série des p_{λ} converge terme à terme, et ce changement de variable est une façon rapide d’obtenir des relations entre les coefficients de ce développement. On trouve

ψ(x, y) = \frac{2}{π^{2}} ∫_{ℂ} ∫_{ℂ} (\frac{exp (∑_{r} \frac{(a+b)^{r}−(a−b)^{r}}{r} p_{r}(x)) − 1}{2b})

× (\frac{exp (∑_{r} \frac{(ā+b̄)^{r}−(b̄−ā)^{r}}{r} p_{r}(y)) − 1}{2ā}) e^{−2|a|^{2}−2|b|^{2}} da db.

Or le polynôme Q_{r}(a, b) = (a + b)^{r} − (a − b)^{r} a tous ses coefficients positifs, par conséquent quand on développe cette expression en termes des p_{λ}(x)p_{μ}(y) on trouve des coefficients positifs. Plus précisément, si on note

R_{λ}(a, b) = \frac{1}{b} ∏_{i} \frac{Q_{i}(a, b)^{α_{i}}}{i^{α_{i}}α_{i}!} = \frac{1}{z_{λ}b} ∏_{i} Q_{λ_{i}}(a, b)

pour λ = 1^{α_{1}}2^{α_{2}} …, qui est un polynôme homogène de degré n − 1, alors on a

c_{λ,μ}^{n} = \frac{n2^{−n−1}}{π^{2}} ∫_{ℂ} ∫_{ℂ} R_{λ}(a, b)R_{μ}(b̄, ā)e^{−|a|^{2}−|b|^{2}} da db,

ou encore, en appelant r_{λ}^{kl} le coefficient de a^{k}b^{l} dans R_{λ}, (qui est positif) on obtient l’expression

c_{λ,μ}^{n} = n2^{−n−1} ∑_{k,l} r_{λ}^{kl}r_{μ}^{lk}k! l!,

qui est équivalente à la formule de Goupil et Schaeffer.

Plusieurs questions naturelles sont soulevées par le calcul précédent. Tout d’abord on peut essayer de retrouver la formule plus générale dûe à Poulalhon et Schaeffer [PS], qui compte des factorisations en un nombre arbitraire de facteurs, mais l’intégrale 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énératrice sous forme d’un intégrale double mais l’intégrand contient un terme polynomial de signe non constant, et je ne vois pas comment en tirer une expression avec des termes positifs.

Bibliographie

[GS] A. Goupil, G. Schaeffer, Factoring N-cycles and counting maps of given genus. Eur. J. Combinatorics 19 (1998), 819–834.

[J] D. M. Jackson, Counting cycles in permutations by group characters, with an application to a topological problem. Trans. Amer. Math. Soc. 299 (1987), no. 2, 785–801.

[M] I. G. Macdonald, Symmetric functions and Hall polynomials, Second Edition, Oxford Univ. Press, Oxford, 1995.

[PS] D. Poulalhon, G. Schaeffer, Factorizations of large cycles in the symmetric group. Discrete Math. 254 (2002), no. 1–3, 433–458.

CNRS, Département de Mathématiques et Applications, École Normale Supérieure, 45, rue d’Ulm 75005 paris, FRANCE

E-mail address: Philippe.Biane@ens.fr