Involution (mathematics)

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

!