A permutation 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). Equivalently, an
involution is its own inverse permutation,
also called a self-conjugate 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 
.
The permutation matrices of an involution are symmetric. The number of involutions on 
elements is the same as the number of standard Young
tableaux of size 
, summed over all shapes (Skiena 1990, p. 32).
For a nonnegative integer 
, the number of permutation involutions on 
elements is given by
 |
(1)
|
where 
is the floor function and 
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)
|
For a nonnegative integer 
, separating the even and odd cases gives
 |
(4)
|
The number of involutions 
of a set containing the first 
integers satisfies the recurrence relation
 |
(5)
|
for 
,
with initial conditions 
(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).
