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:XXf, g : X \to X commute if and only if their composition fgf g is also an involution, as displayed by the following algebra:

fg=f(fgfg)g=(ff)gf(gg)=gff g = f (f g f g ) g = (f f) g f (g g) = g f
(fg)(fg)=f(gf)g=f(fg)g=(ff)(gg)=1(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 nn may be specified by the choice of kk elements which are fixed together with a fixed point free involution on the remaining (nk)(n-k). The number of fixed point free involutions on a set of 2n2n labelled elements is counted by the double factorial (2n1)!!=(2n1)(2n3)31=(2n)!2 nn!(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 nn labelled elements are counted by OEIS sequence A000085, which also counts the number of Young tableaux with nn cells.


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

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