<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>
==Инволюция==
{{Определение
<tex> a_i = a^{-1}_i \Rightarrow (a \circ a ^{-1})_i = (a \circ a)_i = a_{a_i} = i </tex>
}}
{{Утверждение
|statement=
Число инволюций можно посчитать, используя рекуррентную формулу:
<tex> a(n) = a(n-1) + (n-1)a(n-2),\ где a(0) = 1,\ a(1) = 1,\ n>1.</tex>
|proof=
'''Доказательство:'''
Рассмотрим n-ый элемент перестановки. Возможны два случая, где он может находиться:
# n-ый элемент стоит на своём месте. Тогда оставшиеся <tex>n-1</tex> элемент должны представлять собой инволюцию длины <tex>n-1</tex>, значит число таких перестановок равно <tex>a (n-1)</tex>
# n-ый элемент стоит на некотором месте <tex> k \ne \neq n </tex>. Тогда, чтобы перестановка была инволюцией, элемент k должен стоять на месте n. При этом остальные <tex>n-2</tex> элемента также должны образовывать инволюцию длины <tex>n-2</tex>. Получаем, что для фиксированного k существует <tex>a (n-2)</tex> инволюций, но так как элемент k можно выбрать <tex>n-1</tex> способом, то получается <tex> (n-1) a (n-2) </tex> инволюций.
Таким образом, получаем формулу <tex> a(n) = a(n-1) + (n-1)a(n-2)</tex>
}}
