Разложение подстановок на транспозиции

(в процессе)

Разложение подстановок на транспозиции. Покажем, что всякую подстановку можно представить в виде произведения нескольких транспозиций, т.е. подстановок, перемещающих две цифры и оставляющих остальные цифры неизменными. Выше мы видели, что всякую подстановку можно представить в виде произведения циклов. Поэтому достаточно проверить наше утверждение для цикла. Последнее проверить нетрудно. В самом деле:
$$
(123) = (12)(13),\\
(1234) = (12)(13)(14)\\
................\\
(123 ...... m) = (12)(13) ...... (1m)
$$
Обратим здесь внимание на то, что циклы с четным числом цифр разлагаются на нечетное число транспозиций, с нечетным числом цифр - на четное число транспозиций.

Поэтому для каждой данной подстановки мы можем высчитать, разложится ли она на четное или на нечетное число транспозиций. Действительно, если подстановка состоит из циклов порядков:
$$n_1, n_2, \ldots, n_k \;\;\;\; (n_1 + n_2 + \ldots +n_k=n)$$
то четность получаемого числа транспозиций зависит от того, будет ли число (разница между числом элементов в подстановке и числом циклов):
$$
(n_1-1)+(n_2-1)+\ldots+(n_k-1)=n-k
$$

четным или нечетным. При этом мы должны также принять в расчет и одночленные циклы.

Пример. Подстановка $(123)(45)(67)(8)$. Число $(n-k)$ здесь равно $8-4=4$, а потому подстановка разлагается на четное число транспозиций.