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

  • Thread starter Thread starter xsw001
  • Start date Start date
  • Tags Tags
    Group
Click For Summary
SUMMARY

The number of m-cycles in the symmetric group Sn, where n ≥ m, is calculated using the formula [n(n-1)(n-2)...(n-m+1)]/m. This formula arises from counting the ways to select m elements from n and arranging them in a cycle, while dividing by m to account for the indistinguishability of the cycle's rotations. For example, with n=5, the number of 1-cycles is 5, 2-cycles is 10, 3-cycles is 20, 4-cycles is 30, and 5-cycles is 24. The order of Sn is n!, which is fundamental in understanding the structure of symmetric groups.

PREREQUISITES
  • Understanding of symmetric groups, specifically Sn
  • Familiarity with combinatorial counting techniques
  • Knowledge of cycle notation in permutations
  • Basic principles of mathematical induction
NEXT STEPS
  • Study the properties of symmetric groups and their orders
  • Explore combinatorial proofs for counting cycles in permutations
  • Learn about cycle decomposition in group theory
  • Investigate advanced topics in permutation groups and their applications
USEFUL FOR

Mathematics students, particularly those studying abstract algebra, combinatorics, or group theory, will benefit from this discussion. It is also valuable for educators seeking to explain the concept of m-cycles in symmetric groups.

xsw001
Messages
34
Reaction score
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:
Physics news on Phys.org
hi xsw001! :wink:
xsw001 said:
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:
 
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?
 
yup! that should do! :smile:
 
Cool! Thanks tiny-tim!
 

Similar threads

Dot diagrams and Jordan canonical forms
  • · Replies 3 ·
Replies
3
Views
2K
Is m the smallest order for an m-cycle in the symmetric group?
  • · Replies 3 ·
Replies
3
Views
1K
Person i belongs to a clique iff ith diagonal entry of B^3 is positive
  • · Replies 9 ·
Replies
9
Views
2K
If ##|s_{n+1} - s_n| \lt 1/2^n##, then ##(s_n)## is a Cauchy sequence
  • · Replies 9 ·
Replies
9
Views
2K
Do these two statements imply an underlying induction proof?
  • · Replies 7 ·
Replies
7
Views
1K
Showing that the alternating group is normal
  • · Replies 7 ·
Replies
7
Views
2K
Prove ##a \cdot 1 = a = 1 \cdot a## for ##a \in \mathbb{N}##
  • · Replies 1 ·
Replies
1
Views
2K
Proof: τ^2=σ for Odd k-Cycle σ in Symmetric Groups
  • · Replies 8 ·
Replies
8
Views
2K
Help with Sum ∑n!/(3*4*5...*n)
  • · Replies 7 ·
Replies
7
Views
1K
To prove the "##m^{\text{th}}## Powers Theorem"
  • · Replies 3 ·
Replies
3
Views
1K