Изменения
→Обратная перестановка
}}
{{Утверждение
|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>}}
=Группа перестановок=
