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