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

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

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

Определение
Упорядоченный набор $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\}$ — естественный порядок.

Примеры:

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

Пример:

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

Пример:

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

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

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

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

Вопросы:

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

Информация

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

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

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

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

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

Результаты

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

Ваше время:

Время вышло

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

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

Рубрики

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

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

Загрузка

Имя: E-Mail:

Капча:

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

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

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

   1.

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

   Сколькими способами могут разместиться за круглым столом 5 человек?
   Правильно
   

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

   2.

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

   У каких перестановок число инверсий совпадает?

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

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

   3.

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

   Поставьте перестановки в порядке убывания числа инверсий:

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

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

   4.

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

   Для каждой перестановки определите число инверсий:

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

   • $7$
   • $3$
   • $9$
   • $10$

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

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

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

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

   Правильно
   

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

   5.

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

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

   • (Упорядоченный) набор n элементов множества назовём перестановкой n элементов этого множества.
   Правильно
   

   Неправильно