Equations in Sn and Combinatorial Maps

Gilles Schaeffer

LaBRI, Université de Bordeaux I,

Algorithms Seminar

November 3, 1997

[summary by Dominique Gouyou-Beauchamps]

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 (LACIM-UQAM, Montréal).

1   Counting Maps

A partition l = (l 1,l2,... ,lk) is a finite non-increasing sequence of positive integers li such that l1³...³lk>0. The non-zero 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 = 1a12a2··· nan when ai parts of l are equal to i (i=1,...,n). When the sum l1+l2+... +lk=n, we call n the weight of l and we write l|- n or |l |=n. The conjugacy classes Cl of the symmetric group Sn are indexed by partitions of n which are called the cycle types of the permutations sÎ Cl.

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 orientation-preserving 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 cl ,µ(n) that we study below.

2   Equations in Sn

Following [7], let zl=Õiai!iai for a partition l = 1a12a2··· nan. Then
Card (C
 
l
)=|C
 
l
|=
n!
z
 
l
.

Example 1  The conjugacy class T of transpositions is T=C1n-22 and |T|=(
n
2
)=n!/(n-2)!2.

In this talk, we are interested with the general problem of computing the number
C
p
 
l1,... ,lm
= | å(l1,... ,lm;p) |
of solutions (a1,... ,am)Î Cl1×...× Clm of the equation a1a2··· am=p where p is any fixed permutation of Sn and where áa1,... ,amñ acts transitively on {1,2,... ,n}.

Example 2  Factorization of any n-cycle into transpositions
C
(n)
 
Tn-1
= | { (t1,... ,tn-1) transpositions such that t1··· tn-1=(1,2,... ,n) } | =nn-2.
If aÎ Cl and a=t1··· tk, then we have k³ n-l (l)=åi=1l (l)(li-1) and parity of a is given by parity of n-l (l). Thus if a1a2··· am=p, we have the first necessary condition for existence of solutions in å(l1,... ,lm;p):
m
å
i=1
( n-l (li) ) º n-l (p)mod 2.

If áa1,... ,amñ acts transitively on {1,2,... ,n}, the underlying graph is connected.

Example 3   t1··· tm=1. We need m=2n-2 transpositions: n-1 transpositions to get an n-cycle and one connected component, and n-1 transpositions to return to 1.

Proposition 2   Let (a1,... ,am) be in Cl1×...× Clm. If áa1,... ,amñ acts transitively and if a1··· am=1, then åi=1m (n-l (li))³ 2n-2.

Definition 1   The genus of m partitions (l1,... ,lm) of weight n is the non negative integer g defined by the equation
m
å
i=1
( n-l (li) ) =2n-2+2g.

For non transitive systems, we want to compute the number
d
p
 
l1,... ,lm
= ½
½
½
½
^
å
 
(l1,... ,lm;p) ½
½
½
½
of solutions (a1,... ,am)Î Cl1×...× Clm of the equation a1a2··· am=p where p is any fixed permutation of Sn.

We remark that å^(l1,... ,lm;p)= Set (å (l1,... ,lm;p)). From this observation we deduce the exponential generating function (in the variables (pj(i)), j³ 1, 1£ i£ m) of å^(l1,... ,lm;p) for a fixed m:
 
å
n³ 0
zn
n!
 
å
l1,... ,ln,p
d
p
 
l1,... ,lm
P
(1)
 
l1
P
(2)
 
l2
··· P
(m)
 
lm
= exp æ
ç
ç
è
 
å
n³ 1
zn
n!
 
å
l1,... , ln,p
c
p
 
l1,... ,lm
P
(1)
 
l1
P
(2)
 
l2
··· P
(m)
 
lm
ö
÷
÷
ø
where Pl(i)=pl1(i)··· plk(i). Hence, in order to obtain the generating function, we only have to know all the dl1,... ,lmp.

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 (g1,... ,gm)Î Cl1×...× Clm of the equation g1··· gm=1 is
|C1|··· |Cm|
|G|
 
å
c
c (C1)··· c (Cm)
[c(1)]m-2
where the sum is extended over the irreducible characters of G.

If G is the symmetric group Sn, the irreducible characters are { cµ} µ|- n and cµ(Cl) can be computed by the Murnaghan-Nakayama rule
c
µ
 
