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
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
Neil J. Sloane's
of integer sequences.
The algorithm used is from the paper:
U. Taylor and F. Ruskey,
Efficient Generation of Restricted Classes of Permutations,
The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.
There have been 4295 visitors to this page since May 16, 2000
©Frank Ruskey, 1995-2003.