Equations in S_{n} and Combinatorial Maps
Gilles Schaeffer
LaBRI, Université de Bordeaux I,
Algorithms Seminar
November 3, 1997
[summary by Dominique GouyouBeauchamps]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
This talk presents a joint work with Alain Goupil (LACIMUQAM, Montréal).
1 Counting Maps
A partition l = (l _{1},l_{2},... ,l_{k}) is a
finite nonincreasing sequence of positive integers l_{i} such
that l_{1}³...³l_{k}>0. The nonzero terms are called
the parts of l and the number k of parts is the length
of l, denoted l (l). We also write
l = 1^{a}_{1}2^{a}_{2}··· n^{a}_{n} when a_{i} parts
of l are equal to i (i=1,...,n). When the sum
l_{1}+l_{2}+... +l_{k}=n, we call n the weight of
l and we write l n or l =n. The conjugacy
classes C_{l} of the symmetric group S_{n} are indexed by partitions
of n which are called the cycle types of the permutations
sÎ C_{l}.
There exit relations between pairs of permutations and maps on oriented surfaces.
A map (S,G) on a compact oriented surface S without boundary is a graph
G together with an embedding of G into S such that connected components
of the complement S\ G of the embedding of G in S, called the
faces of the map, are homeomorphic to discs. Multiple edges are allowed
and our maps are rooted, i.e., one edge of G is distinguished. Two maps
(S,G) and (S',G') are isomorphic if there exits an orientationpreserving
homeomorphism f:S® S' such that f(G)=G'.
A map is bicolored if its vertices are colored in black or white so that
each edge is incident to one vertex of each color. A map is unicellular
if it has one face. The type of a bicolored unicellular map M with
n edges is a pair of partitions (l ,µ) whose parts give respective
degrees of black and white vertices of M.
Proposition 1 [see [3] for more details]
Bicolored unicellular maps of type (l ,µ) are maps on a compact
orientable surface of genus g which satisfy g=g(l ,µ). Moreover,
the number Bi(l ,µ) of bicolored unicellular maps of
type (l ,µ) with n edges is the number of pairs (s ,t)
such that s t =(1,2,... ,n), which is also the coefficient
c_{l ,µ}^{(n)} that we study below.
2 Equations in S_{n}
Following [7], let
z_{l}=Õ_{i}a_{i}!i^{a}_{i} for a partition
l = 1^{a}_{1}2^{a}_{2}··· n^{a}_{n}. Then
Example 1 The conjugacy class T of transpositions is T=C_{1}^{n2}_{2}
and T=()=n!/(n2)!2.
In this talk, we are interested with the general problem of
computing the number
C 

=

 
å(l^{1},... ,l^{m};p) 
 
of solutions (a_{1},... ,a_{m})Î C_{l}^{1}×...×
C_{l}^{m} of the equation a_{1}a_{2}··· a_{m}=p
where p is any fixed permutation of S_{n} and where
áa_{1},... ,a_{m}ñ acts transitively on {1,2,... ,n}.
Example 2 Factorization of any ncycle into transpositions
C 

= 
 
{ 
(t_{1},... ,t_{n1}) transpositions such that
t_{1}··· t_{n1}=(1,2,... ,n) 
} 
 
=n^{n2}. 
If aÎ C_{l} and a=t_{1}··· t_{k}, then we have
k³ nl (l)=å_{i=1}^{l (l)}(l_{i}1) and
parity of a is given by parity of nl (l). Thus
if a_{1}a_{2}··· a_{m}=p, we have the first necessary
condition for existence of solutions in
å(l^{1},... ,l^{m};p):

( 
nl (l^{i}) 
) 
º nl
(p)mod 2. 
If áa_{1},... ,a_{m}ñ acts transitively on
{1,2,... ,n}, the underlying graph is connected.
Example 3 t_{1}··· t_{m}=1. We need m=2n2 transpositions:
n1 transpositions to get an ncycle and one connected component,
and n1 transpositions to return to 1.
Proposition 2
Let (a_{1},... ,a_{m}) be in C_{l}^{1}×...×
C_{l}^{m}. If
áa_{1},... ,a_{m}ñ acts transitively and if
a_{1}··· a_{m}=1, then
å_{i=1}^{m} (nl (l^{i}))³ 2n2.
Definition 1
The genus of m partitions (l^{1},... ,l^{m}) of weight n
is the non negative integer g defined by the equation

( 
nl (l^{i}) 
) 
=2n2+2g. 
For non transitive systems, we want to compute the number
d 

=

½ ½ ½ ½ 


(l^{1},... ,l^{m};p) 
½ ½ ½ ½ 
of solutions (a_{1},... ,a_{m})Î C_{l}^{1}×...×
C_{l}^{m} of the equation a_{1}a_{2}··· a_{m}=p
where p is any fixed permutation of S_{n}.
We remark that
å^{^}(l^{1},... ,l^{m};p)=
Set (å (l^{1},... ,l^{m};p)).
From this observation we deduce the exponential generating function
(in the variables (p_{j}^{(i)}), j³ 1, 1£ i£ m)
of å^{^}(l^{1},... ,l^{m};p) for a fixed m:



d 

P 

P 

··· P 

=
exp 
æ ç ç è 



c 

P 

P 

··· P 

