Results 1 to 3 of 3

Math Help - Symmetric group counting

  1. #1
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,663
    Thanks
    298
    Awards
    1

    Symmetric group counting

    Show that if n \geq 4 then the number of permutations in S_n which are the product of two disjoint 2-cycles is n(n - 1)(n - 2)(n - 3)/8.
    The n(n - 1)(n - 2)(n - 3) portion is trivial. Obviously this over counts the number of permutations we're looking for and it is natural to find a counting scheme to divide by to get the number of distinct 2-cycles, but I am at a loss to explain how to get the 8.

    Any thoughts?

    Thanks.
    -Dan
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,375
    Thanks
    503

    Re: Symmetric group counting

    There are \binom{n}{2} = \dfrac{n(n-1)}{2} ways to choose two elements for the first 2-cycle. There are \binom{n-2}{2} = \dfrac{(n-2)(n-3)}{2} ways to choose two elements for the second 2-cycle. Since you can choose the 2-cycles in either order, this double counts:

    \dfrac{\binom{n}{2}\binom{n-2}{2}}{2} = \dfrac{n(n-1)(n-2)(n-3)}{8}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,663
    Thanks
    298
    Awards
    1

    Re: Symmetric group counting

    Quote Originally Posted by SlipEternal View Post
    There are \binom{n}{2} = \dfrac{n(n-1)}{2} ways to choose two elements for the first 2-cycle. There are \binom{n-2}{2} = \dfrac{(n-2)(n-3)}{2} ways to choose two elements for the second 2-cycle. Since you can choose the 2-cycles in either order, this double counts:

    \dfrac{\binom{n}{2}\binom{n-2}{2}}{2} = \dfrac{n(n-1)(n-2)(n-3)}{8}
    Thanks. I had thought that there might be a combinatorial in there somewhere. I just couldn't find it.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Symmetric Group
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: August 16th 2010, 12:09 AM
  2. symmetric group
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 25th 2009, 07:04 AM
  3. Symmetric group of P
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 19th 2008, 05:40 AM
  4. symmetric group
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: October 31st 2008, 10:34 PM
  5. Symmetric Group
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 22nd 2008, 03:29 PM

Search Tags


/mathhelpforum @mathhelpforum