TOPICS
Search

Cycle Index


Let j_k(alpha) denote the number of cycles of length k for a permutation alpha expressed as a product of disjoint cycles. The cycle index Z(X) of a permutation group X of order m=|X| and degree d is then the polynomial in d variables x_1, x_2, ..., x_d given by the formula

 Z(X)=1/(|X|)sum_(alpha in X)product_(k=1)^dx_k^(j_k(alpha)).
(1)

The cycle index of a permutation group X is implemented as CycleIndexPolynomial[perm, {x1, ..., xn}], which returns a polynomial in x_i. For any permutation alpha, the numbers j_k=j_k(alpha) satisfy

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

and thus constitutes a partition of the integer d. Sets of values j_k are commonly denoted j_i=(j_1,...,j_d)_i, where i ranges over all the d-vectors satisfying equation (2).

Formulas for the most important permutation groups (the symmetric group S_p, alternating group A_p, cyclic group C_p, dihedral group D_p, and trivial group E_p) are 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)
(3)
Z(A_p)=1/(p!)sum_((j))(p![1+(-1)^(j_2+j_4+...)])/(product_(k=1)^(p)k^(j_k)j_k!)a_1^(j_1)a_2^(j_2)...a_p^(j_p)
(4)
Z(C_p)=1/psum_(k|p)phi(k)a_k^(p/k)
(5)
Z(D_p)=1/2Z(C_p)+{1/2a_1a_2^((p-1)/2) for p odd; 1/4(a_2^(p/2)+a_1^2a_2^((p-2)/2)) for p even
(6)
Z(E_p)=a_1^p,
(7)

where k|p means k divides p and phi(k) is the totient function (Harary 1994, p. 184).


See also

Alternating Group, Cycle Graph, Cycle Polynomial, Permutation Cycle, Cyclic Group, Dihedral Group, Permutation Group, Pólya Enumeration Theorem, Simple Graph, Symmetric Group, Symmetric Polynomial

Explore with Wolfram|Alpha

References

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 181 and 184, 1994.

Referenced on Wolfram|Alpha

Cycle Index

Cite this as:

Weisstein, Eric W. "Cycle Index." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CycleIndex.html

Subject classifications