Метка: инверсия

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

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

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

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

Перестановки. Лемма о числе перестановок длины n


Определение
Упорядоченный набор $n$ элементов множества назовём перестановкой $n$ элементов этого множества.
$(i_1,i_2,\ldots,i_n),$ $i_j \in \{1,2,\ldots,k\},$ $j=\overline{1,n}$. Перестановка $(1,2,\ldots,n)$ называется нормальной. Также перестановки бывают четными и нечетными.
$A=\{ a_1,a_2,\ldots,a_n\}\to\{1,2,\ldots,n\}$ — естественный порядок.

Лемма о числе перестановок длины $n$ 
Число перестановок $n$-элементов множества равна $n!$, где $n$ — длина перестановки.

Для $n=1$ это очевидно. Пусть утверждение верно для любого множества из $n-1$ чисел. Все перестановки из $n$ чисел можно разбить на $n$ классов, помещая в один класс лишь те перестановки, которые на первом месте имеют одно и то же число. Число перестановок в каждом классе совпадает с числом перестановок $n-1$ чисел, т. е. равно $(n-1)!$. Следовательно, число всех перестановок из $n$ чисел равно $n!$.

Примеры:

  1. В турнире участвуют семь команд. Сколько вариантов распределения мест между ними возможно?
    Ответ

    $P_{n} = 7! = 5040$

    [свернуть]
  2. Сколькими способами могут разместиться за круглым столом 10 человек?
    Ответ

    $P_n = 10! =3 62880$

    [свернуть]

Два числа $i$ и $j$ образуют инверсию, если $i>j$, но $i$ стоит в перестановке раньше $j$.

Пример:

  • $(1, 2, 3, 4, 5, 6)$ — нормальная перестановка.
  • $(1, 2, 4, 5, 3, 6)$ — инверсия.

В каждой перестановке можно определить число инверсий в ней, которое можно подсчитать следующим образом: для каждого числа определяют количество стоящих справа чисел, меньших данного числа, и полученные результаты суммируются.

Пример:

Определите число инверсий в данной перестановке: $(4, 5, 1, 3, 6, 2)$.
Решение

1) $\mathbf{4}, 5, 1, 3, 6, 2$
$4<5, 4>1, 4>3, 4<6, 4>2 \Rightarrow 3$
2) $4, \mathbf{5}, 1, 3, 6, 2$
$5>1, 5>3, 5<6, 5>2 \Rightarrow 3$
3) $4, 5, \mathbf{1}, 3, 6, 2$
$1<3, 1<6, 1<2 \Rightarrow 0$
4) $4, 5, 1, \mathbf{3}, 6, 2$
$3<6, 3>2 \Rightarrow 1$
5) $4, 5, 1, 3, \mathbf{6}, 2$
$6>2 \Rightarrow 1$
Теперь суммируя результаты получаем, число инверсий в данной перестановке равна: $3+3+0+1+1=8$.

[свернуть]

Литература :

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

Перестановки

Тест на знание темы «Перестановки»


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

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