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