### Conjugation

Having described the elements of * S*_{n} , we show which
of them are in the same conjugacy class, i.e. in the same
orbit of the group * S*_{n}
on the set * S*_{n} under the
conjugation action. In order to do this, we first
note how * rpr*^{-1} is obtained from the permutation * p*:
Thus, in terms of cyclic factors of * p*, * rpr*^{-1} arises from
* p = ( ...i pi ...) ...*

by simply
applying * r* to the points in the cycles of * p*:
*
rpr*^{-1}= ...( ...ri r( pi) ...)
... .

(For any mapping * j:S -> T* we mean by * j(s)=t*
that *s* has to
be replaced by *t* and *not* that *t* is replaced by *s,*
as it is sometimes understood!)
This equation shows that the lengths of the cyclic factors of * p*
are the same as those of * rpr*^{-1}. It is easy to see that,
conversely, for any two elements * p, sÎS*_{n} with the same
lengths *l*_{ n} of cyclic factors there exists a * rÎS*_{n}
such that * rpr*^{-1}= s. Hence the lengths of
the cyclic factors of * p* characterize its conjugacy class.
To make this more explicit, we introduce the notion of *(proper) partition*
of *n Î ***N**, by which we mean any sequence * a= ( a*_{1}, a_{2},
...) of natural numbers * a*_{i} which satisfy
* " i : a*_{i} >= a_{i+1}, and å_{i} a_{i}=n.

The * a*_{i} are called the *parts*
of * a*. The fact that * a*
is a partition of *n* is abbreviated by
* a|¾n.
*

If * a|¾n* then there exists an *h* such that * a*_{i}=0 for
all *i>h*. We may therefore write
* a=( a*_{1}, ..., a_{h}),

for any such *h*. The minimal *h* with this property will be denoted
by *l( a)* and called the *length*
of * a*.
The following abbreviation is useful in the case when several
nonzero parts of
* a* are equal, say *a*_{i} parts are equal to *i,i Î*__n__:
* a= (n*^{an},(n-1)^{an-1}, ...,1^{a1}).

If *a*_{i}=0, then *i*^{ai} is usually omitted, e.g.
*(3,1*^{2})=(3,1,1,0, ...).
For * pÎS*_{n} the ordered lengths * a*_{i}( p),i Î __c( p)__,
of the cyclic factors of * p* in cycle notation form a uniquely determined
proper partition
* a( p)=( a*_{1}( p), a_{2}( p), ..., a_{c( p)}
( p)) |¾n,

which we call the *cycle partition*
of * p*. The corresponding
*n*-tuple
*a( p):=(a*_{1}( p), ...,a_{n}( p))

consisting of the multiplicities *a*_{i}( p) of the parts of length *i* in
* a( p)*
is called the *cycle type*
of * p*. Correspondingly we call an *n*-tuple
*a:=(a*_{1}, ...,a_{n}) a
cycle type of *n* if and only if
each *a*_{i} Î **N**, and
* åi ·a*_{i}
=n.
This will be abbreviated by
*a |¾| n. *

harald.fripertinger@kfunigraz.ac.at,

last changed: August 28, 2001