Involution (mathematics) - General Properties

General Properties

Any involution is a bijection.

The identity map is a trivial example of an involution. Common examples in mathematics of more detailed involutions include multiplication by −1 in arithmetic, the taking of reciprocals, complementation in set theory and complex conjugation. Other examples include circle inversion, rotation by a half-turn, and reciprocal ciphers such as the ROT13 transformation and the Beaufort polyalphabetic cipher.

The number of involutions, including the identity involution, on a set with n = 0, 1, 2, … elements is given by a recurrence relation found by Heinrich August Rothe in 1800:

a₀ = a₁ = 1;

a_n = a_{n − 1} + (n − 1)a_{n − 2}, for n > 1.

The first few terms of this sequence are 1, 1, 2, 4, 10, 26, 76, 232 (sequence A000085 in OEIS); these numbers are called the telephone numbers, and they also count the number of Young tableaux with a given number of cells.