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

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

Пример четной перестановки

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

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

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

Следствие. При $latex n\ge2$ число четных перестановок из $latex n$ символов равно числу нечетных, т.е. $latex \frac{n!}{2}$.

Литература

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

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

Лимит времени: 0

Навигация (только номера заданий)

0 из 4 заданий окончено

Вопросы:

1. 1
2. 2
3. 3
4. 4

Информация

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

Вы уже проходили тест ранее. Вы не можете запустить его снова.

Тест загружается...

Вы должны войти или зарегистрироваться для того, чтобы начать тест.

Вы должны закончить следующие тесты, чтобы начать этот:

Результаты

Правильных ответов: 0 из 4

Ваше время:

Время вышло

Вы набрали 0 из 0 баллов (0)

Рубрики

1. Нет рубрики 0%
2. Алгебра 0%

Ваш результат был записан в таблицу лидеров

Загрузка

Имя: E-Mail:

Капча:

1. 1
2. 2
3. 3
4. 4

1. С ответом
2. С отметкой о просмотре

1. Задание 1 из 4

   1.

   Количество баллов: 1

   Вставьте пропущенное слово:

   • Перестановка, содержащая нечетное количество (инверсий), называется нечетной.
   Правильно
   

   Неправильно
   
2. Задание 2 из 4

   2.

   Количество баллов: 1

   Какие из данных перестановок четные?

   • $(5, 4, 3, 8, 2, 6, 9, 1, 7)$
   • $(7, 2, 1, 5, 6, 9, 3, 4, 8)$
   • $(5, 4, 3, 8, 2, 6, 9, 1, 7)$
   • $(3, 7, 5, 6, 2, 1, 9, 8, 4)$
   Правильно
   

   Неправильно
   
3. Задание 3 из 4

   3.

   Количество баллов: 1

   Сопоставьте:

   Элементы сортировки

   • $(3, 2, 6, 4, 5, 1)$
   • $(6, 5, 2, 3, 1, 4)$

   • Четная

   • Нечетная

   Правильно
   

   Неправильно
   
4. Задание 4 из 4

   4.

   Количество баллов: 1

   Перестановка $(8,5,3,1,2,4,7,6)$ является:

   • четной
   • нечетной
   Правильно
   

   Неправильно
   

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

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

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

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

Лимит времени: 0

Навигация (только номера заданий)

0 из 6 заданий окончено

Вопросы:

1. 1
2. 2
3. 3
4. 4
5. 5
6. 6

Информация

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

Вы уже проходили тест ранее. Вы не можете запустить его снова.

Тест загружается...

Вы должны войти или зарегистрироваться для того, чтобы начать тест.

Вы должны закончить следующие тесты, чтобы начать этот:

Результаты

Правильных ответов: 0 из 6

Ваше время:

Время вышло

Вы набрали 0 из 0 баллов (0)

Средний результат
Ваш результат

Рубрики

1. Нет рубрики 0%
2. Алгебра 0%

Ваш результат был записан в таблицу лидеров

Загрузка

Имя: E-Mail:

Капча:

максимум из 11 баллов

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

1. 1
2. 2
3. 3
4. 4
5. 5
6. 6

1. С ответом
2. С отметкой о просмотре

1. Задание 1 из 6

   1.

   За какое количество транспозиций перестановка (4, 2, 5, 1, 3) будет приведена к начальной?
   Правильно
   

   Неправильно
   
2. Задание 2 из 6

   2.

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

   • Любая транспозиция меняет (чётность перестановки)
   Правильно
   

   Неправильно
   
3. Задание 3 из 6

   3.

   Являются ли такое преобразования перестановок транспозицией ?
   2679035418[latex]\Rightarrow[/latex]2479305618

   • Да
   • Нет
   • Невозможно определить
   Правильно
   

   Неправильно
   
4. Задание 4 из 6

   4.

   Перестановка 38524671 является:

   • четной
   • нечетной
   Правильно
   

   Неправильно
   
5. Задание 5 из 6

   5.

   Сопоставить перестановки с числом содержащихся в них инверсий:

   Элементы сортировки

   • 7
   • 10
   • 4

   • ( 1, 5, 8, 3, 2, 4)

   • ( 6, 9, 5, 8, 7, 1)

   • (4, 1, 3, 2, 5, 6)

   Правильно
   

   Неправильно
   
6. Задание 6 из 6

   6.

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

   • $n= 2$, то получаем перестановки $ (1, 2), (2, 1)$, тогда расположения будут иметь вид $ (1, 2, 2, 1)$ и $(2, 1, 1, 2)$, теорема справедлива;
   • $ n \in m,$ $m \ge 2$;
   • Рассмотрим все перестановки, где на первом месте стоит $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)!$ перестановок.
   Правильно
   

   Неправильно
   

Источники

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