Циклы перестановки

Будем обозначать $\pi^k = \underbrace{\pi\circ\pi\circ \cdots \circ \pi}_k$; $\pi^0 = e$; $\pi^{-k} = \underbrace{\pi^{-1}\circ\pi^{-1} \circ \cdots \circ \pi^{-1}}_k$.

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

Циклом длины $l$ называется такая перестановка $\pi$,

которая тождественна на всём множестве $\{1,2,...,n\}$, кроме подмножества $\{x_1,...,x_l\}$.

Кроме того, $\pi(x_l)=x_1$ и $\pi(x_i)=x_{i+1}$, $i=\overline{1, l-1}$.

Цикл обычно обозначается $(x_1,x_2,...,x_l) = (x_1,\pi(x_1),...,\pi^{l-1}(x_1))$.

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

Транспозиция — перестановка элементов множества $\{1,2,...,n\}$, которая меняет местами только два элемента.

Замечание

Транспозиция — цикл длины 2.

Утверждение:

Пусть $\pi\in\sigma_n$ и $i\in\{1,...,n\}$. Тогда существует такое число $k\in\mathbb{N}$, что $\pi^k(i) = i$.

Доказательство:

Пусть $i\in\{1,...,n\}$. Предположим от противного, что для любого $k\in\mathbb{N}$ верно $\pi^k(i) \neq i$. Так как множество $\{1,...,n\}$ конечно, а последовательность $i, \pi(i), \pi^2(i), ..., \pi^s(i), ...$ бесконечна, элементы этой последовательности будут повторяться.

Пусть $s\geq 0$ такое наименьшее целое число, что элемент $\pi^s(i)$ встретиться в нашей последовательности больше одного раза. То есть существует $t>s$: $\pi^s(i)=\pi^t(i)$. Согласно нашему предположению, $\pi^s(i)\neq i$ и, следовательно, $s > 0$.

Поскольку $s>0$ для элементов $\pi^s(i)$ и $\pi^t(i)$ в последовательности степеней перестановки $\pi$ от $i$ существуют предыдущие элементы. Тогда можно записать $\pi(\pi^{s-1}(i)) = \pi(\pi^{t-1}(i))$. Из инъективности перестановки следует, что $\pi^{s-1}(i) = \pi^{t-1}(i)$. Последнее равенство противоречит выбору $s$ как степени наименьшего из повторяющихся элементов последовательности, поскольку элемент $\pi^{s-1}$ тоже должен повториться. Противоречие доказывает утверждение.

[math]\displaystyle{ \blacksquare }[/math]

Для произвольной перестановки $\pi\in\sigma_n$ введем бинарное отношение $\rho_\pi$ на множестве $\{1,2,...,n\}$: $\forall x, y\in\{1,...,n\}: x\rho_\pi y \Leftrightarrow \exists k\in\mathbb{Z}: y = \pi^k(x)$. Покажем, что $\forall \pi\in\sigma_n$ $\rho_\pi$ — отношение эквивалентности.

1) Рефлексивность. Для любого $x\in\{1,...,n\}$ $x = \pi^0(x)$ $\Rightarrow$ $x \rho_\pi x$.

2) Симметричность. Для любых $x,y\in\{1,...,n\}$, для которых $x\rho_\pi y$, существует $k\in\mathbb{Z}$: $y = \pi^k(x)$. Следовательно, $x = \pi^{-k}(y)$ и $y\rho_\pi x$.

3) Транзитивность. Пусть $x,y,z\in\{1,2,...,n\}$, $x\rho_\pi y$ и $y\rho_\pi z$. Тогда существуют $k_1, k_2\in\mathbb{Z}$: $y = \pi^{k_1}(x)$, $z = \pi^{k_2}(y)$. Следовательно, $z = \pi^{k_2}(\pi^{k_1}(x)) = \pi^{k_1+k_2}(x)$. То есть $x\rho_\pi z$.

Пусть $\{1,2,...,n\}=B_1\cup B_2\cup ...\cup B_m$ — разбиение $\{1,2,...,n\}$ на классы эквивалентности относительно $\rho_\pi$. $B_i$ называются орбитами перестановки.

Пусть $\pi\in\sigma_n$, $B_1\cup B_2\cup ... \cup B_m$ — разбиение множества $\{1,2,...,n\}$ на классы эквивалентности, порожденное отношением $\rho_\pi$, и $x_i\in B_i$, $i=\overline{1,m}$. Тогда

1) для любого $i\in\{1,2,...,m\}$ существует $n_i\in\mathbb{N}$: $B_i = \{x_i, \pi(x_i), ..., \pi^{n_i-1}(x_i)\}$.

2) перестановка $\pi$ представима в виде произведения циклов: $\pi = (x_1,\pi(x_1),...,\pi^{n_1-1}(x_1))\circ (x_2,\pi(x_2),...,\pi^{n_2-1}(x_2))\circ \circ \cdots \circ (x_m,\pi(x_m),...,\pi^{n_m-1}(x_m))$.

