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
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
| I(n)=(-i)^n2^(n/2)U(-1/2n,1/2,-1/2). |
(3)
|
Breaking this up into n even and odd gives
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 TableauExplore 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 InvolutionCite this as:
Weisstein, Eric W. "Permutation Involution." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PermutationInvolution.html