1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number of all permutations

  1. Nov 4, 2005 #1

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    Hi, I need to work out the number of all permutations, [itex]\tau[/itex], in the form:

    [tex]\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}[/tex]

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

    [tex] \text{o}(\tau) = \frac{(2n)!}{2n^2}[/tex]

    My first thought was to try and prove this inductively, but I’m struggling to come up with some kind of sum for [itex]\text{o}(\tau)[/itex]. Could anyone give me a hint or a starting step please.
     
  2. jcsd
  3. Nov 4, 2005 #2

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Can you figure out how many ways to make an [itex]n[/itex] cycle in [itex]S_{2n}[/itex]?

    How about the number of [itex]n[/itex] cycles in [itex]S_n[/itex]?
     
  4. Nov 4, 2005 #3

    CarlB

    User Avatar
    Science Advisor
    Homework Helper

    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
     
  5. Nov 4, 2005 #4

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    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 Sn 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.
     
  6. Nov 4, 2005 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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! :smile:
     
    Last edited: Nov 4, 2005
  7. Nov 5, 2005 #6

    CarlB

    User Avatar
    Science Advisor
    Homework Helper

    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
     
  8. Nov 5, 2005 #7

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    Thanks, I had figured out it needed to be turned in to a sequence but I wasn't sure how. But it seems more complex for the numbers of an n cycle in S2n. 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 S2n is it? I mean it's not closed..
     
    Last edited: Nov 5, 2005
  9. Nov 5, 2005 #8

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
    Last edited: Nov 5, 2005
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?