Involution (Set)

An involution of a Set $S$ is a Permutation of $S$ which does not contain any cycles of length $>2$. The Permutation Matrices of an involution are Symmetric. The number of involutions $I(n)$ of a Set containing the first $n$ integers is given by the Recurrence Relation

$$I(n)=I(n-1)+(n-1)I(n-2).$$

For $n=1$, 2, ..., the first few values of $I(n)$ are 1, 2, 4, 10, 26, 76, ... (Sloane's A000085). The number of involutions on $n$ symbols cannot be expressed as a fixed number of hypergeometric terms (Petkovsek et al. 1996, p. 160).

See also Permutation

References

Petkovsek, M.; Wilf, H. S.; and Zeilberger, D. A=B. Wellesley, MA: A. K. Peters, 1996.

Ruskey, F. ``Information on Involutions.'' http://sue.csc.uvic.ca/~cos/inf/perm/Involutions.html.

Sloane, N. J. A. Sequence A000085/M1221 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.