TOPICS

# Permutation Involution

An involution of a set is a permutation of which does not contain any permutation cycles of length (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 , the two involution permutations on 2 elements are and , and the four involution permutations on 3 elements are , , , and . A permutation 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 elements is the same as the number of distinct Young tableaux on elements (Skiena 1990, p. 32).

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

 (1)

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

 (2)

(Skiena 1990, p. 32). Although the number of involutions on 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 as

 (3)

Breaking this up into even and odd gives

 (4)

The number of involutions of a set containing the first integers is given by the recurrence relation

 (5)

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

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

## Explore with Wolfram|Alpha

More things to try:

## 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