Results 1 to 3 of 3

Math Help - permutations (1x) and (123 ... n) generate Sn

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    5

    permutations (1x) and (123 ... n) generate Sn

    Conjecture a necessary and sufficient condition involving x and n for (1x) and (123 ... n) to generate Sn.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by safecracker View Post
    Conjecture a necessary and sufficient condition involving x and n for (1x) and (123 ... n) to generate Sn.
    My conjecture: (1\ x) and (1\ \cdots\ n) generate S_n if, and only if x-1 and n are relatively prime.

    A partial sketch of proof (of the sufficiency):

    You can first prove that (1\ 2) and (1\ \cdots\ n) always generate S_n by showing that they generate the transpositions (k\ k+1), and then any transposition (note that (1\ k)=(1\ 2)(2\ 3)\cdots(k-2\ k-1)(k-1\ k)(k-2\ k-1)\cdots(2\ 3)(1\ 2) if I'm not mistaking).

    If n and x-1 are relatively prime, it suffices to show that (1\ 2) is in the group generated by (1\ x) and (1\ \cdots\ n). The idea is very similar to the proof of the first case. Let p=x-1. First show that you can get the transpositions (k\ (k+p)), and then find (1\ 2) by composing the previous ones in a neat way (very much like the first case).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    5
    Thanks, that makes more sense now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. i need to generate a formula
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 1st 2011, 02:16 PM
  2. how to generate new formulas?
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: November 28th 2010, 06:52 AM
  3. generate
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: November 17th 2010, 10:51 AM
  4. How to generate this?
    Posted in the Geometry Forum
    Replies: 3
    Last Post: February 12th 2010, 10:47 AM
  5. generate the set of polynomials
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: January 24th 2010, 04:24 PM

Search Tags


/mathhelpforum @mathhelpforum