Info on Involutions

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 4295 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.