TOPICS
Search

Symmetric Group


The symmetric group S_n of degree n is the group of all permutations on n symbols. S_n is therefore a permutation group of order n! and contains as subgroups every group of order n.

The nth symmetric group is represented in the Wolfram Language as SymmetricGroup[n]. Its cycle index can be generated in the Wolfram Language using CycleIndexPolynomial[SymmetricGroup[n], {x1, ..., xn}].

The number of conjugacy classes of S_n is given P(n), where P is the partition function P of n. The symmetric group is a transitive group (Holton and Sheehan 1993, p. 27).

For any finite group G, Cayley's group theorem proves G is isomorphic to a subgroup of a symmetric group.

SymmetricGroupTable

The multiplication table for S_4 is illustrated above.

Let (ab...)(c...) be the usual permutation cycle notation for a given permutation. Then the following table gives the multiplication table for S_3, which has 3!=6 elements.

S_3(1)(2)(3)(1)(23)(3)(12)(123)(132)(2)(13)
(1)(2)(3)(1)(2)(3)(1)(23)(3)(12)(123)(132)(2)(13)
(1)(23)(1)(23)(1)(2)(3)(132)(2)(13)(3)(12)(123)
(3)(12)(3)(12)(123)(1)(2)(3)(1)(23)(2)(13)(132)
(123)(123)(3)(12)(2)(13)(132)(1)(2)(3)(1)(23)
(132)(132)(2)(13)(1)(23)(1)(2)(3)(123)(3)(12)
(2)(13)(2)(13)(132)(123)(3)(12)(1)(23)(1)(2)(3)

This may be somewhat clearer to understand by using a sequence of three integers to denote both a given permutation and the ordering of numbers after applying a permutation. For example, consider the sequence {2,1,3}, and apply to it the permutation that places the terms of a sequence in the order {2,1,3}. In the notation of the Wolfram Language, this then gives {2,1,3}[[{2,1,3}]]={1,2,3}, which is the identity permutation, as indicated in the table below.

S_3123132213231312321
123123132213231312321
132132123312321213231
213213231123132321312
231231213321312123132
312312321132123231213
321321312231213132123

The cycle index (in variables x_i, ..., x_p) for the symmetric group S_p is given by

 Z(S_p)=1/(p!)sum_((j))(p!)/(product_(k=1)^(p)k^(j_k)j_k!)a_1^(j_1)a_2^(j_2)...a_p^(j_p),
(1)

(Harary 1994, p. 184), where the sum runs over the set of solution vectors j=(j_1,...,j_d) to

 1j_1+2j_2+...+dj_d=d.
(2)

The cycle indices for the first few p are

Z(S_1)=x_1
(3)
Z(S_2)=1/2x_1^2+1/2x_2
(4)
Z(S_3)=1/6x_1^3+1/2x_2x_1+1/3x_3
(5)
Z(S_4)=1/(24)x_1^4+1/4x_2x_1^2+1/3x_3x_1+1/8x_2^2+1/4x_4
(6)
Z(S_5)=1/(120)x_1^5+1/(12)x_2x_1^3+1/6x_3x_1^2+1/8x_2^2x_1+1/4x_4x_1+1/6x_2x_3+1/5x_5.
(7)

Netto's conjecture states that the probability that two elements P_1 and P_2 of a symmetric group generate the entire group tends to 3/4 as n->infty. This was proven by Dixon (1969). The probability that two elements generate S_n for n=1, 2, ... are 1, 3/4, 1/2, 3/8, 19/40, 53/120, 103/168, ... (OEIS A040173 and A040174). Finding a general formula for terms in the sequence is a famous unsolved problem in group theory.


See also

Alternating Group, Cayley's Group Theorem, Conjugacy Class, Erdős-Turán Theorem, Finite Group, Jordan's Symmetric Group Theorem, Landau's Function, Netto's Conjecture, Partition Function P, Permutation Group, Simple Group Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

References

Dixon, J. D. "The Probability of Generating the Symmetric Group." Math. Z. 110, 199-205, 1969.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 181 and 184, 1994.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.Huang, J.-S. "Symmetric Groups." Ch. 3 in Lectures on Representation Theory. Singapore: World Scientific, pp. 15-25, 1999.Lomont, J. S. "Symmetric Groups." Ch. 7 in Applications of Finite Groups. New York: Dover, pp. 258-273, 1987.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 17, 1990.Sloane, N. J. A. Sequences A040173 and A040174 in "The On-Line Encyclopedia of Integer Sequences."Trott, M. Graphica 1: The World of Mathematica Graphics. The Imaginary Made Real: The Images of Michael Trott. Champaign, IL: Wolfram Media, pp. 57 and 87, 1999.

Referenced on Wolfram|Alpha

Symmetric Group

Cite this as:

Weisstein, Eric W. "Symmetric Group." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SymmetricGroup.html

Subject classifications