СВ в 13:42, 24 октября 2026

2026-10-24T13:42:34Z

← Предыдущая		Версия 13:42, 24 октября 2026
Строка 137:		Строка 137:
	$\pi(6)=6, \Rightarrow B_4 = \{6\}$.		$\pi(6)=6, \Rightarrow B_4 = \{6\}$.
	Представление перестановки $\pi$ в виде произведения циклов имеет вид $\pi = (1,4)(2)(3,7,5)(6)$.		Представление перестановки $\pi$ в виде произведения циклов имеет вид $\pi = (1,4)(2)(3,7,5)(6)$.

			[[Файл:p27-01-cycle-decomposition.svg\|frame\|none\|900px\|alt=Циклы (1,4), (2), (3,7,5), (6) и вычисление степени НОК(2,1,3,1)=6\|Рис. 1. Перестановка распадается на циклы <math>(1,4)</math>, <math>(2)</math>, <math>(3,7,5)</math> и <math>(6)</math> длин <math>2,1,3,1</math>. Степень перестановки — <math>\text{НОК}(2,1,3,1)=6</math>.]]

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

СВ в 09:56, 11 октября 2026

2026-10-11T09:56:19Z

← Предыдущая		Версия 09:56, 11 октября 2026
Строка 151:		Строка 151:
	С другой стороны, пусть $q = \textrm{НОК} (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.$		Тогда $\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.$

			[[Категория:Дискретная математика]]

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

СВ: Новая страница: «Будем обозначать $\pi^k = \underbrace{\pi\circ\pi\circ \cdots \circ \pi}_k$; $\pi^0 = e$; $\pi^{-k} = \underbrace{\pi^{-1}\circ\pi^{-1} \circ \c...»

2026-10-09T19:54:51Z

Новая страница: «Будем обозначать $\pi^k = \underbrace{\pi\circ\pi\circ \cdots \circ \pi}_k$; $\pi^0 = e$; $\pi^{-k} = \underbrace{\pi^{-1}\circ\pi^{-1} \circ \c...»

Новая страница

Будем обозначать
$\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$.

{{Определение
|definition=Циклом длины $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))$.
{{Определение
|definition=
Транспозиция {{---}} перестановка элементов множества $\{1,2,...,n\}$, которая меняет местами только два элемента.
}}
{{Замечание
|content=Транспозиция {{---}} цикл длины 2.
}}
{{Утверждение
|statement=Пусть $\pi\in\sigma_n$ и $i\in\{1,...,n\}$. Тогда существует такое число $k\in\mathbb{N}$, что $\pi^k(i) = i$.
|proof=Пусть $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}$ тоже должен повториться.
Противоречие доказывает утверждение.
}}

Для произвольной перестановки $\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>
(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>
\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>\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)$.

{{Определение
|definition=
$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.$

Циклы перестановки - История изменений

СВ в 13:42, 24 октября 2026

СВ в 09:56, 11 октября 2026

СВ: Новая страница: «Будем обозначать $\pi^k = \underbrace{\pi\circ\pi\circ \cdots \circ \pi}_k$; $\pi^0 = e$; $\pi^{-k} = \underbrace{\pi^{-1}\circ\pi^{-1} \circ \c...»