Prove # of m-cycles in Sn (symmetric group)

[xsw001]

Homework Statement

Prove that if n>=m then the # of m-cycles in Sn is given by [n(n-1)(n-2)...(n-m+1)]/m

Homework Equations

The order of Sn is n!. We're counting the # of ways of forming an m-cycle, then divide by the # of a particular m-cycle.

The Attempt at a Solution

This problem doesn't seem too bad. Initially I was thinking about using the induction proof. But now that I have doubts the induction would even work after I looking at an example since we have to prove for any given n in symmetric group, the # of m-cycles in Sn = [n(n-1)(n-2)...(n-m+1)]/m for all m<=n.

For example if n=5, then
1) m=1, (# of m-cycles in Sn) = 5/1 = 5
2) m=2, (# of m-cycles in Sn) = 5*4/2 = 10
3) m=3, (# of m-cycles in Sn) = 5*4*3/3 = 20
4) m=4, (# of m-cycles in Sn) = 5*4*3*2/4 = 30
5) m=5, (# of m-cycles in Sn) = 5*4*3*2*1/5 = 24

Any helpful tips would be greatly appreciated!

 

[tiny-tim]

hi xsw001!

The order of Sn is n!. We're counting the # of ways of forming an m-cycle, then divide by the # of a particular m-cycle.

what's the difficulty?

what are the # of ways of forming an m-cycle (and why)?

 

[xsw001]

Okay, for any given Sn, there are n elements in Sn {1, 2, ... m,..., n}, so we have n choices for the 1st element, then n-1 choices for the 2nd element, so on and so forth, and we have n-k+1 choices for mth element, etc. So there are total of n(n-1)(n-2)...(n-m+1)choices to form a m-cycle, to count the number of cycles that we have, then we have to divide by m so that we don't count too many.

Can I just explain it out without using induction proof then?

 

[tiny-tim]

yup! that should do!

 

[xsw001]

Cool! Thanks tiny-tim!