Изменения

Существует Очевидно, что <tex> I(0) = I(1) = 1 </tex>. Предположим, что мы посчитали количество инволюций для всех длин <tex> i < n </tex> перестановок, при <tex> n > 1 </tex>, тогда существует <tex> I(n-1)</tex> инволюций, при <tex>a_n = n </tex>. Число (у которых последний элемент представляет собой цикл длины <tex> 1 </tex>), а число инволюцийдлины <tex> n </tex>, содержащих в своём представлении в виде циклов цикл <tex>(j,n)</tex>, где <tex> 1\leq leqslant j\leq leqslant n-1 </tex>, <tex> (n-1)\cdot I(n-2)</tex>(так как при фиксированных <tex> j </tex> и <tex> n </tex> имеем <tex> I(n-2) </tex> перестановок оставшихся элементов, которые не нарушают свойств инволюции). ИмеемТаким образом, что <tex> I(n) = I(n-1)+(n-1)\cdot I(n-2). </tex>

Перестановка, содержащая чётное количество инверсий, называется '''чётной'''(англ. ''even permutation''), в противном случае <tex> - </tex> '''нечётной'''(англ. ''odd permutation'').

Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют '''симметрической ''' (англ. ''symmetric group''), и обозначают <tex> S_n </tex>).