BG Math/CS Students!

[bori]

If anyone can clarify this problem for me, it would be much appreciated.

The conjugacy type of a permutation is the number of cycles it has of each size. Of the 120 permutations of {1,2,3,4,5}, how many have each possible conjugacy type?


Now, I know what cycle notation is and how it works, but I'm pretty sure there is a way of figuring out this problem without listing all 120 notations...Can anyone give me a hint?

[Teorem]

I had to pull out some materials on group theory, but it sounds like by "conjugacy type" they mean "conjugacy class," and so they just want you to find out the size of each conjugacy class.

That means there's two parts to the question, given your finite symmetric group S5 = {1,2,3,4,5}:

Q1: What are the conjugacy classes of the set you're using, and
Q2: How do you determine the size of each conjugacy class (without enumerating)

Q1 can be determined easily because the number of conjugacy classes for Sn is equal to the number of integer partitions of n. There's a formula to determine the exact number, but for smaller values of n, it's easier to just list them because it makes the solution to Q2 easier to understand.

There are 7 integer partitions of n = 5:

1) 5 (1 5-cycle, eg. (12345) )
2) 4 + 1 (1 4-cycle and 1 1-cycle, eg. (1234) )
3) 3 + 2 (1 3-cycle and 1 2-cycle, eg. (123)(45) )
4) 3 + 1 + 1 (1 3-cycle and 2 1-cycles, eg. (123) )
5) 2 + 2 + 1 (2 2-cycles and 1 1-cycle, eg. (12)(34) )
6) 2 + 1 + 1 + 1 (1 2-cycle and 3 1-cycles, eg. (12) )
7) 1 + 1 + 1 + 1 + 1 (5 1-cycles, identity)

To determine the size of each conjugacy class, you can look at each class as being made up of a series of Ci i-cycles, where 1*C1 + 2*C2 +... + k*Ck = n.

So for a non-trivial example, in the sixth conjugacy class there is:

3 1-cycles (C1=3),
1 2-cycle (C2=1),
0 3-cycles (C3=0),
0 4-cycles (C4=0), and
0 5-cycles (C5=0):

The size of the conjugacy class is defined by (with 1 <= k <= n):

http://starflare.usc.edu/ffxi/linked/20090925_math.gif

, which basically says it's the number of total permutations divided by the number of times you "overcount" the sets, as there's equivalency when you commute disjoint cycles (eg., (12)(34)=>(34)(12)) AND when you permutate the elements within each cycle itself (eg., (12) = (21)).

The size of the sixth conjugacy class is:

n! / ( ( 1^C1 * 2^C2 * 3^C3 * 4^C5 * 5^C6 ) * (C1! * C2! * C3! * C4!* C5!) )
= 5! / ( 1^3 * 2^1 * 3^0 * 4^0 * 5^0) * (3! * 1! * 0! * 0! * 0!) )
= 5! / ( (2) * (3!) )
= (5 * 4) / (2)
= 10

Thus, the size of that conjugation class (1 2-cycle, 3 1-cycles) is 10, which can easily be verified by enumeration:

(12), (13), (14), (15), (23), (24), (25), (34), (35), (45)

Repeat as necessary for the other conjugation classes and remember the Lagrange Theorem if you get a size for one of the conjugation classes that looks off.

Edit: Read this: http://www.math.umn.edu/~drake/pdfs/...tric-group.pdf