Доказательство. 1) По определению, $B_i$ состоит из всех таких $y$, для которых существует $s\in\mathbb{Z}$: $y=\pi^s(x_i)$.

По утверждению, для $x_i$ существует $k\in\mathbb{N}$: $\pi^{k}(x_i) = x_i$. Пусть $n_i$ — наименьшее из таких чисел. Тогда $x_i, \pi(x_i), ..., \pi^{n_i-1}(x_i)$ — различные элементы из $\{1,2,...,n\}$ и $\{x_i, \pi(x_i), ..., \pi^{n_i-1}(x_i)\}\subseteq B_i$.

Пусть $y\in B_i\setminus \{x_i, \pi(x_i), ..., \pi^{n_i-1}(x_i)\}$. Тогда существует такое $s\in\mathbb{Z}$, что $y=\pi^s(x_i)$ и $s\notin\{1,2,...,n_i-1\}$. $s = p\cdot n_i+q$, $p\in\mathbb{Z}\setminus \{0\}$, $q\in\{0,1,...,n_i-1\}$. Следовательно, $y = \pi^{s}(x_i) = \pi^q(\pi^{p\cdot n_i}(x_i))$.

Если $p > 0$, то $\pi^{p\cdot n_i}(x_i) = \underbrace{\pi^{n_i}\circ\pi^{n_i}\circ\cdots\circ \pi^{n_i}}_p(x_i) = x_i$.

Пусть теперь $p < 0$. Тогда, получим $\pi^{p\cdot n_i}(x_i) = \underbrace{\pi^{-n_i}\circ\pi^{-n_i}\circ\cdots\circ \pi^{-n_i}}_{-p}(x_i) = $ $=\underbrace{\pi^{-n_i}\circ\pi^{-n_i}\circ\cdots\circ \pi^{-n_i}}_{-p} (\underbrace{\pi^{n_i}\circ\pi^{n_i}\circ\cdots\circ \pi^{n_i}}_{-p}(x_i)) =x_i$, поскольку $\pi^{-n_i}\circ\pi^{n_i}(i) = \underbrace{\pi^{-1}\circ\pi^{-1}\circ...\circ\pi^{-1}}_{n_i}\circ \underbrace{\pi\circ\pi\circ...\circ\pi}_{n_i}(i)=i$.

Таким образом, $y =\pi^q(x_i)$, где $q\in\{0,1,...,n_i-1\}$, что противоречит выбору $y$. Следовательно, $B_i = \{x_i, \pi(x_i), ..., \pi^{n_i-1}(x_i)\}$.

