Изменения
доказательство рекуррентной формулы инволюций
Число инволюций можно посчитать, используя рекуррентную формулу:
<tex> a(0n) = a(n-1) + (n-1)a(n-2),\ где a(10) = 1,\ a(n1) = a(1,\ n>1.</tex> Доказательство:Рассмотрим n-ый элемент перестановки. Есть два случая, где он может находиться:1) + n-ый элемент стоит на своём месте. Тогда относительно случая, когда элементов n-1 ничего не меняется, и число инволюций по-прежнему остаётся а(n-1)a2)n-ый элемент стоит не на своём месте. Тогда вариантов мест на которых он может стоять будет n-1, и для каждого такого варианта мы получим возможное число инволюций а(n-2),\ так как тот элемент, на месте которого окажется n-ый элемент, сам переместится на место n>1-ого элемента.</tex>
=Группа перестановок=
