Тип перестановки

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

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

Обозначим

$\sigma_n (c_1, c_2, ..., c_n) = \{\pi

Замечание

$c(\pi) = c_1(\pi) + \cdots + c_n(\pi)$ — число циклов перестановки и $n = \sum_{i=1}^n i\cdot c_i(\pi)$.

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

[math]\displaystyle{ |\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]

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

Множество $\{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]

[math]\displaystyle{ \blacksquare }[/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).

Рис. 1. Одну перестановку типа [math]\displaystyle{ (0,2,1,\ldots) }[/math] можно записать [math]\displaystyle{ 2!\cdot2^2\cdot3=24 }[/math] способами: переставить два 2-цикла, повернуть каждый из них и повернуть 3-цикл. Поэтому [math]\displaystyle{ 7!/24=210 }[/math].

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