Cycle (Permutation)

A Subset of a Permutation whose elements trade places with one another. A cycle decomposition of a Permutation can therefore be viewed as a Class of a Permutation Group. For example, in the Permutation Group $\{4, 2, 1, 3\}$, $\{1, 3, 4\}$ is a 3-cycle ($1\to 3$, $3\to 4$, and $4\to 1$) and $\{2\}$ is a 1-cycle ($2\to 2$). Every Permutation Group on $n$ symbols can be uniquely expressed as a product of disjoint cycles. The cyclic decomposition of a Permutation can be computed in Mathematica ${}^{\scriptstyle\circledRsymbol}$ (Wolfram Research, Champaign, IL) with the function ToCycles and the Permutation corresponding to a cyclic decomposition can be computed with FromCycles. According to Vardi (1991), the Mathematica code for ToCycles is one of the most obscure ever written.

To find the number $N(m,n)$ of $m$ cycles in a Permutation Group of order $n$, take

$$N(n,m)=(-1)^{n-m} S_1(n, m),$$

where $S_1$ is the Stirling Number of the First Kind.

See also Golomb-Dickman Constant, Permutation, Permutation Group, Subset

References

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 20, 1990.

Vardi, I. Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, p. 223, 1991.