## Information on Involutions

An *involution*, on a set *S* is a permutation
(i.e., a bijection), *p*, on *S* for which
*p*(*p*(*s*)) = *s* for all *s* in *S*.
In other words, they are the self-inverse permutations.
In terms of the cycle-structure of the permutation,
every cycle is of length 1 or 2.
Involutions are characterized by the property that their
permutation matrices are symmetric.
The number of involutions on an *n*-set, call it
*I*(*n*), satisfies the recurrence relation

*I*(*n*) = *I*(*n-*1) + (*n-*1) *I*(*n-*2).
The Schensted correspondence can be used to show a one-to-one
correspondence between involutions and standard
Young tableau.

The number of involutions for *n* = 1,2,...,15, is
1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152,
568504, 2390480, 10349536.
This is sequence
**A000085**(M1221) in
Neil J. Sloane's
database
of integer sequences.

The algorithm used is from the paper:
U. Taylor and F. Ruskey,
*Efficient Generation of Restricted Classes of Permutations*,
manuscript, 1995.

Programs available:

**Questions??** Email
The wizard of COS.

(Please note that the suffix XXXX must be removed from the preceeding
email address.)

It was last updated Wednesday, 10-May-2006 10:32:14 PDT.

There have been 4613 visitors to this page since May 16, 2000
.

©Frank Ruskey, 1995-2003.