|
|
| (не показана 1 промежуточная версия этого же участника) |
| Строка 1: |
Строка 1: |
| Пусть $a=\{ 1, 2, ..., n-1, n\}$ последовательность натуральных чисел, а $b=\{ j_{1}, j_2, ..., j_n\}$ {{---}} последовательность тех же чисел, но взятых в другом (том же) порядке.
| | {{Определение |
| {{Определение
| | |definition= |
| |definition=Последовательность $b$ называется перестановкой последовательности $a$.
| | Перестановкой на множестве $\{1,...,n\}$ называется инъективная функция $\pi : \{1,...,n\}\rightarrow \{1,...,n\}$. Число $n$ называется порядком перестановки $\pi$. |
| | |
| }} | | }} |
| {{Лемма | | |
| |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!$.
| | |content=Как любая инъективная на конечном множестве функция, перестановка является биективной. |
| }} | | }} |
| {{Определение | | {{Замечание |
| |definition=Будем говорить, что пара элементов $(j_{k}, j_{m})$, $k<m$, перестановки $b$ образует инверсию, если $j_{k} > j_{m}$. Число всех пар перестановки $b$, образующих инверсию, называется числом инверсий в $b$ и обозначается $inv\{b\}$. | | |content=В общем случае, перестановкой произвольного множества $X$ называют биекцию $\pi : X\rightarrow X$. |
| }} | | }} |
| {{Определение | | |
| |definition=Перестановка, содержащая четное число инверсий, называется четной, а нечетное число {{---}} нечетной. | | Обозначим $\sigma_n$ множество всех перестановок порядка $n$. Очевидно, что $|\sigma_n|=n!$ |
| | |
| | Существует несколько способов задания перестановки. |
| | Явное задание перестановки |
| | <math> |
| | \pi = |
| | \left( |
| | \begin{array}{cccc} |
| | 1 & 2 & ... & n\\ |
| | \pi(1) & \pi(2) & ... & \pi(n)\\ |
| | \end{array} |
| | \right). |
| | </math> |
| | В записи выше первая строка всегда одинакова. Для задания перестановки достаточно второй строки |
| | $\pi = \pi(1) \pi(2) ... \pi(n)$. |
| | |
| | [[Файл:p25-01-permutation-bijection.svg|frame|none|800px|alt=Двустрочная запись перестановки (2,3,4,1) и стрелочная схема цикла 1→2→3→4→1|Рис. 1. Перестановка <math>\pi=(2,3,4,1)</math> задана двустрочной записью и стрелками <math>1\to2</math>, <math>2\to3</math>, <math>3\to4</math>, <math>4\to1</math>. Это биекция множества на себя: у каждой вершины ровно одна входящая и одна исходящая стрелка.]] |
| | |
| | |
| | Также можно задать перестановку перечислением ее циклов, о чем мы скажем позже. |
| | |
| | {{Определение |
| | |definition= |
| | Пусть $\pi_1,\pi_2\in\sigma_n$. Произведением перестановок $\pi_2$ и $\pi_1$ называют композицию этих функций: $\pi_2\circ \pi_1(i) = \pi_2(\pi_1(i))$, $i=\overline{1,n}$. |
| | |
| }} | | }} |
| {{Определение
| |
| |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$ элементов, то в соответствии с индукционным предположением посредством нескольких транспозиций одна из них приводится к другой.
| | Докажем, что произведение перестановок есть перестановка. |
| | Очевидно, что $\pi_2\circ \pi_1 : \{1,...,n\}\rightarrow \{1,...,n\}$. Покажем инъективность. |
| | Пусть $i,j\in\{1,...,n\}$ и $i\neq j$. Поскольку $\pi_1$ инъективна, $\pi_1(i)\neq \pi_1(j)$, а поскольку инъективна $\pi_2$, |
| | $\pi_2(\pi_1(i))\neq \pi_2(\pi_1(j))$. Следовательно, |
| | $\pi_2\circ\pi_1(i) = \pi_2(\pi_1(i))\neq \pi_2(\pi_1(j)) = \pi_2\circ\pi_1(j)$. |
| | То есть, $\pi_2\circ\pi_1$ {{---}} инъективна, а, значит, является перестановкой. |
| | |
| | |
| | Конспект: [[Дискретная математика]] |
|
| |
|
| Пусть $\alpha_{1} \ne \beta_{1}$, но, понятно, что существует такой элемент $\beta_{j}$, что $\alpha_{1} =\beta_{j} $. Если сделать транспозицию $(1, j)$ в $b$, то получаем перестановку, в которой первый элемент совпадает с первым элементом $a$. Таким образом, приходим к уже рассмотренному случаю.
| | [[Категория:Комбинаторика]] |
| }}
| |
Определение:
Перестановкой на множестве $\{1,...,n\}$ называется инъективная функция $\pi : \{1,...,n\}\rightarrow \{1,...,n\}$. Число $n$ называется порядком перестановки $\pi$.
Замечание
Как любая инъективная на конечном множестве функция, перестановка является биективной.
Замечание
В общем случае, перестановкой произвольного множества $X$ называют биекцию $\pi : X\rightarrow X$.
Обозначим $\sigma_n$ множество всех перестановок порядка $n$. Очевидно, что $|\sigma_n|=n!$
Существует несколько способов задания перестановки.
Явное задание перестановки
[math]\displaystyle{
\pi =
\left(
\begin{array}{cccc}
1 & 2 & ... & n\\
\pi(1) & \pi(2) & ... & \pi(n)\\
\end{array}
\right).
}[/math]
В записи выше первая строка всегда одинакова. Для задания перестановки достаточно второй строки
$\pi = \pi(1) \pi(2) ... \pi(n)$.
Рис. 1. Перестановка [math]\displaystyle{ \pi=(2,3,4,1) }[/math] задана двустрочной записью и стрелками [math]\displaystyle{ 1\to2 }[/math], [math]\displaystyle{ 2\to3 }[/math], [math]\displaystyle{ 3\to4 }[/math], [math]\displaystyle{ 4\to1 }[/math]. Это биекция множества на себя: у каждой вершины ровно одна входящая и одна исходящая стрелка.
Также можно задать перестановку перечислением ее циклов, о чем мы скажем позже.
Определение:
Пусть $\pi_1,\pi_2\in\sigma_n$. Произведением перестановок $\pi_2$ и $\pi_1$ называют композицию этих функций: $\pi_2\circ \pi_1(i) = \pi_2(\pi_1(i))$, $i=\overline{1,n}$.
Докажем, что произведение перестановок есть перестановка.
Очевидно, что $\pi_2\circ \pi_1 : \{1,...,n\}\rightarrow \{1,...,n\}$. Покажем инъективность.
Пусть $i,j\in\{1,...,n\}$ и $i\neq j$. Поскольку $\pi_1$ инъективна, $\pi_1(i)\neq \pi_1(j)$, а поскольку инъективна $\pi_2$,
$\pi_2(\pi_1(i))\neq \pi_2(\pi_1(j))$. Следовательно,
$\pi_2\circ\pi_1(i) = \pi_2(\pi_1(i))\neq \pi_2(\pi_1(j)) = \pi_2\circ\pi_1(j)$.
То есть, $\pi_2\circ\pi_1$ — инъективна, а, значит, является перестановкой.
Конспект: Дискретная математика
