Инволюция (математика)

Инволю́ция (от лат. involutio — свёртывание, завиток) — преобразование, которое является обратным самому себе.

Формально, функция ${\displaystyle f}$ называется инволюцией если ${\displaystyle f(f(x))=x}$ для всякого ${\displaystyle x}$ из области определения функции ${\displaystyle f}$.

Если ${\displaystyle f}$ — инволюция, то имеют место следующие соотношения:

• ${\displaystyle \forall a:f^{-1}(a)=f(a)}$
• ${\displaystyle \forall a:f(f(a))=a}$
• ${\displaystyle \forall a,\exists b:f(a)=b\land f(b)=a}$

Примеры инволюций:

• ${\displaystyle f(x)=-x}$, заданная на множестве целых ${\displaystyle \mathbb {Z} }$, рациональных ${\displaystyle \mathbb {Q} }$ или вещественных чисел ${\displaystyle \mathbb {R} }$;
• ${\displaystyle f(x)={\bar {x}}}$ — дополнение множества, заданная для подмножеств некоторого универсального множества ${\displaystyle U}$;
• ${\displaystyle f(x)=\neg x}$ — логическое отрицание булевой алгебры;
• симметрии: центральная, осевая, зеркальная;
• инверсия;
• комплексное сопряжение;
• преобразование Лежандра.

Перестановка ${\displaystyle \tau }$ является инволюцией, если ${\displaystyle \tau \circ \tau =id}$, каждая инволюция является произведением непересекающихся транспозиций, например:

${\displaystyle {\begin{pmatrix}1&2&3&4&5&6&7&8\\5&7&4&3&1&8&2&6\end{pmatrix}}=(1,5)(2,7)(3,4)(6,8)}$.

Число инволюций в группе перестановок порядка ${\displaystyle n}$ определяется по формулам:

• ${\displaystyle a(0)=1,\ a(1)=1,\ a(n)=a(n-1)+(n-1)a(n-2),\ n>1}$ (рекуррентная формула),
• ${\displaystyle a(n)=\sum _{k=0}^{[n/2]}{\frac {n!}{2^{k}\cdot (n-2k)!\cdot k!}}}$,

(первые значения ${\displaystyle a(n)}$: 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35 696, 140 152[1]).

Свойства инволюции обеспечивают ей широкое применение в различных приложения, например, инволютивные преобразования над пространством булевых векторов используются в различных схемах построения симметричных криптоалгоритмов, таких как сети Фейстеля и подстановочно-перестановочные сети.