Изменения

'''Доказательство:'''

Рассмотрим n-ый элемент перестановки. Есть Возможны два случая, где он может находиться:# n-ый элемент стоит на своём месте. Тогда относительно случая, когда элементов оставшиеся n-1 элемент должны представлять собой инволюцию длины n-1 ничего не меняется, и значит число инволюций по-прежнему остаётся таких перестановок равно а(n-1)# n-ый элемент стоит не на своём некотором местеk!=n. Тогда вариантов мест , чтобы перестановка была инволюцией, элемент k должен стоять на которых он может стоять будет месте n. При этом остальные n-2 элемента также должны образовывать инволюцию длины n-12. Получаем, и что для каждого такого варианта мы получим возможное число инволюций фиксированного k существует а(n-2)инволюций, но так как тот элементk можно выбрать n-1 способом, на месте которого окажется то получается (n-1)a(n-ый элемент2) инволюций. Таким образом, сам переместится на место получаем формулу a(n)=a(n-1)+(n-1)a(n-ого элемента.2)