Перестановки последовательности натуральных чисел - История изменений

СВ в 13:30, 25 октября 2026

2026-10-25T13:30:08Z

← Предыдущая		Версия 13:30, 25 октября 2026
Строка 49:		Строка 49:
	}}		}}

	---		----

	Конспект: [[Алгебра и геометрия]]		Конспект: [[Алгебра и геометрия]]

СВ в 13:29, 25 октября 2026

2026-10-25T13:29:39Z

← Предыдущая		Версия 13:29, 25 октября 2026
Строка 48:		Строка 48:
	Пусть $\alpha_{1} \ne \beta_{1}$, но, понятно, что существует такой элемент $\beta_{j}$, что $\alpha_{1} =\beta_{j} $. Если сделать транспозицию $(1, j)$ в $b$, то получаем перестановку, в которой первый элемент совпадает с первым элементом $a$. Таким образом, приходим к уже рассмотренному случаю.		Пусть $\alpha_{1} \ne \beta_{1}$, но, понятно, что существует такой элемент $\beta_{j}$, что $\alpha_{1} =\beta_{j} $. Если сделать транспозицию $(1, j)$ в $b$, то получаем перестановку, в которой первый элемент совпадает с первым элементом $a$. Таким образом, приходим к уже рассмотренному случаю.
	}}		}}

			---

			Конспект: [[Алгебра и геометрия]]

СВ в 13:29, 25 октября 2026

2026-10-25T13:29:10Z

