• Support PF! Buy your school textbooks, materials and every day products Here!

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

  • Thread starter xsw001
  • Start date
  • #1
37
0

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!
 
Last edited:

Answers and Replies

  • #2
tiny-tim
Science Advisor
Homework Helper
25,832
250
hi xsw001! :wink:
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? :confused:

what are the # of ways of forming an m-cycle (and why)? :smile:
 
  • #3
37
0
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?
 
  • #4
tiny-tim
Science Advisor
Homework Helper
25,832
250
yup! that should do! :smile:
 
  • #5
37
0
Cool! Thanks tiny-tim!
 

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

  • Last Post
Replies
2
Views
5K
Replies
1
Views
5K
Replies
1
Views
2K
Replies
4
Views
1K
  • Last Post
2
Replies
28
Views
3K
  • Last Post
Replies
10
Views
9K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
8
Views
801
Top