Изменения

Очевидно, что Базой доказательства являются <tex> I(0) = I(1) = 1 </tex>. Предположим, что мы посчитали количество инволюций для всех длин Осуществим переход от <tex> I(i ) < /tex> к <tex> I(n ) </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\leqslant j\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>