15
правок
Изменения
м
Fixed links and proof
Количество инволюционных перестановок длины <tex>n\geqslant 2 </tex> может быть получено по формуле: <tex> I(n) = I(n-1)+(n-1)\cdot I(n-2) </tex>, где <tex> I(0) = I(1) = 1. </tex>
|proof=
Докажем формулу по '''индукции'''. '''Базой доказательства ''' являются <tex> I(0) = I(1) = 1 </tex>. Осуществим переход от '''Предположим''', что для всех <tex> I(i) </tex> к , где <tex> I(i < n) </tex>, при <tex> i < n > 1 </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>
}}
*[[Теорема Кэли]]
*[[Действие перестановки на набор из элементов, представление в виде циклов]]
<references />
==Источники и литература==
* [https://en.wikipedia.org/wiki/Involution_(mathematics)Wikipedia - Involution]* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
