TOPICS
Search

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),
(1)

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

 I(n)=n!sum_(k=0)^(|_n/2_|)1/(2^kk!(n-2k)!)
(2)

(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

 I(n)=(-i)^n2^(n/2)U(-1/2n,1/2,-1/2).
(3)

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.
(4)

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

 I(n)=I(n-1)+(n-1)I(n-2)
(5)

(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

References

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. http://www.cis.upenn.edu/~wilf/AeqB.html.Ruskey, F. "Information on Involutions." http://www.theory.csc.uvic.ca/~cos/inf/perm/Involutions.html.Skiena, 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. https://mathworld.wolfram.com/PermutationInvolution.html

Subject classifications