Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Permutation question

  1. Nov 16, 2008 #1
    1. The problem statement, all variables and given/known data
    prove that there are not permutations of order 18 in S_9.


    2. Relevant equations



    3. The attempt at a solution
    let t=c_1,...,c_k is cycle decomposition of such permutation. let r_1,...,r_k the orders of c_1,...,c_k.

    then lcm(r_1,...,r_k) = 18 and r_1+...+r_k = 9.

    What To Do Next ?
     
  2. jcsd
  3. Nov 16, 2008 #2

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Why is r_1+...+r_k=9? There is definitely something to be said about the r_i's, but this is not it!
     
  4. Nov 17, 2008 #3
    because this is cycle decomposition and hence c_1 is r_1-cycle,..., c_k is r_k cycle.
     
  5. Nov 17, 2008 #4
    well, here are my thoughts, but wait for morphism to confirm it.

    Like you said, let

    [tex]\alpha=\beta_1\beta_2.....\beta_k-----(@)[/tex] be such a permutation written as a product of k disjoint cycles. Let [tex] o(\beta_i)=r_i,i\in\{1,2,....,k\}[/tex] be the orders of those cycles respectively.

    Then we know that the order of that permutation is the least common multiple of the lengths(orders) of the cycles, that is

    [tex]lcm[r_1,r_2,....,r_k]=18[/tex] (in here we are using proof by contradiction, that is we are assuming that indeed there is such a permutation in S_9 whose order is 18)

    But this is not possible, why?

    In order for [tex]lcm[r_1,r_2,....,r_k]=18[/tex] to be true there must be cycles in (@) with orders 9 and 6. But, such a thing is not possible, because say:

    [tex]\beta_1=(a_1a_2a_3a_4a_5a_6), and \beta_2=(b_1b_2.....b_9) [/tex] if

    [tex]\beta=\beta_1\beta_2[/tex] there must be some [tex]a_i=b_j[/tex] for i=1,2...6 and j=1,2,...,9.

    So, the contradiction derived, tells us that the assumption that [tex]lcm[r_1,r_2,....,r_k]=18[/tex] is not true.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook