Перестановка, содержащая четное количество инверсий, называется четной, в противном случае — нечетной.
Лемма. Если в перестановке длинны больше latexn,n≥2, поменять местами latex2 элемента , то четность поменяется на противоположную.
Доказательство:
Докажем, что всякая транспозиция меняет четность перестановки. Для чисел, стоящих рядом, это утверждение очевидно. Их взаимное расположение относительно других чисел осталось прежним, а перестановка самих чисел меняет общее число инверсий на единицу.
Пусть теперь между переставляемыми числами latexi и latexj находятся latexs других чисел latexl1,l2,⋯,ls, т. е. перестановка имеет вид latex⋯,i,l1,l2,⋯,ls,j,⋯.
Будем менять местами число latexi последовательно с рядом стоящими числами latexl1,l2,⋯,ls,j. Затем число latexj, стоящее уже перед latexi , переместим влево при помощи latexs транспозиций с числами latexls,ls−1,⋯,l1. Таким образом, всего мы выполним latex2s+1 транспозиций рядом стоящих чисел. Следовательно, четность перестановки изменится.
Лемма доказана.
Пример четной перестановки
Данная перестановка является четной, так как содержит 2 инверсии, числа 3 и 2, 6 и 5 образуют инверсии.
Пример нечетной перестановки
Данная перестановка является нечетной, так как содержит 3 инверсии, числа 2 и 1, 5 и 4, 7 и 6 образуют инверсии.
Транспозиция меняет четность.
Лемма. Все latexn!-перестановок длины latexn можно расположить одну за другой таким образом, что каждая последующая получается из предыдущей одной транспозицией. Причем можно начинать такое упорядочивание с любой перестановки.
Следствие. При latexn≥2 число четных перестановок из latexn символов равно числу нечетных, т.е. latexn!2.
Литература
- Белозёров Г.С. Конспект лекций по алгебре и геометрии
- Курош А.Г. Курс высшей алгебры 431 стр. М.: Наука, 1968, Стр. 28-30
- Воеводин В.В. Линейная алгебра 400 стр. М.: Наука, 1980, Стр. 122-124
Четность перестановки
Четность перестановки
Таблица лучших: Четность перестановки
Место | Имя | Записано | Баллы | Результат |
---|---|---|---|---|
Таблица загружается |