WikiSort.ru - Не сортированное

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

Определение

Функция ${\displaystyle f}$ называется инволюцией если

${\displaystyle f(f(x))=x}$

для всякого ${\displaystyle x}$ из области определения функции ${\displaystyle f}$ .

Свойства

Если ${\displaystyle P(a)}$  — инволюция, то

1. ${\displaystyle \forall a,P^{-1}(a)=P(a)}$
2. ${\displaystyle \forall a,P(P(a))=a}$
3. ${\displaystyle \forall x,\exists y:P(x)=y,P(y)=x}$

Примеры

• ${\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}$ определяется по формулам
    1. рекуррентная формула: ${\displaystyle a(0)=1,\ a(1)=1,\ a(n)=a(n-1)+(n-1)a(n-2),\ n>1.}$
    2. ${\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 (последовательность A000085 в OEIS).

Применения

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

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.

Для улучшения этой статьи по математике желательно: Дополнить статью (статья слишком короткая либо содержит лишь словарное определение). Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное. Проставить для статьи более точные категории.