# Conjugacy classes — how to generate them for a list to be sorted?

In another thread I had brought up the notion of sorting a list of four randomly scrambled items.

It was mentioned that they can be broken down into 5 conjugacy classes: (), (12), (123), (12)(34) and (1234)

Can anyone explain how these work or if there is a general way to list all possible conjugacies? For instance, what about a list of size 6?

-
In what other thread? It would be immensely better to actually link to it (or at least provide the link)! –  Mariano Suárez-Alvarez Mar 10 '12 at 6:32

The conjugacy classes of the symmetric group $S_n$ correspond to the partitions of $n$. How to generate all partitions of $n$ is described e.g. in The Art of Computer Programming by Donald E. Knuth; see Algorithm P on p. 2 of this online version.

-

I write this answer only to make sure that OP realises the connection between the problem stated and the formulation. I think this however could be closed as exact duplicate.

The notion of sorting $n$ items you're talking about is formally called the permutations of $n$ symbols. The notion of conjugacy discussed in the answer corresponds to the action of group on itself by conjugation.

Well, you are asking for the number of conjugacy classes in a symmetric group of order $n$. Yes, there is a nice description.

I'll recall the main result while I'll let you go through the details in an exactly same answer $^\dagger$ I had written over here.

Main result:

The number of conjugacy classes in $S_n$ equals the number of partitions of $n$.

We'll give a way to list an exhaustive set or representatives for the conjugacy classes.

Write down all the additive partitions of $n$. To each partition, associate a representative as follows.

For each number appearing in the partition, attach with it a disjoint cycle of that length. The product of all such cycles represents a unique conjugacy class. It is best illustrated by an example for $4$:

\begin{align*}Id &\cong 1+1+1+1\\(1234)&\cong 4\\(12)(34) &\cong 2+2\\ (34) &\cong 1+1+2(\text{since (1) and (2) are omitted in this notation})\\(123)&\cong 3+1\end{align*}

-
Not sure I understand what your link is explaining. If I partition a list of 6, I can have (12)(345)(6) for instance, but I could just as easily do (1)(234)(56) and yet both (12) and (56) would be considered part of the (12) conjugacy... unless I am totally misunderstanding what such classes represent here. –  John Smith Mar 10 '12 at 7:07
Neither do I understand what you mean. Do you understand what conjugacy means? –  user21436 Mar 10 '12 at 7:22
Perhaps not. I read the Wiki but I am not quite sure I get it in this case. –  John Smith Mar 10 '12 at 15:17
Well, then a more elementary question, do you understand what a group action on a set $X$ means? –  user21436 Mar 10 '12 at 15:20
Not in terms of jargon necessarily but likely the idea is simple –  John Smith Mar 10 '12 at 15:23

I'm just going to add on to what Kanna wrote. In the answer he links he proves that permutations of the same cycle type are all conjugate (and indeed that cycle type is necessarily invariant under conjugation, so that the conjugacy classes are precisely the cycle types). Ultimately this puts classes in bijection with integer partitions. Explicitly, we may list representatives via

$$(a_1,a_2,\dots,a_k)\vdash n \quad \longleftrightarrow \quad (\underbrace{1\;2\;3\;\cdots}_{a_1})(\underbrace{\cdots\cdots}_{a_2})\cdots (\underbrace{\cdots n-1\; n}_{a_k})$$

For example, the integer partition $(3,2,2,1)\vdash8$ corresponds to the permutation $(123)(45)(67)(8)$.

-
@John: First, because the number 4 has exactly five integer partitions (1+1+1+1; 2+1+1; 2+2; 3+1; 4). Second, there is no canonical way to select a representative from each conjugacy class here afaik, so we could have just as easily picked (34) instead of (12) for the permutation corresponding to the partition (2,1,1). We picked arbitrarily. –  anon Mar 10 '12 at 21:52