СВ: /* Пример */

2026-10-24T13:43:45Z

Пример

← Предыдущая		Версия 13:43, 24 октября 2026
Строка 92:		Строка 92:
	* (4, 3, 1, 2, 7, 5, 6),		* (4, 3, 1, 2, 7, 5, 6),
	* (4, 3, 2, 1, 7, 5, 6).		* (4, 3, 2, 1, 7, 5, 6).

			[[Файл:p28-01-permutation-type-count.svg\|frame\|none\|800px\|alt=Перестановка (1,2)(3,4)(5,6,7) и множители 2!, 2², 3, дающие 24; внизу 7!/24=210\|Рис. 1. Одну перестановку типа <math>(0,2,1,\ldots)</math> можно записать <math>2!\cdot2^2\cdot3=24</math> способами: переставить два 2-цикла, повернуть каждый из них и повернуть 3-цикл. Поэтому <math>7!/24=210</math>.]]


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

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

СВ: Новая страница: «{{Определение |definition= Пусть $c_i = c_i(\pi)$ {{---}} число циклов длины $i$ перестановки $\pi$. Тогда $(c_1...»

2026-10-11T10:01:32Z

Новая страница: «{{Определение |definition= Пусть $c_i = c_i(\pi)$ {{---}} число циклов длины $i$ перестановки $\pi$. Тогда $(c_1...»

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

{{Определение
|definition=
Пусть $c_i = c_i(\pi)$ {{---}} число циклов длины $i$ перестановки $\pi$. Тогда $(c_1, c_2, ..., c_n)$ {{---}} тип перестановки $\pi$.

Обозначим
$\sigma_n (c_1, c_2, ..., c_n) = \{\pi | \pi\in\sigma_n, (c_1, c_2, ..., c_n) \textrm{ {{---}} тип } \pi\}$.
}}
{{Замечание
|content=$c(\pi) = c_1(\pi) + \cdots + c_n(\pi)$ {{---}} число циклов перестановки и $n = \sum_{i=1}^n i\cdot c_i(\pi)$.
}}
{{Утверждение
|statement=<math>|\sigma_n (c_1, c_2, ..., c_n)| = \frac{n!}{c_1! c_2! \cdots c_n! 1^{c_1}2^{c_2}\cdots n^{c_n}}</math>
|proof=Множество $\{1,...,n\}$ можно разбить на подмножества, среди которых ровно $c_i$ подмножеств имеют мощность $i$,
<math>\frac{n!} {c_1! c_2! \cdots c_n! (1!)^{c_1} (2!)^{c_2}\cdots (n!)^{c_n}}</math> способами.
Чтобы получить перестановку из любого неупорядоченного разбиения, нужно расставить элементы каждого подмножества в определенном порядке, чтобы определить циклы.

Сколько циклов можно получить из одного подмножества мощности $i$?

Элементы множества можно расставить в различном порядке $i!$ способами.

Это число надо разделить на количество вариантов выбора начальный точки цикла {{---}} $i$.

Таким образом, из данного подмножества можно составить $\frac{i!}{i}$ различных циклов.

Домножим число неупорядоченных разбиений на число вариантов создания циклов из подмножеств.
Получим:
<math>\frac{n!}{c_1! c_2! \cdots c_n! (1!)^{c_1} (2!)^{c_2}\cdots (n!)^{c_n}}
\cdot
\frac{(1!)^{c_1} (2!)^{c_2}\cdots (n!)^{c_n}}{1^{c_1} 2^{c_2}\cdots n^{c_n}}
=\frac{n!}{c_1! c_2! \cdots c_n! 1^{c_1} 2^{c_2}\cdots n^{c_n}}
</math>
}}

Утверждение может быть доказано и напрямую, если посчитать, сколькими способами можно получить перестановку типа
$(c_1, c_2, ..., c_n)$ из перестановок в $\sigma_n$, различным образом расставляя скобки.

Чтобы узнать это число, рассмотрим произвольную перестановку $(c_1, c_2, ..., c_n)$ представленную в виде произведения циклов:
\begin{equation*}\tag{$\star$}
\pi = \pi_1^{(1)}\circ ...\circ \pi_{c_1}^{(1)}\circ\pi_1^{(2)}\circ
...\circ \pi_{c_2}^{(2)}\circ
\pi_1^{(3)}\circ...\circ\pi_{c_n}^{(n)},
\end{equation*}
где $\pi_i^{(j)}$ {{---}} $i$-тый цикл нашей перестановки длины $j$.

Как мы замечали раньше, поскольку циклы перестановки воздействуют на разные элементы, перестановки в этом произведении можно расставлять в произвольном порядке.
Сколькими способами мы можем переставить циклы таким образом, чтобы сначала в записи шли все циклы длины 1, затем все циклы длины 2 и т.д.?
Очевидно, $c_1!\cdot c_2!\cdot ... \cdot c_n!$ способами.

Теперь посчитаем, сколькими способами можно переставить элементы в скобках, обозначающих циклы. Если $\pi_i^{(j)}$ в нашей записи
обозначает цикл $(a_{l_1}, ..., a_{l_j})$, то ясно, что первый элемент в последовательности можно выбрать $j$ способами и, значит, у нас
есть $j$ способов расставить числа $a_{l_1}$, ..., $a_{l_j}$ в скобках, чтобы запись означала один и тот же цикл.

Таким образом, для всех циклов перестановки у нас есть $1^{c_1}\cdot 2^{c_2}\cdot ... \cdot n^{c_n}$ способов переставить элементы в циклах, чтобы запись означала все ту же исходную перестановку $\pi$.

Рассмотрим следующее отображение $f$. Любой перестановке $\pi$ типа $(c_1, c_2, ..., c_n)$ сопоставим все перестановки (как мы подсчитали, их будет $c_1! c_2! \cdots c_n! 1^{c_1} 2^{c_2} \cdots n^{c_n}$) которые получаются, если произвольным образом перемешивать в произведении $(\star)$ циклы одинаковой длины, а для каждого цикла переставлять его элементы в записи по кругу.
Оказывается, образы для разных перестановок типа $(c_1, c_2, ..., c_n)$ не пересекаются (отображение инъективно) и каждая перестановка из $\sigma_n$ входит в образ одной из перестановок типа $(c_1, c_2, ..., c_n)$ (отображение сюръективно).

Значит мы построили взаимно-однозначное соответствие между множеством перестановок типа $(c_1, c_2, ..., c_n)$
и разбиением множества перестановок $\sigma_n$ на группы по $c_1! c_2! \cdots c_n! 1^{c_1} 2^{c_2} \cdots n^{c_n}$ штук.
Поделив мощность $\sigma_n$ на количество перестановок, сопоставленных каждой перестановке типа $(c_1, c_2, ..., c_n)$,
получим формулу из утверждения.

== Пример ==
Пусть задан тип перестановки $(0,2,1,0,0,0,0)$.
Согласно утверждению, число перестановок такого типа должно быть
$\frac{7!}{0!2!1!0!0!0!0! 1^0 2^2 3^1 4^0 5^0 6^0 7^0}= \frac{7!}{24} =7\cdot 6\cdot 5=210$, где $24$ {{---}} число перестановок,
из которых можно получить одну и ту же перестановку типа $(0,2,1,0,0,0,0)$.
Рассмотрим, например, перестановку $(1,2)(3,4)(5,6,7)$. Из каких перестановок она может быть получена добавлением скобок?
Перечислим такие перестановки:
* (1, 2, 3, 4, 5, 6, 7),
* (2, 1, 3, 4, 5, 6, 7),
* (1, 2, 4, 3, 5, 6, 7),
* (2, 1, 4, 3, 5, 6, 7),
* (1, 2, 3, 4, 6, 7, 5),
* (2, 1, 3, 4, 6, 7, 5),
* (1, 2, 4, 3, 6, 7, 5),
* (2, 1, 4, 3, 6, 7, 5),
* (1, 2, 3, 4, 7, 5, 6),
* (2, 1, 3, 4, 7, 5, 6),
* (1, 2, 4, 3, 7, 5, 6),
* (2, 1, 4, 3, 7, 5, 6),
* (3, 4, 1, 2, 5, 6, 7),
* (3, 4, 2, 1, 5, 6, 7),
* (4, 3, 1, 2, 5, 6, 7),
* (4, 3, 2, 1, 5, 6, 7),
* (3, 4, 1, 2, 6, 7, 5),
* (3, 4, 2, 1, 6, 7, 5),
* (4, 3, 1, 2, 6, 7, 5),
* (4, 3, 2, 1, 6, 7, 5),
* (3, 4, 1, 2, 7, 5, 6),
* (3, 4, 2, 1, 7, 5, 6),
* (4, 3, 1, 2, 7, 5, 6),
* (4, 3, 2, 1, 7, 5, 6).

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

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

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

СВ: /* Пример */

СВ: Новая страница: «{{Определение |definition= Пусть $c_i = c_i(\pi)$ {{---}} число циклов длины $i$ перестановки $\pi$. Тогда $(c_1...»