# Contents

## Idea

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).

## Properties

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.

## References

• 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)