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

Матеріал з Вікіпедії — вільної енциклопедії.

Перестановкою скінченної множини $\;X$ називається довільна бієктивна функція $\pi\;:X\rightarrow\;X$ . Всього існує $\;n!$ різних перестановок, де $\;n = |X|$ .

Зміст

1 Група перестановок
2 Представлення перестановок
3 Алгоритми на перестановках
4 Див. також

[ред.] Група перестановок

Перестaновки скінченної множини $\;X$ утворюють групу відносно операції множення перестановок.

[ред.] Тотожня перестановка

Одиничним елементом в групі перестановок є тотожня перестановка $\;E$ , для якої виконується:

$\forall\;x\in\;X: E(x) = x$

Тотожня перестановка переводить множину $\;X$ саму в себе.

[ред.] Добуток перестановок

Добуток перестановок — це послідовне виконання двох перестановок (композиція):

Якщо $\;f,g$ — перестановки, то:

$c = f\times\;g \Leftrightarrow\; \forall\;x\in\;X: c(x)=g(f(x))$ .

[ред.] Обернений елемент

Кожна перестановка має обернену перестановку.

$\forall$ перестановки $f, \;\exists\;f^{-1}$ така що:

$f\times\;f^{-1} = f^{-1}\times\;f = E$

[ред.] Представлення перестановок

Для зручності, перестановки розглядають над множиною $\{1,2,\dots\;,n\}$ (будь-яку іншу скінченну множину можна відобразити в множину такого виду).

[ред.] Запис у два рядки

Запис $f = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 2 & 5 & 10 & 4 & 3 & 7 & 1 & 9 & 8 & 6\end{pmatrix}$ означає, що $f$ — перестановка множини $\{1,2,\dots\;,10\}$ і $f(1) = 2, f(2) = 5, \dots\;,f(10) = 6$ (кожне число у верхньому рядку матриці переводиться у відповідне число в нижньому рядку).

[ред.] Запис в один рядок

Більш уживаним в літературі є запис перестановки в один рядок (верхній рядок непишеться):

$f = \begin{pmatrix} 2 & 5 & 10 & 4 & 3 & 7 & 1 & 9 & 8 & 6\end{pmatrix}$ (та сама перестановка, що і в прикладі запису у два рядки).

[ред.] Циклічний запис

Циклом перестановки $\;\pi$ називається така послідовність $\;x_1, x_2,\dots\;, x_n$ , що $\pi(x_1) = x_2, \pi(x_2) = x_3, \dots\;, \pi(x_{n-1})=x_n, \pi(x_n)=x_1.$

Приклад:

Перестановка $\;f = \begin{pmatrix} 2 & 5 & 10 & 4 & 3& 7& 1 & 9 & 8 & 6 \end{pmatrix}$ має три цикли:

$1\to\;2\to\;5\to\;3\to\;10\to\;6\to\;7\to\;1$
$4\to\;4$
$8\to\;9\to\;8$

Циклічий запис перестановки — це запис через її цикли:

$\pi = \begin{pmatrix} x^{1}_{1} & \dots\; & x^{1}_{n_1} \end{pmatrix}\begin{pmatrix} x^{2}_{1} & \dots\; & x^{2}_{n_2} \end{pmatrix}\dots\;\begin{pmatrix} x^{m}_{1} & \dots\; & x^{m}_{n_m} \end{pmatrix}$

Так для перестановки з прикладу справедливим є запис: $f = \begin{pmatrix}1 & 2 & 5 & 3 & 10 & 6 & 7\end{pmatrix}\begin{pmatrix}4\end{pmatrix}\begin{pmatrix}8 & 9\end{pmatrix}$