(C
 
l
)=c
µ
 
l
=
 
å
TÎ T (l , µ)
 
Õ
SÎ T
(-1)h(S).
Hence theoretically dl1,... ,lmp can be computed since it can be rewritten as
d
p
 
l1,... ,lm
=
|C
 
l1
|··· |C
 
lm
|
n!
 
å
µ|- n
c
µ
 
l1
···c
µ
 
lm
c
µ
 
p
[f
µ
 
]m-1
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 n-cycle into n-1 tranpositions: CTn-1(n)=nn-2.
Theorem 3  [Hurwitz formula]   Factorization of a of cycle-type (a1,a2,... , al (a)) into a minimal product of n+l (a)-2 transpositions acting transitively on {1,2,... ,n}:
C
a
 
T
n+l (a)-2
 
=n
l (a)-3
 
(n+l (a)-2)!
k
Õ
i=1
a
ai
 
i
(ai-1)!
.
A new bijective proof without using theory of characters is given in [2].
Theorem 4  [Tree cacti of Goulden and Jackson [4]]  
C
(n)
 
l1,... ,lm
=nm-1
m
Õ
i=1
1
l (li)
æ
è
l(li)
a1i,... ,ami
ö
ø
with li=1
a1i
 
2
a2i
 
··· n
ani
 
and minimality:
m
å
i=1
(n-l (li))=n-1.
The proof uses a recursive decomposition of tree cacti and the Lagrange-Good inversion.

5   Our Main Theorem

Theorem 5  [A. Goupil and G. Schaeffer]   Factorization of an n-cycle into two permutations of cycle-types l and µ with l=(l1,... ,lk), µ=(µ1,... ,µk) and l (l)+l (µ)=n+1-2g:
C
(n)
 
l ,µ
=
n
z
 
l
z
 
µ
22g
 
å
g1+g2=g
(l (l)-1+2g1)!(l (µ)-1+2g2)! S
 
g1
(l)S
 
g2
(µ)
with Sg(l)=
 
å
i1+... +i
 
l (l)
=g
l (l)
Õ
k=1
æ
è
lk
2ik+1
ö
ø
.
If g=0,     C
(n)
 
l ,µ
=
n(l (l)-1)!(l (µ)-1)!
z
 
l
z
 
µ
k
Õ
i=1
li
k
Õ
j=1
µj.
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
(n)
 
l ,µ
=
n(l (l)-1)!(l (µ)-1)!
2z
 
l
z
 
µ
é
ê
ê
ë
æ
è
l (l)+1
2
ö
ø
k
å
i=1
æ
è
li
3
ö
ø
+
æ
è
l(µ)+1
2
ö
ø
k
å
i=1
æ
è
µi
3
ö
ø
ù
ú
ú
û		 .
Survey of the proof of Theorem 5:
  1. Using explicit expressions for characters of the symmetric group, we give the following formula
    c
    (n)
     
    l ,µ
    		=
    n
    z
     
    l
    		z
     
    µ
    n-1
    å
    r=0
    		(-1)rr!(n-1-r)!c
    1r(n-r)
     
    l
    		c
    1r(n-r)
     
    µ
    		.     (1)
  2. The evaluation of some characters are given as weighted summations over set of ``quasi-painted diagrams''.
  3. We use a bijection to replace quasi-painted diagrams by properly ``painted diagrams'' and we rewrite Formula (1) as a weighted summation over some ``painted diagram matchings''.
  4. 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.
  5. As expected, the fix-points yield positive contributions. These contributions count ``colorings'' of the diagram matchings.
  6. We show that colored diagrams are enumerated by formula of Theorem 5.

6   Corollary for Genus >0

C
(n)
 
Tn-1+2g
=
nn-2+2g
(n-1)!22g
 
å
c1,... ,cn-1
æ
è
n-1+2g
c1,... ,cn-1
ö
ø
~
 
n® ¥
nn-2+5g
g!24g
where the sum is taken over the odd ci such that å ci=n-1+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. 152--160.

[2]
Bousquet-Mé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. 403--427, 429--447, 449--467.

[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. 357--365.

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

[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. 785--801.

[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 LATEX by HEVEA.