2) Согласно пункту 1 доказательства, для цикла $(x_i,\pi(x_i),...,\pi^{n_1-1}(x_i))$ выполняется формула [math]\displaystyle{ (x_i,\pi(x_i),...,\pi^{n_1-1}(x_i)) (x)= \left\{ \begin{array}{ll} x, & x\notin B_i,\\ \pi(x), & x\in B_i. \end{array} \right. }[/math]

Обозначим $\pi_i = (x_i,\pi(x_i),...,\pi^{n_1-1}(x_i))$, $i=\overline{1, m}$.

Если $x\in B_j$ и $j\neq i$, то $\pi_i(x) = x$. То же верно и для $\pi(x)$, поскольку $\pi(x)\in B_j$.

Пусть $x\in\{1, 2,...,n\}$ — произвольное значение. Пусть, не умаляя общности, $x\in B_i$. Тогда, $(\pi_1\circ\pi_2\circ\cdots\circ \pi_i\circ\cdots \circ\pi_{m-1}\circ\pi_m) (x)=$ $=(\pi_1\circ\pi_2\circ\cdots\circ \pi_i\circ\cdots \circ\pi_{m-1})(\pi_m (x))=$ $=(\pi_1\circ\pi_2\circ\cdots\circ \pi_i\circ\cdots \circ\pi_{m-1})(x)= \cdots =$ $= (\pi_1\circ\pi_2\circ\cdots\circ \pi_i)(x) = (\pi_1\circ\pi_2\circ\cdots\circ \pi_{i-1})(\pi_i(x)) = $ $= (\pi_1\circ\pi_2\circ\cdots\circ \pi_{i-1})(\pi(x)) = \cdots = \pi_1(\pi(x)) = \pi(x)$.

Если $x\in B_j$ и $j\neq i$, то $(x_i,\pi(x_i),...,\pi^{n_1-1}(x_i))(x) = x$. То же верно и для $\pi(x)$, поскольку $\pi(x)\in B_j$. Тогда $(x_1,\pi(x_1),...,\pi^{n_1-1}(x_1))\circ \cdots \circ (x_j,\pi(x_j),...,\pi^{n_j-1}(x_j))\circ \cdots \circ \circ (x_m,\pi(x_m),...,\pi^{n_m-1}(x_m))(x)= $ $=(x_1,\pi(x_1),...,\pi^{n_1-1}(x_1))\circ \cdots \circ \circ (x_j,\pi(x_j),...,\pi^{n_j-1}(x_j))\circ \cdots \circ \circ (x_{m-1},\pi(x_{m-1}),...,\pi^{n_{m-1}-1}(x_{m-1})) ((x_m,\pi(x_m),...,\pi^{n_m-1}(x_m))(x))=$ $=(x_1,\pi(x_1),...,\pi^{n_1-1}(x_1))\circ \cdots \circ (x_j,\pi(x_j),...,\pi^{n_j-1}(x_j))\circ \cdots \circ \circ (x_{m-1},\pi(x_{m-1}),...,\pi^{n_{m-1}-1}(x_{m-1}))(x)=$ $=(x_1,\pi(x_1),...,\pi^{n_1-1}(x_1))\circ \cdots \circ (x_j,\pi(x_j),...,\pi^{n_j-1}(x_j))(x)=$ $=(x_1,\pi(x_1),...,\pi^{n_1-1}(x_1))\circ \cdots \circ \circ (x_{j-1},\pi(x_{j-1}),...,\pi^{n_{j-1}-1}(x_{j-1}))(\pi(x))=$ $=(x_1,\pi(x_1),...,\pi^{n_1-1}(x_1))(\pi(x))=\pi(x)$

Это верно для любого $x\in\{1,2,...,n\}$. Таким образом, $\pi = (\pi_1\circ\pi_2\circ\cdots\circ\pi_m)$, что и требовалось доказать. Сопоставим каждой орбите $B_i$ перестановку $\pi_i$: [math]\displaystyle{ \pi_i (x)= \left\{ \begin{array}{ll} x, & x\notin B_i,\\ \pi(x), & x\in B_i. \end{array} \right. }[/math] Будем называть циклы $\pi_i$, $i=\overline{1, m}$, циклами перестановки $\pi$. Замечание. Из утверждения следует, что перестановку $\pi$ можно представить в виде произведения всех ее циклов: $\pi = \pi_1 \circ \pi_2 \circ \cdots \circ \pi_m$. Поскольку орбиты не пересекаются, перестановки в этой композиции можно располагать в любом порядке: $\pi = \pi_{i_1} \circ \pi_{i_2} \circ \cdots \circ \pi_{i_m}$, где $i_1 i_2 ... i_m$ — произвольная перестановка из $\sigma_m$.

Пусть $n=7$ и [math]\displaystyle{ \pi = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 2 & 7 & 1 & 3 & 6 & 5\end{array}\right). }[/math] Найдем орбиты $\pi$. $\pi(1)=4, \pi^2(1) = \pi(4) = 1 \Rightarrow B_1 = \{1,4\}$, $\pi(2)=2, \Rightarrow B_2 = \{2\}$, $\pi(3)=7, \pi^2(3) = \pi(7) = 5, \pi^3(3) = \pi(5) = 3 \Rightarrow B_3 = \{3,5,7\}$, $\pi(6)=6, \Rightarrow B_4 = \{6\}$. Представление перестановки $\pi$ в виде произведения циклов имеет вид $\pi = (1,4)(2)(3,7,5)(6)$.

Рис. 1. Перестановка распадается на циклы [math]\displaystyle{ (1,4) }[/math], [math]\displaystyle{ (2) }[/math], [math]\displaystyle{ (3,7,5) }[/math] и [math]\displaystyle{ (6) }[/math] длин [math]\displaystyle{ 2,1,3,1 }[/math]. Степень перестановки — [math]\displaystyle{ \text{НОК}(2,1,3,1)=6 }[/math].

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

$p\in\mathbb{N}$ — степень перестановки $\pi$, если $p$ — наименьшее из таких натуральных чисел, что $\pi^p = e$.

Пусть $\pi\in\sigma_n$, $\pi = \pi_1\circ\pi_2\circ \cdots\circ\pi_m$ — разложение $\pi$ на непересекающиеся циклы; $n_i$ — длина цикла $\pi_i$. Степень перестановки определяется как наименьшее общее кратное длин ее циклов: $\textrm{Степень }\pi = \textrm{НОК} (n_1, n_2,...,n_m)$.

Доказательство. Пусть число $p\in\mathbb{N}$ таково, что $\pi^p = e$. Тогда $\pi_1^p\circ\pi_2^p\circ \cdots\circ\pi_m^p=e$. Поскольку все перестановки $\pi_i$ воздействуют на разные элементы $\{1,2,...,n\}$, то $\pi_i^p = e$, $i=\overline{1, m}$. Следовательно, $p$ является общим кратным для $n_1$, $n_2$, ..., $n_m$. С другой стороны, пусть $q = \textrm{НОК} (n_1, n_2,...,n_m)$. Тогда $\pi_i^q = \pi_i^{n_i\cdot t}=e$, $i=\overline{1, m}$, и $\pi^q = \pi_1^q\circ\pi_2^q\circ \cdots\circ\pi_m^q=e.$

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