In mathematics, an involution, involutory function, or self-inverse function is a function f that is its own inverse, f(f(x)) = x for all x in the domain of f. Equivalently, applying f twice produces the original value.
General properties Any involution is a bijection. The identity map is a trivial example of an involution. Examples of nontrivial involutions include negation (x ↦ −x), reciprocation (x ↦ 1/x), and complex conjugation (z ↦ z) in arithmetic; reflection, half-turn rotation, and circle inversion in geometry; complementation in set theory; and reciprocal ciphers such as the ROT13 transformation and the Beaufort polyalphabetic cipher. The composition g ∘ f of two involutions f and g is an involution if and only if they commute: g ∘ f = f ∘ g.
Involutions on finite sets 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 0 = a 1 = 1 {\displaystyle a_{0}=a_{1}=1} and a n = a n − 1 + ( n − 1 ) a n − 2 {\displaystyle a_{n}=a_{n-1}+(n-1)a_{n-2}} for n > 1. {\displaystyle n>1.}
The first few terms of this sequence are 1, 1, 2, 4, 10, 26, 76, 232 (sequence A000085 in the OEIS); these numbers are called the telephone numbers, and they also count the number of Young tableaux with a given number of cells. The number an can also be expressed by non-recursive formulas, such as the sum
a n = ∑ m = 0 ⌊ n 2 ⌋ n ! 2 m m ! ( n − 2 m ) ! . {\displaystyle a_{n}=\sum _{m=0}^{\lfloor {\frac {n}{2}}\rfloor }{\frac {n!}{2^{m}m!(n-2m)!}}.}
The number of fixed points of an involution on a finite set and its number of elements have the same parity. Thus the number of fixed points of all the involutions on a given finite set have the same parity. In particular, every involution on an odd number of elements has at least one fixed point. This can be used to prove Fermat's two squares theorem.
Involution throughout the fields of mathematics
Real-valued functions The graph of an involution (on the real numbers) is symmetric across the line y = x. This is due to the fact that the inverse of any general function will be its reflection over the line y = x. This can be seen by "swapping" x with y. If, in particular, the function is an involution, then its graph is its own reflection. Some basic examples of involutions include the functions
… excerpt ends here. Continue reading the full article.
