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

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

Формально, функция называется инволюцией если для всякого из области определения функции .

Если  — инволюция, то имеют место следующие соотношения:

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

Перестановка является инволюцией, если , каждая инволюция является произведением непересекающихся транспозиций, например:

.

Число инволюций в группе перестановок порядка определяется по формулам:

  • (рекуррентная формула),
  • ,

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

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

Примечания

  1. последовательность A000085 в OEIS
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.