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

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

Перестановкой на множестве $\{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$ — инъективна, а, значит, является перестановкой.

Конспект: Дискретная математика