Тип перестановки
Обозначим
$\sigma_n (c_1, c_2, ..., c_n) = \{\pi
Множество $\{1,...,n\}$ можно разбить на подмножества, среди которых ровно $c_i$ подмножеств имеют мощность $i$, [math]\displaystyle{ \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]\displaystyle{ \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).
Конспект: Дискретная математика