Самоинверсная перестановка

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

Свойства

Если P(a) — инволюция, то

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

Примеры

• Симметрии
  • центральная,
  • осевая,
  • зеркальная
• Инверсия.
• Перестановка τ является инволюцией, если $\tau\circ\tau=id$. Каждая инволюция является произведением непересекающихся транспозиций. Например:

  $\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)$

  • Число инволюций в группе перестановок порядка n определяется по формулам
    1. рекуррентная формула: $a(0) = 1,\ a(1) = 1,\ a(n) = a(n-1) + (n-1)a(n-2),\ n>1.$
    2. $a(n) = \sum_{k=0}^{[ n/2 ]}{\frac{n!}{2^k\cdot (n-2k)!\cdot k!}}$

Последовательность a(n) начинается так: 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, … (последовательность A000085 в OEIS).