A permutation cycle is a subset of a permutation whose elements trade places with one another. Permutations cycles are called "orbits" by Comtet (1974, p. 256). For example, in the permutation group , (143) is a 3-cycle and (2) is a 1-cycle. Here, the notation (143) means that starting from the original ordering , the first element is replaced by the fourth, the fourth by the third, and the third by the first, i.e., .

There is a great deal of freedom in picking the representation of a cyclic decomposition since (1) the cycles are disjoint and can therefore be specified in any order, and (2) any rotation of a given cycle specifies the same cycle (Skiena 1990, p. 20). Therefore, (431)(2), (314)(2), (143)(2), (2)(431), (2)(314), and (2)(143) all describe the same permutation. The following table gives the set of representations for each element of the symmetric group on three elements, , sorted in lowest canonical order (first by cycle length, and then by lowest initial order of elements).

The cyclic decomposition of a permutation can be computed in the Wolfram Language with the function PermutationCycles[p] and the permutation corresponding to a cyclic decomposition can be computed with PermutationList[c]. Here, the individual cycles are represented using the function Cycles. In previous versions, the cyclic decomposition could be computed less efficiently using ToCycles[p] in the Wolfram Language package Permutations` and the permutation corresponding to a cyclic decomposition could be computed using FromCycles[c1, ..., cn] in the Wolfram Language package Permutations` . According to Vardi (1991), the Wolfram Language code for ToCycles is one of the most obscure ever written.

Every permutation group on symbols can be uniquely expressed as a product of disjoint cycles (Skiena 1990, p. 20). A cycle decomposition of a permutation can be viewed as a class of a permutation group.

The number of -cycles in a permutation group of order is given by

where are the Stirling numbers of the first kind. More generally, let be the number of permutations of having exactly cycles all of which are of length . are sometimes called the associated Stirling numbers of the first kind (Comtet 1974, p. 256). The quantities appear in a closed-form expression for the coefficients of in Stirling's series (Comtet 1974, p. 257 and 267). The following table gives the triangles for .

The functions are given by the recurrence relation

where is the falling factorial, combined with the initial conditions

(Riordan 1958, p. 85; Comtet 1974, p. 257).

See also

Golomb-Dickman Constant, Permutation, Permutation Group, Stirling Number of the First Kind, Stirling's Series, Subset

Explore with Wolfram|Alpha

References

Biggs, N. Discrete Mathematics, rev. ed. Oxford, England: Clarendon Press, 1993.Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, p. 257, 1974.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1997.Riordan, J. Combinatorial Identities. New York: Wiley, 1958.Skiena, S. "The Cycle Structure of Permutations." §1.2.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 20-24, 1990.Sloane, N. J. A. Sequences A008275, A008306, A050211, A050212, A050213 in "The On-Line Encyclopedia of Integer Sequences."Stanton, D. and White, D. Constructive Combinatorics. New York: Springer-Verlag, 1986.Vardi, I. Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, p. 223, 1991.

Referenced on Wolfram|Alpha

Permutation Cycle

Cite this as:

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

Subject classifications