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


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

Лемма. Если в перестановке длинны больше $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

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

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


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

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

Четность перестановки: 1 комментарий

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

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

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