The Warwick Mathematics Society Website

User login

Upcoming events

  • No upcoming events available
Add to iCalendar
more

There are 394 members of the Warwick Mathematics Society, of which 14 are new today!
We're 78% of the way toward our target of 500 members.
You can join up on the UWSU website.

This is combinatorics not algebra

Post Icon Posted: Submitted by richardhp on 8 June 2008 - 3:20pm.

Joined: 2007-10-01
Posts: 179

Is there any reliable way to count the sizes of conjugacy classes in $ S_n $?

So far I've been reduced to writing out all possibilities for $ S_5 $ which is taking quite a long time.

‹ Mathematical Programming Questions on module/exam failure scenario ›
Post Icon Posted: 8 June 2008 - 4:20pm

Joined: 2006-11-02
Posts: 1090

An easier way is this: write out the cycle types as "partitions" of $ (1,2,\dotsc, n) $ with the cycle lengths in decreasing order and say for any given cycle type that $ a_i $ is the length of the $ i\th $ cycle and there are $ b_j $ cycles of length $ j $. As an example in $ S_5 $, one of the cycle types will be $ (1,2)(3,4)(5) $. To find out the number of permutations in the conjugacy class, you will have $ n! $ (by permuting the "letters" in the partition) divided by $ a_i $ for every $ i $ (because of the fact that it doesn't matter by which number a cycle starts) and again by $ b_j! $ for every $ j $ (because we can swap around cycles of the same length and still get the same permutation - e.g. for the permutations (of the letters) 12345 and 34125). So for the example you'll get $ \frac{5!}{2 \cdot 2 \cdot 2!} = 15 $.
Post Icon Posted: 8 June 2008 - 6:12pm

Joined: 2007-10-03
Posts: 397

My method for doing it was slightly different, though I counted things twice but Cosmin corrected me.

Let's try it on $ (abcde)(fgh)(ij)(kl)(mn)(op) $ in $ S_{17} $.

For the first cycle, we have to choose 5 elements from the 17 possible, and then multiply that by the number of distinct cycles of order 5, which is $ 4!=24 $.

Then we choose 3 elements from the remaining 12, and multiply that by the distinct number of cycles of order 3, which is $ 2!=2 $.

Then we choose 3 from 9, 2 from 7, 2 from 5, 2 from 3, multiply that together, and divide by the number of permutations of 4 elements (4!) because we chose the 4 2-cycles in a particular order when it doesn't matter.

Then you should get :

$\displaystyle \binom{17}{5}(5-1)!\binom{12}{3}(3-1)!\binom{9}{2}\binom{7}{2}\binom{5}{2}\binom{3}{2}\frac{1}{4!} $ $\displaystyle = 6188\cdot 24\cdot 220 \cdot 2 \cdot 36 \cdot 21 \cdot 10 \cdot 3 \cdot \frac{1}{24}=61751289600 $

I'd like to see you count THAT one :P

P.S. : $ \big \lfloor 100 \pi \big \rfloor $ posts !
Post Icon Posted: 8 June 2008 - 6:34pm

Joined: 2006-11-02
Posts: 1090
Yes, that also works, but using mine all you need to compute is:
$$\frac{17!}{5\cdot3\cdot2^4\cdot 4!} = 61751289600,$$
which is a bit easier. :P

P.S.: $ \pi + O(1) $ posts!
Post Icon Posted: 8 June 2008 - 6:55pm

Joined: 2007-10-03
Posts: 397

Yes your method is much better, I just thought I'd give my initial approach to offer him a different perspective on the matter !

I also suppose your method gives a nice little extra result :
$\displaystyle \text{In } S_5, \,\, \frac{5!}{5} + \frac{5!}{4} + \frac{5!}{3\cdot2} + \frac{5!}{3\cdot2} + \frac{5!}{2^2\cdot2} + \frac{5!}{2\cdot3!} + \frac{5!}{5!} = 5! $

$\displaystyle \frac{1}{5} + \frac{1}{4} + \frac{1}{3\cdot2} + \frac{1}{3\cdot2} + \frac{1}{2^2\cdot2} + \frac{1}{2\cdot3!} + \frac{1}{5!} = 1 $
Post Icon Posted: 8 June 2008 - 7:18pm

Joined: 2006-10-10
Posts: 520

Spoilers >.< I don't go around saying Hedwig dies on page 57 of HP7, or whatever, so you should tag your stuff too :(

Could you explain your last post a bit more, Xedi? Like, how that falls out. It looks pretty interesting
Post Icon Posted: 8 June 2008 - 7:25pm

Joined: 2007-10-03
Posts: 397

Why would we need spoilers ? In the first post, Richard explicitly asks how to calculate the order of the conjugacy classes, so we tell him :P

The last equality just stems from the fact that the sum of the orders of the conjugacy classes sums to the order of the group itself as they partition it. So I just added up the orders of all the conjugacy classes of $ S_5 $ and equated with $ 5! $.
Post Icon Posted: 8 June 2008 - 7:30pm

Joined: 2006-10-10
Posts: 520

Sweeeeet
Post Icon Posted: 8 June 2008 - 8:36pm

Joined: 2007-10-17
Posts: 109

I suppose you've got a point on this occasion Sam, but by always going straight for the answer you seem to be trying to be smart all the time. Mightn't it be better to try to be wise instead, sometimes? Perhaps one ought to ponder the question for a while, then try to give some sort of explanatory hint that would help someone to think about it for themselves and hopefully then, understand it. Possibly.
Post Icon Posted: 8 June 2008 - 8:52pm

Joined: 2006-11-02
Posts: 1090

Are you talking about the general problem of finding the number of permutations in a conjugacy class or that last identity, Colin?
Post Icon Posted: 8 June 2008 - 8:57pm

Joined: 2006-10-10
Posts: 520

Holy crap, seriously, stfu. NO-ONE, except for you, believes that Sam is trying to showoff, and as his friend I completely resent that implication. There is a simple solution for the problem you seem to have with threads like these - don't read them. Two days before the exam, we don't want to discuss the answer over vending machine coffee in the maths dept, we want the answer.

Although he'll hate me saying this, Sam is one of the sharpest people on this forum, and pulls it off without the arrogance displayed by a lot of the mathematics undergraduates here. Have you read his question on De Rham Cohomology? Or his answer to that matrix question from the start of the year? Compared to threads such as these, this bitter, resentful comment is like getting raped in the eyes with a chese grater.

in a pissed off mood
Post Icon Posted: 8 June 2008 - 9:02pm

Joined: 2006-11-02
Posts: 1090

Seconded...

Edit: What I was going to say (and the reason I asked that question) is that in either case, I would have thought giving a hint would be a massively more condescending answer. It sort of says "I know that if I give you a full solution you'll gloss over it and not understand it, so I'll just give you a hint so that you actually do think about the problem". That's fine when you're trying to help someone in maths cafe for example but in some cases just giving the answer is really a lot better and a lot less time-wasting (especially if you were refering to the identity).
Post Icon Posted: 9 June 2008 - 8:00am

Joined: 2007-10-01
Posts: 179

indeed, i think the need for straight answers is driven by the very short time frame between now, and the time when knowing the answer will save you from immense pain.

EDIT: whenever sam answers a question i always think of this:

Back to the Maths Forum