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

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