Loading [MathJax]/jax/output/SVG/jax.js

Четность перестановки


Перестановка, содержащая четное количество инверсий, называется четной, в противном случае — нечетной.

Лемма. Если в перестановке длинны больше latexn,n2, поменять местами latex2 элемента , то четность поменяется на противоположную.
Доказательство:
Докажем, что всякая транспозиция меняет четность перестановки. Для чисел, стоящих рядом, это утверждение очевидно. Их взаимное расположение относительно других чисел осталось прежним, а перестановка самих чисел меняет общее число инверсий на единицу.
Пусть теперь между переставляемыми числами latexi и latexj находятся latexs других чисел latexl1,l2,,ls, т. е. перестановка имеет вид latex,i,l1,l2,,ls,j,.
Будем менять местами число latexi последовательно с рядом стоящими числами latexl1,l2,,ls,j. Затем число latexj, стоящее уже перед latexi , переместим влево при помощи latexs транспозиций с числами latexls,ls1,,l1. Таким образом, всего мы выполним latex2s+1 транспозиций рядом стоящих чисел. Следовательно, четность перестановки изменится.
Лемма доказана.

Пример четной перестановки
Четная перестановка
Данная перестановка является четной, так как содержит 2 инверсии, числа 3 и 2, 6 и 5 образуют инверсии.
Пример нечетной перестановки
Нечетная перестановка
Данная перестановка является нечетной, так как содержит 3 инверсии, числа 2 и 1, 5 и 4, 7 и 6 образуют инверсии.

Транспозиция меняет четность.
Лемма. Все latexn!-перестановок длины latexn можно расположить одну за другой таким образом, что каждая последующая получается из предыдущей одной транспозицией. Причем можно начинать такое упорядочивание с любой перестановки.

Следствие. При latexn2 число четных перестановок из latexn символов равно числу нечетных, т.е. latexn!2.

Литература

  1. Белозёров Г.С. Конспект лекций по алгебре и геометрии
  2. Курош А.Г. Курс высшей алгебры 431 стр. М.: Наука, 1968, Стр. 28-30
  3. Воеводин В.В. Линейная алгебра 400 стр. М.: Наука, 1980, Стр. 122-124

Четность перестановки

Четность перестановки


Таблица лучших: Четность перестановки

максимум из 4 баллов
Место Имя Записано Баллы Результат
Таблица загружается
Нет данных

Теоремы о транспозиции

Теоремы о транспозиции

Прежде чем мы будем рассматривать теоремы о транспозиции, попытаемся сформулировать само понятие транспозиции. Транспозицией называется перемена местами двух элементов перестановки .

Теорема 1

Все n! перестановок длин n можно расположить одну за другой так, что каждая последующая получается из предыдущей 1 (одной) транспозицией, начинать можно с любой перестановки.

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

Доказательство будем проводить индукцией по n .
База индукции: n=2 , то получаем перестановки (1,2),(2,1) , тогда расположения будут иметь вид (1,2,2,1) и (2,1,1,2) , теорема справедлива.
Предположение индукции: nm, m2 .
Шаг индукции: n=m+1 (i1,i2,,im+1) . Рассмотрим все перестановки, где на первом месте стоит i1 .
(i1,i2,,im+1) ;
(i2,i1,,im+1) ;
(i2,i1,,i«m+1) ;
Таких m!(m+1)=(m+1)! перестановок.
Следствие:
Пусть n2 , тогда число n!2 чётных равно числу n!2 нечётных перестановок.

Для следующей теоремы нам понадобятся знания таких понятий, как “инверсия”, “чётность перестановок”.

Теорема 2

Любая транспозиция меняет чётность перестановки.

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

Рассмотрим перестановку …,i,j , …, где i и j транспонируемые символы, стоящие рядом. В результате транспозиции получим новую перестановку …, j,i , …, при этом в данных перестановках каждый из символов i и j составит одинаковые инверсии с символами, остающимися на месте, количество таких инверсий n . В случае, если до этого i и j не составляли инверсий, то с новой перестановкой появится и новая инверсия (число инверсий будет равным n+1 ), в противном случае, число инверсий на 1 уменьшиться. И в том и в другом случаях чётность перестановки меняется.
Теперь рассмотрим вариант, когда между i , j расположеноs символов (s>0) , т.е. перестановка имеет вид …i,k1,k2 , …, ks,j ,…. Транспозицию символов i , j получим последовательным выполнением 2s+1 транспозиции элементов, стоящих рядом. В итоге, мы меняем четность перестановки нечетное число раз, и по-этому перестановки
…, i,k1,k2 , …, ks,j ,… и …, j,k1,k2 , …, ks,i ,… будут противоположной чётности.

Пример

(2,5,4,1,3) (1,5,4,2,3) (1,2,4,5,3)
(1,2,3,5,4) (1,2,3,4,5) .
Здесь, перестановка (2,5,4,1,3) приведена к начальной за 4 транспозиции и она четная, т.к. τ(2,5,4,1,3)=6

Тест о теоремах о транспозиции

Данный тест поможет проверить, как вы усвоили материал данной статьи

Источники

  1. Г.С.Белозеров.Конспект лекций
  2. В.В.Воеводин. Линейная алгебра. Второе издание, физико-математическая литература, 1980. Стр. 122-124.
  3. А.Г.Курош. Курс линейной алгебры. Издание тринадцатое, 2004. Стр.28-37.