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


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

Лемма. Если в перестановке длинны больше n, n\ge2 , поменять местами 2 элемента , то четность поменяется на противоположную.
Доказательство:
Докажем, что всякая транспозиция меняет четность перестановки. Для чисел, стоящих рядом, это утверждение очевидно. Их взаимное расположение относительно других чисел осталось прежним, а перестановка самих чисел меняет общее число инверсий на единицу.
Пусть теперь между переставляемыми числами i и j находятся s других чисел l_1, l_2, \cdots, l_s, т. е. перестановка имеет вид \cdots, i, l_1, l_2, \cdots, l_s, j, \cdots.
Будем менять местами число i последовательно с рядом стоящими числами l_1, l_2, \cdots, l_s, j. Затем число j, стоящее уже перед i , переместим влево при помощи s транспозиций с числами l_s, l_{s-1}, \cdots, l_1. Таким образом, всего мы выполним 2s+1 транспозиций рядом стоящих чисел. Следовательно, четность перестановки изменится.
Лемма доказана.

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

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

Следствие. При n\ge2 число четных перестановок из n символов равно числу нечетных, т.е. \frac{n!}{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), теорема справедлива.
Предположение индукции:  n \le m,  m \ge 2.
Шаг индукции:  n= m+1  (i_1, i_2,, i_{m+1}). Рассмотрим все перестановки, где на первом месте стоит  i_1.
(i_1, {i`}_2,, {i`}_{m+1});
({i`}_2, i_1,, {i`}_{m+1});
({i`}_2, {i`}_1,, {i``}_{m+1});
Таких  m!(m+1)= (m+1)! перестановок.
Следствие:
Пусть  n \ge 2 , тогда число  \frac{n!}{2} чётных равно числу  \frac{n!}{2} нечётных перестановок.

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

Теорема 2

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

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

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

Пример

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

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

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

Источники

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