Symmetric group counting

Printable View

Nov 10th 2013, 12:07 PM
topsquark

Symmetric group counting

Quote:

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
Nov 10th 2013, 12:17 PM
SlipEternal

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}$
Nov 10th 2013, 12:29 PM
topsquark

Re: Symmetric group counting

Quote:

Originally Posted by SlipEternal

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

All times are GMT -8. The time now is 06:33 AM.

Copyright © 2005-2016 Math Help Forum. All rights reserved.