Упражнение 9. - теорема о числе подстановок, разлагающихся на опр. количество циклов определенного порядка

Теорема. Симметрическая группа $\mathfrak{S}_n$ содержит ровно
$$
{n!\over{n_1^{k_1}n_2^{k_2}......n_s^{k_s}k_1!k_2!......k_s!}}
$$
$(n = k_1 n_1 + k_2 n_2 + ...... + k_s n_s)$ подстановок, разлагающихся на $k_1$ циклов порядка $n_1$, $k_2$ циклов порядка $n_2$,......, $k_s$ циклов порядка $n_s$, где $ n_1 \gt n_2 \gt ..... \gt n_s $. (Циклы длины 1 также учитываются.)

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

Мы знаем, что каждая подстановка разлагается единственным образом в произведение непересекающихся циклов.

Пусть дана подстановка $A\in\mathfrak{S}_n$, разлагающаяся на $k_i$ циклов порядка $n_i$, $i=1, \ ...,\ s$:
$$
A=(...)(...)...(...).
$$
Сколькими способами можно переставить элементы $1,\ ...,\ n$ в последней формуле, чтобы подстановка $A$ осталась прежней? Покажем, что таких способов ровно
$$
{n_1^{k_1}n_2^{k_2}......n_s^{k_s}k_1!k_2!......k_s!}.
$$

Пусть $t$ --- количество циклов в подстановке. Доказывать будем индукцией по $t$.
Для подстановок, состоящих из одного цикла, формула доказана --- существует ровно $n_1$ способов записать один ($k_1=1$) цикл длины $n_1$:
$$
n_1^{k_1}\cdot k_1!=n_1^1\cdot 1!=n_1.
$$
Предположим, что теорема доказана для случая $t-1$ и докажем её для подстановок, разлагающихся в произведение $t$ непересекающихся циклов.

Пусть подстановка $B$ состоит из $t$ непересекающихся циклов:
$$
B=(...)(...)...(...).
$$
Пусть $B$ состоит из $k_i$ циклов порядка $n_i$, $i=1, \ ...,\ s$. (Для каждой подстановки число $s$, конечно, своё.)

Зафиксируем элементы последнего цикла (обозначим его $C$) в представлении подстановки $B$. Пусть длина $C$ равна $n_s$. Возможны два варианта:

1. в $B$ нет отличных от $C$ циклов, равных по длине циклу $C$. Тогда $k_s=1$.

   По индуктивному предположению, при фиксированных элементах цикла $C$, существует ровно
   $$
   n_1^{k_1}n_2^{k_2}......n_{s-1}^{k_{s-1}}k_1!k_2!......k_{s-1}!
   $$
   способов перестановки элементов, чтобы подстановка осталась равной $B$. Записать $C$ cуществует ровно $n_s$ способов (циклический сдвиг). Поэтому
   $$
   ({n_1^{k_1}n_2^{k_2}......n_{s-1}^{k_{s-1}}k_1!k_2!......k_{s-1}!})\cdot n_s={n_1^{k_1}n_2^{k_2}......n_{s-1}^{k_{s-1}}n_s^{k_s}k_1!k_2!......k_{s-1}!k_s},
   $$
   так как $n_s^{k_s}=n_s^1=n_s$ и $k_s!=1!=1$.

2. В $B$ есть циклы, отличные от $C$ и равные ему по длине. По индуктивному предположению, при фиксированных элементах цикла $C$, существует ровно
   $$
   n_1^{k_1}n_2^{k_2}......n_{s}^{(k_{s}-1)}k_1!k_2!......(k_{s}-1)!
   $$
   способов перестановки элементов, чтобы подстановка осталась равной $B$. Записать $C$ cуществует ровно $n_s$ способов (циклический сдвиг), и также существует ровно $k_s$ циклов, на место которых можно поставить $C$. Поэтому
   $$
   ({n_1^{k_1}n_2^{k_2}......n_{s}^{(k_{s}-1)}k_1!k_2!......(k_{s}-1)!})\cdot k_s \cdot n_s=
   {n_1^{k_1}n_2^{k_2}......n_{s}^{k_{s}}k_1!k_2!......k_{s}!}.
   $$

Теперь, существует ровно $n!$ способов переставить элементы $1,\ ...,\ n$ в представлении подстановки $B$ в непересекающихся циклах. Таким способом мы получим все подстановки из $\mathfrak{S}_n$, состоящие из $k_i$ циклов порядка $n_i$, $i=1, \ ...,\ s$. Среди этих перестановок лишь
$$
{n_1^{k_1}n_2^{k_2}......n_{s}^{k_{s}}k_1!k_2!......k_{s}!}
$$
представляют $B$. Поэтому
$$
\frac{n!}{n_1^{k_1}n_2^{k_2}......n_{s}^{k_{s}}k_1!k_2!......k_{s}!}.
$$

Теорема доказана.

Примеры

Проверим эту формулу на примере $\mathfrak{S}_4$, мы получим:

• для тождественных подстановок число $\displaystyle{4!\over{4!}} = 1$,
• для транспозиций -- число $\displaystyle{4!\over{2!2!}} = 6$,
• для двойных транспозиций -- число $\displaystyle \displaystyle {4!\over{2^2 2!}} = 3$,
• для двойных трехчленных циклов -- число $\displaystyle{4!\over{3}} = 8$,
• для двойных трехчленных циклов -- число $\displaystyle {6!\over{4}} = 6$.