← Предыдущая		Версия 13:29, 25 октября 2026
Строка 10:		Строка 10:
	\|definition=Будем говорить, что пара элементов $(j_{k}, j_{m})$, $k<m$, перестановки $b$ образует инверсию, если $j_{k} > j_{m}$. Число всех пар перестановки $b$, образующих инверсию, называется числом инверсий в $b$ и обозначается $inv\{b\}$.		\|definition=Будем говорить, что пара элементов $(j_{k}, j_{m})$, $k<m$, перестановки $b$ образует инверсию, если $j_{k} > j_{m}$. Число всех пар перестановки $b$, образующих инверсию, называется числом инверсий в $b$ и обозначается $inv\{b\}$.
	}}		}}

			[[Файл:p02-03-01-inversions-parity.svg\|frame\|none\|800px\|alt=Перестановка 3, 1, 4, 2 с тремя дугами инверсий и таблица всех шести пар\|Рис. 1. Инверсии перестановки <math>(3,1,4,2)</math>: дуги соединяют пары, где левый элемент больше правого. Все шесть пар перечислены в таблице, инверсий три — перестановка нечётная.]]

	{{Определение		{{Определение
	\|definition=Перестановка, содержащая четное число инверсий, называется четной, а нечетное число {{---}} нечетной.		\|definition=Перестановка, содержащая четное число инверсий, называется четной, а нечетное число {{---}} нечетной.
Строка 30:		Строка 33:
	\|statement=Любая транспозиция меняет четность перестановки на противоположную.		\|statement=Любая транспозиция меняет четность перестановки на противоположную.
	}}		}}

			[[Файл:p02-03-02-adjacent-transposition.svg\|frame\|none\|800px\|alt=Две перестановки до и после соседней транспозиции: число инверсий меняется с 3 на 2\|Рис. 2. Соседняя транспозиция 4 и 2 убирает ровно одну инверсию: inv <math>3\to2</math>, чётность меняется. Поэтому транспозиция <math>(1,2)</math> задаёт биекцию между чётными и нечётными перестановками.]]

	{{Теорема		{{Теорема
	\|statement=Число четных перестановок всегда совпадает с числом нечетных.		\|statement=Число четных перестановок всегда совпадает с числом нечетных.

СВ: Новая страница: «Пусть $a=\{ 1, 2, ..., n-1, n\}$ последовательность натуральных чисел, а $b=\{ j_{1}, j_2, ..., j_n\}$ {{---}} после...»

2026-10-24T13:35:41Z

Новая страница: «Пусть $a=\{ 1, 2, ..., n-1, n\}$ последовательность натуральных чисел, а $b=\{ j_{1}, j_2, ..., j_n\}$ {{---}} после...»

Новая страница

Пусть $a=\{ 1, 2, ..., n-1, n\}$ последовательность натуральных чисел, а $b=\{ j_{1}, j_2, ..., j_n\}$ {{---}} последовательность тех же чисел, но взятых в другом (том же) порядке.
{{Определение
|definition=Последовательность $b$ называется перестановкой последовательности $a$.
}}
{{Лемма
|statement=Число различных перестановок последовательности a равно $n!=n(n-1)(n-2)\cdots 2\cdot 1$.
|proof= Так как среди чисел $j_{1}, j_2, ..., j_n$ нет одинаковых, то в качестве первого числа $j_{1}$ можно взять любое из чисел от 1 до $n$. Поэтому имеем ровно $n$ вариантов выбора. В качестве второго числа $j_2$ можно взять любое из $n-1$ оставшихся, то есть имеем $n-1$ вариантов выбора. Таким образом, получаем $n(n-1)$ различных способов выбора первых двух элементов. Продолжая аналогичные рассуждения, убеждаемся, что число различных перестановок из $n$ чисел равно $n!$.
}}
{{Определение
|definition=Будем говорить, что пара элементов $(j_{k}, j_{m})$, $k<m$, перестановки $b$ образует инверсию, если $j_{k} > j_{m}$. Число всех пар перестановки $b$, образующих инверсию, называется числом инверсий в $b$ и обозначается $inv\{b\}$.
}}
{{Определение
|definition=Перестановка, содержащая четное число инверсий, называется четной, а нечетное число {{---}} нечетной.
}}
{{Определение
|definition=Если в некоторой перестановке $j$-й и $k$-й элементы поменять местами, оставив без изменения положение остальных $n-2$ элементов, то такая операция называется транспозицией и обозначается $(j, k)$.
}}
{{Теорема
|statement=Пусть в некоторой перестановке сделана транспозиция. Полученная перестановка приводится к исходной в результате нечетного числа транспозиций соседних элементов.
|proof= Пусть дана некоторая перестановка $\{j_{1}, ..., j_{k}, ..., j_{s}, ..., j_n\}$. Допустим, что в результате транспозиции $(k, s)$ элементы $j_{k}$ и $j_{s}$ поменялись местами. Число элементов между ними равно $s-k-1$. Меняем местами $j_{k+1}$ и $j_{s}$, затем $j_{k+2}$ и $j_{s}$ и так далее После $s-k-1$ транспозиций получаем перестановку $\{ j_{1}, ..., j_{k-1}, j_{k+1}, ..., j_{s}, j_{k}, j_{s+1}, ..., j_n \} $. Меняем теперь местами $j_{k}$ и $j_{s}$, потом $j_{k}$ и $j_{s-1}$ и так далее В результате $s-k$ транспозиций приходим к исходной перестановке. Всего совершено нечетное число $2(s-k)-1$ транспозиций соседних элементов.
}}
{{Теорема
|statement=При транспозиции соседних элементов число инверсий в перестановке меняется на единицу.
|proof= Допустим, что в перестановке $a=\{ j_{1}, ..., j_{k}, j_{k+1}, ..., j_n \} $ сделана транспозиция $(k, k+1)$, получаем $b=\{ j_{1}, ..., j_{k+1}, j_{k}, ..., j_n \}$. Понятно, что число инверсий в перестановках, не содержащих элементы $j_{k}$ и $j_{k+1}$, совпадают. Больше того, если из перестановок $a$ и $b$ исключить один из этих элементов, то число инверсий в оставшихся перестановках также будут совпадать, поскольку каждый из них не меняет своего положения относительно других элементов. Тогда становится очевидным, что если $j_{k} >j_{k+1} $, то $inv \{a\} = inv \{b\} + 1$, тогда как в случае $j_{k} <j_{k+1} $ имеем $inv \{b\} = inv \{a\} + 1$.
}}
{{Следствие
|statement=При транспозиции соседних элементов четная перестановка становится нечетной, а нечетная {{---}} четной.
}}
{{Следствие
|statement=Любая транспозиция меняет четность перестановки на противоположную.
}}
{{Теорема
|statement=Число четных перестановок всегда совпадает с числом нечетных.
|proof= Допустим, что число четных перестановок равно $p$, а число нечетных $q$. Если во всех четных перестановках сделать транспозицию $(1, 2)$, то получим $p$ нечетных перестановок, следовательно, $p\le q$. С другой стороны, если во всех нечетных перестановках также произвести транспозицию $(1, 2)$, то получаем $q$ четных. Но по условию всего их было $p$, поэтому $q\le p$. Отсюда следует, что $p=q$.
}}
{{Теорема
|statement=Любая перестановка может быть получена из любой другой посредством нескольких транспозиций.
|proof= Доказательство проведем методом математической индукции. Если $n=2$, то утверждение очевидно. Пусть теорема доказана для случая, когда в перестановке $n-1$ элементов. Докажем утверждение, когда элементов $n$.

Рассмотрим две произвольные перестановки $a=\{\alpha_{1}, \alpha_2, ..., \alpha_n\} $ и $b=\{\beta_{1}, \beta_2, ..., \beta_n\}$. Если $\alpha_{1} =\beta_{1}$, то поскольку перестановки $\{ \alpha_2, \alpha_3, ..., \alpha_n \} $ и $\{ \beta_2, \beta_3, ..., \beta_n \} $ содержат $n-1$ элементов, то в соответствии с индукционным предположением посредством нескольких транспозиций одна из них приводится к другой.

Пусть $\alpha_{1} \ne \beta_{1}$, но, понятно, что существует такой элемент $\beta_{j}$, что $\alpha_{1} =\beta_{j} $. Если сделать транспозицию $(1, j)$ в $b$, то получаем перестановку, в которой первый элемент совпадает с первым элементом $a$. Таким образом, приходим к уже рассмотренному случаю.
}}