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

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

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

Теорема 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.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *