Calculating the Number of Permutations in the Symmetric Group of Degree 2n

[Zurtex]

Hi, I need to work out the number of all permutations, $\tau$, in the form:

$$\tau = (\sigma_1 \sigma_2 \ldots \sigma_n) (\theta_1 \theta_2 \ldots \theta_n) \quad \text{for} \quad \sigma_i \neq \theta_j \quad \text{and} \quad \tau \in S_{2n}$$

Namely 2 disjoint cycles of equal length in the symmetric group of degree 2n, letting $\text{o}(\tau)$ be the number of permutations of this form existing, then I have a good guess that:

$$\text{o}(\tau) = \frac{(2n)!}{2n^2}$$

My first thought was to try and prove this inductively, but I’m struggling to come up with some kind of sum for $\text{o}(\tau)$. Could anyone give me a hint or a starting step please.

 

[NateTG]

Can you figure out how many ways to make an $n$ cycle in $S_{2n}$?

How about the number of $n$ cycles in $S_n$?

 

[CarlB]

Your guess is right, now what you need to do is look back through your class notes or book and figure out what the instructor means when they ask for a "proof". I would think that a careful counting is enough.

Carl

 

[Zurtex]

Your guess is right, now what you need to do is look back through your class notes or book and figure out what the instructor means when they ask for a "proof". I would think that a careful counting is enough.
Carl

This is part of a much larger problem, careful counting will be enough but I am unsure how to do that. We have been deliberatly set something that is ahead of what we know, my method for deriving that was somewhat strange and relies on things that I won't be able to prove until I've proven this (again more guesses).

There are (n – 1)! cycles in S_n right? I’m not sure how to derive that, I just remember it, I’m having to absorb a lot of new material in a very short time so I’ve kind of skipped over a lot of deriving in the books I’ve got out.

 

[Hurkyl]

Frequently, the trick to counting something is finding a good way to describe the things being counted. Often, it involves not being distracted by what the things actually are!

 

[CarlB]

There are (n – 1)! cycles in S_n right? I’m not sure how to derive that, I just remember it, I’m having to absorb a lot of new material in a very short time so I’ve kind of skipped over a lot of deriving in the books I’ve got out.

Here's a counting proof for (n-1)! cycles in S_n:

We assume the cycles are for the integers from 1 to n. Without loss of generality, we assume that the cycle is described by a sequence of these digits starting with 1. For example, instead of describing a cycle by (231), we will instead use (123). By arranging for the cycles to always start with 1, we know that the number of cycles will be exactly equal to the number of these sequences of integers.

After the 1 which goes in the first position, there are n-1 choices for the second position in the cycle, then n-2 choices for the next, etc. So the total number of different cycles is (n-1)! .

Carl

 

[Zurtex]

Here's a counting proof for (n-1)! cycles in S_n:
We assume the cycles are for the integers from 1 to n. Without loss of generality, we assume that the cycle is described by a sequence of these digits starting with 1. For example, instead of describing a cycle by (231), we will instead use (123). By arranging for the cycles to always start with 1, we know that the number of cycles will be exactly equal to the number of these sequences of integers.
After the 1 which goes in the first position, there are n-1 choices for the second position in the cycle, then n-2 choices for the next, etc. So the total number of different cycles is (n-1)! .
Carl

Thanks, I had figured out it needed to be turned into a sequence but I wasn't sure how. But it seems more complex for the numbers of an n cycle in S_2n. 1 might not be in the cycle...

In fact I'm not even sure that will be helpful, I was hoping to use a theorem I'd found but it only applies to subgroups and an n cycle isn't a subgroup in S_2n is it? I mean it's not closed..

 

[Zurtex]

Hehe

Ignore my last post, just me being a little slow to catch on :shy:

Edit: Arghh I haven't quite worked it out, but I'm probabily close enough to firgure out the rest myself.