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 Anum=A000085"> A000085(M1221) in

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


Programs available:


It was last updated .