ö ÷ ÷ ø 
where P_{l}^{(i)}=p_{l}_{1}^{(i)}··· p_{l}_{k}^{(i)}.
Hence, in order to obtain the generating function, we only have to know
all the d_{l}^{1}_{,... ,l}^{m}^{p}.
3 Theory of Characters
Detailed proofs for this section can be found in [5, 6].
Theorem 1 [Frobenius formula]
Let G be a finite group. The number of solutions
(g_{1},... ,g_{m})Î C_{l}^{1}×...× C_{l}^{m}
of the equation g_{1}··· g_{m}=1 is


c (C_{1})···
c (C_{m}) 

[c(1)]^{m2} 

where the sum is extended over the irreducible characters of G.
If G is the symmetric group S_{n}, the irreducible characters
are { c^{µ}} _{µ n} and
c^{µ}(C_{l}) can be computed by the MurnaghanNakayama
rule
Hence theoretically d_{l}^{1}_{,... ,l}^{m}^{p} can be
computed since it can be rewritten as
where f^{µ} is the number of standard Young tableaux of shape µ.
But it is hopeless for n³ 15.
4 Results for Genus 0
The following results are known.
Theorem 2 [Dénès theorem]
Factorization of an ncycle into n1 tranpositions: C_{T}^{n1}^{(n)}=n^{n2}.
Theorem 3 [Hurwitz formula]
Factorization of a of cycletype (a_{1},a_{2},... ,
a_{l (a)}) into a minimal product of n+l (a)2 transpositions
acting transitively on {1,2,... ,n}:
A new bijective proof without using theory of characters
is given in [2].
Theorem 4 [Tree cacti of Goulden and Jackson [4]]
C 

=n^{m1}



æ è 
l(l_{i}) 
a_{1}^{i},... ,a_{m}^{i} 

ö ø 

with 
l^{i}=1 

2 

··· n 

and minimality: 


(nl (l^{i}))=n1. 
The proof uses a recursive decomposition of tree cacti and the LagrangeGood
inversion.
5 Our Main Theorem
Theorem 5 [A. Goupil and G. Schaeffer]
Factorization of an ncycle into two permutations of cycletypes
l and µ with l=(l_{1},... ,l_{k}),
µ=(µ_{1},... ,µ_{k}) and l (l)+l (µ)=n+12g:
C 

= 



(l (l)1+2g_{1})!(l (µ)1+2g_{2})!
S 

(l)S 

(µ) 
In [1] this simple expression was derived. This coefficient was later
interpreted combinatorially by Goulden and Jackson [4] as the number
of unicellular rooted bicolored maps with n edges on a surface of
genus zero, the vertices of each color having degree distribution given
by l and µ respectively, that is the case where m=2 in theorem 4.
If 
g=1,
C 

= 

é ê ê ë 





+ 




ù ú ú û 
. 
Survey of the proof of Theorem 5:

Using explicit expressions for characters of the symmetric group, we
give the following formula
c 

= 


(1)^{r}r!(n1r)!c 

c 

.
(1) 
 The evaluation of some characters are given as weighted summations
over set of ``quasipainted diagrams''.
 We use a bijection to replace quasipainted diagrams by properly
``painted diagrams'' and we rewrite Formula (1) as a weighted summation over some
``painted diagram matchings''.
 The introduction of ``connected components'' of diagram matchings
allows to set apart the diagram matching from its painting and to show
that the weight depends only on the painting.
This is used to apply a sign reversing involution.
 As expected, the fixpoints yield positive contributions. These
contributions count ``colorings'' of the diagram matchings.
 We show that colored diagrams are enumerated by formula of Theorem 5.
6 Corollary for Genus >0
C 

= 



æ è 
n1+2g 
c_{1},... ,c_{n1} 

ö ø 

~ 



where the sum is taken over the odd c_{i} such that å c_{i}=n1+2g.
References
 [1]

Bédard (François) and Goupil (Alain). 
The poset of conjugacy classes and decomposition of products in the
symmetric group. Canadian Mathematical Bulletin, vol. 35, n°2,
1992, pp. 152160.
 [2]

BousquetMélou (M.) and Schaeffer (G.). 
Enumeration of planar constellations. Advances in Applied
Mathematics, 1998. 
To appear.
 [3]

Cori (Robert) and Machí (Antonio). 
Maps, hypermaps and their automorphisms: a survey. I, II,
III. Expositiones Mathematicae, vol. 10, n°5,
1992, pp. 403427, 429447, 449467.
 [4]

Goulden (I. P.) and Jackson (D. M.). 
The combinatorial relationship between trees, cacti and certain
connection coefficients for the symmetric group. European Journal of
Combinatorics, vol. 13, n°5, 1992, pp. 357365.
 [5]

Goupil (Alain). 
On products of conjugacy classes of the symmetric group. Discrete Mathematics, vol. 79, n°1, 1989/90, pp. 4957.
 [6]

Jackson (D. M.). 
Counting cycles in permutations by group characters, with an
application to a topological problem. Transactions of the American
Mathematical Society, vol. 299, n°2, 1987, pp. 785801.
 [7]

Macdonald (I. G.). 
Symmetric functions and Hall polynomials. 
The Clarendon Press Oxford University Press, New York,
1995, second edition, Oxford Mathematical Monographs,
x+475p. With contributions by A. Zelevinsky, Oxford Science Publications.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.