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

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

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

Зміст

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

Перестоновки скінченної множини \;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. 1\to\;2\to\;5\to\;3\to\;10\to\;6\to\;7\to\;1
  2. 4\to\;4
  3. 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}

[ред.] Алгоритми на перестановках

[ред.] Див. також