involution

An **involution** is an endomorphism whose square is the identity morphism. Such an endomorphism must be an automorphism; indeed, it is its own inverse.

Where this makes sense, an **anti-involution** is an antihomomorphism instead of a homomorphism (so an antiendomorphism and necessarily an antiautomorphism).

Two involutions $f, g : X \to X$ commute if and only if their composition $f g$ is also an involution, as displayed by the following algebra:

$f g = f (f g f g ) g = (f f) g f (g g) = g f$

$(f g)(f g) = f (g f) g = f (f g) g = (f f)(g g)= 1$

In combinatorics, an important class of involutions are the fixed point free ones: an arbitrary involution on a finite set of cardinality $n$ may be specified by the choice of $k$ elements which are fixed together with a fixed point free involution on the remaining $(n-k)$. The number of fixed point free involutions on a set of $2n$ labelled elements is counted by the double factorial $(2n-1)!! = (2n-1)\cdot (2n-3)\cdot\dots\cdot 3\cdot 1 = \frac{(2n)!}{2^n n!}$, while arbitrary involutions on a set of $n$ labelled elements are counted by OEIS sequence A000085, which also counts the number of Young tableaux with $n$ cells.

- Philippe Flajolet and Robert Sedgewick,
*Analytic Combinatorics*, CUP, 2009. (author pdf)

Revised on September 18, 2015 10:09:07
by Noam Zeilberger
(176.189.43.179)