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!

Computing Permutations

  1. Feb 21, 2012 #1
    1. The problem statement, all variables and given/known data
    The problem says to compute the expression shown for the permutations σ, τ, and μ.
    My problem in particular says to compute |{σ}| for σ= (1 2 3 4 5 6; 3 1 4 5 6 2)


    3. The attempt at a solution
    My attempt to solve this problem was by first trying to change σ into σ^2. And then I tried continuing to double σ until I got the identity, but at that rate it would take forever.
     
  2. jcsd
  3. Feb 21, 2012 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Do you know how to find the cycle decomposition of a permutation?
     
  4. Feb 21, 2012 #3
    I don't think my professor ever taught me that
     
  5. Feb 21, 2012 #4

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Well, here's a crash course. [itex]\sigma[/itex] maps 1 to 3, 3 to 4, 4 to 5, 5 to 6, 6 to 2, and 2 to 1. We say that [itex]\sigma[/itex] has a cycle consisting of these elements, and we write it as (1 3 4 5 6 2). And we have accounted for all of the elements, so in fact [itex]\sigma[/itex] consists of just this cycle.

    If the above makes sense to you, can you see how many times you would have to apply [itex]\sigma[/itex] in order to obtain the identity?
     
  6. Feb 21, 2012 #5
    So i understood that and I continued doing that. I then got (1 2 3 4 5 6; 1 4 5 6 2 3). After doing it a couple more times, I ended up getting (1 2 3 4 5 6; 1 3 4 5 6 2) again. I dunno if I did something wrong.
     
  7. Feb 21, 2012 #6
    Or would you have to keep going back to the original σ for each new cycle?
     
  8. Feb 21, 2012 #7

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    This doesn't look right. Can you explain how you got that?
     
  9. Feb 21, 2012 #8

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    If you want to write out the powers of [itex]\sigma[/itex], you can do it as follows, for example to calculate [itex]\sigma^2[/itex]:

    [itex]\sigma[/itex] maps 1 to 3 and 3 to 4. Therefore [itex]\sigma^2[/itex] maps 1 to 4.
    [itex]\sigma[/itex] maps 2 to 1 and 1 to 3. Therefore [itex]\sigma^2[/itex] maps 2 to 3.
    [itex]\sigma[/itex] maps 3 to 4 and 4 to 5. Therefore [itex]\sigma^2[/itex] maps 3 to 5.
    [itex]\sigma[/itex] maps 4 to 5 and 5 to 6. Therefore [itex]\sigma^2[/itex] maps 4 to 6.
    [itex]\sigma[/itex] maps 5 to 6 and 6 to 2. Therefore [itex]\sigma^2[/itex] maps 5 to 2.
    [itex]\sigma[/itex] maps 6 to 2 and 2 to 1. Therefore [itex]\sigma^2[/itex] maps 6 to 1.

    This means that [itex]\sigma^2[/itex] = (1 2 3 4 5 6 ; 4 3 5 6 2 1).
     
  10. Feb 21, 2012 #9
    okay i did that and then I got (1 2 3 4 5 6; 6 5 2 1 3 4), then ( 1 2 3 4 5 6; 4 3 5 6 2 1). does this look right?
     
  11. Feb 21, 2012 #10
    I just tried doing σ^3 and I got the inverse because
    1 maps to 4, 4 to 6 and 6 to 1
    2 to 3, 3 to 5, and 5 to 2.
    3 to 5, 5 to 2, and 2 to 3.

    Does this look correct now?
     
  12. Feb 21, 2012 #11
    Okay, i redid it a final time and I believe the answer is 6
     
  13. Feb 21, 2012 #12

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No, here's what I get:

    1 to 3 to 4 to 5
    2 to 1 to 3 to 4
    3 to 4 to 5 to 6
    4 to 5 to 6 to 2
    5 to 6 to 2 to 1
    6 to 2 to 1 to 3

    so [itex]\sigma^3[/itex] = (1 2 3 4 5 6 ; 5 4 6 2 1 3).
     
  14. Feb 21, 2012 #13

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, that's correct.
     
  15. Feb 21, 2012 #14

    Deveno

    User Avatar
    Science Advisor

    in general, if

    σ = (a1 a2....ak1)(b1 b2....bk2)...(t1 t2...tkr)

    where each cycle is disjoint from all the others,

    then |σ| = lcm(k1,k2,...,kr)

    for example, the order of σ =

    (1 2 3 4 5)
    (2 1 4 5 3) = (1 2)(3 4 5) is lcm(2,3) = 6.

    also, if σ is a n-cycle that maps aj→aj+1 (mod n),

    then σk maps aj→aj+k (mod n),

    that is, instead of "jumping to the next number in the cycle (circle)", we skip to the k-th following number" ("looping back around when necessary").
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Computing Permutations
  1. Permutation question (Replies: 3)

  2. Permutation combination (Replies: 11)

Loading...