Permutation Involution

An involution of a set S is a permutation of S which does not contain any permutation cycles of length >2 (i.e., it consists exclusively of fixed points and transpositions). Involutions are in one-to-one correspondence with self-conjugate permutations (i.e., permutations that are their own inverse permutation). For example, the unique permutation involution on 1 element is {1}, the two involution permutations on 2 elements are {1,2} and {2,1}, and the four involution permutations on 3 elements are {1,2,3}, {1,3,2}, {2,1,3}, and {3,2,1}. A permutation p can be tested to determine if it is an involution using InvolutionQ[p] in the Wolfram Language package Combinatorica` .

The permutation matrices of an involution are symmetric. The number of involutions on n elements is the same as the number of distinct Young tableaux on n elements (Skiena 1990, p. 32).

In general, the number of involution permutations on n letters is given by the formula

 I(n)=1+sum_(k=0)^(|_(n-1)/2_|)1/((k+1)!)product_(i=0)^k(n-2i; 2),

where (n; k) is a binomial coefficient (Muir 1960, p. 5), or alternatively by


(Skiena 1990, p. 32). Although the number of involutions on n symbols cannot be expressed as a fixed number of hypergeometric terms (Petkovšek et al. 1996, p. 160), it can be written in terms of the confluent hypergeometric function of the second kind U(a,b,z) as


Breaking this up into n even and odd gives

 I(n)={(-2)^kU(-k,1/2,-1/2)   for n=2k; (-2)^kU(-k,3/2,-1/2)   for n=2k+1.

The number of involutions I(n) of a set containing the first n integers is given by the recurrence relation


(Muir 1960, pp. 3-7; Skiena 1990, p. 32). For n=1, 2, ..., the first few values of I(n) are 1, 2, 4, 10, 26, 76, ... (OEIS A000085).

See also

Inverse Permutation, Permutation, Permutation Cycle, Permutation Matrix, Young Tableau

Explore with Wolfram|Alpha


Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Reading, MA: Addison-Wesley, 1998.Muir, T. "On Self-Conjugate Permutations." Proc. Royal Soc. Edinburgh 17, 7-22, 1889.Muir, T. A Treatise on the Theory of Determinants. New York: Dover, 1960.Petkovšek, M.; Wilf, H. S.; and Zeilberger, D. A=B. Wellesley, MA: A K Peters, 1996., F. "Information on Involutions.", S. "Involutions." §1.4.1 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 32-33, 1990.Sloane, N. J. A. Sequence A000085/M1221 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Permutation Involution

Cite this as:

Weisstein, Eric W. "Permutation Involution." From MathWorld--A Wolfram Web Resource.

Subject classifications