Метка: перестановка

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


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

Лемма. Если в перестановке длинны больше $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 баллов
Место Имя Записано Баллы Результат
Таблица загружается
Нет данных

Подстановки степени n

 Определение:

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

$latex
\begin{pmatrix}
i_{1} & i_{2} & \ldots & i_{n}\\
a_{i_{1}} & a_{i_{2}} & \ldots & a_{i_{n}}
\end{pmatrix} $
через $latex a_{i}$ здесь обозначается то число, в которое при подстановке $latex A$ переходит число $latex i$, $latex i = 1,2,$ $latex \ldots , n$.

Замечание:

От одной записи подстановки $latex A$ к другой можно перейти при помощи транспозиций столбиков. Любая подстановка $latex n$-й степени может быть записана в виде:

$latex \begin{pmatrix}
1 & 2 & \ldots & n\\
a_{1} & a_{2} & \ldots & a_{n}
\end{pmatrix} $
Т.е. с натуральным расположением чисел в верхней строке. При такой записи различные подстановки различаются друг от друга перестановками, стоящими в нижней строке, и поэтому число перестановок из $latex n$ чисел равно $latex n!$ .

Переход к любой другой записи подстановки $latex A$ можно осуществить, как мы знаем, путём последовательного выполнения нескольких транспозиций в верхней строке и соответствующих им транспозиций в нижней строке. Мы одновременно меняем чётность и поэтому сохраняем совпадение или противоположность этих чётностей.

Отсюда следует, что либо при всех записях подстановки $latex A$ чётности верхней и нижней строк совпадают, либо же при всех записях они противоположны. В первом случае подстановка $latex A$ называется чётной, а во втором — нечётной. В частности тождественная подстановка($latex E$) будет чётной:

$latex E =
\begin{pmatrix}
1 & 2 & \ldots & n\\
1 & 2 & \ldots & n
\end{pmatrix} $Число чётных подстановок равно числу нечётных, равно $latex {\frac12 n!}$

Пример

$latex \begin{pmatrix}
4 & 3 & 5 & 2 &1\\
3 & 5 & 2 & 1 &4
\end{pmatrix}$ всегда можно представить в виде $latex \begin{pmatrix}
1 & 2 & 3 & 4 &5\\
4 & 1 & 5 & 3 &2
\end{pmatrix}$

Подстановки степени n

Тест по теме «Подстановки степени $latex n$».

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

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

Список литературы:

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

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

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

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