Подстановки и произведения циклов

Перестановка множества может быть записана в виде подстановки, например:

где и

Перестановку также можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например:

Теперь разобьем все п\ перестановок п элементов на два класса, по признаку, кажущемуся довольно искусственным, но именно это разбиение будет нужно для разумного правила расстановки знаков в определителе.

Пусть (а,, о&2, •••, OLn)—некоторая перестановка чисел 1, 2,... п. Скажем, что пара элементов (а,-, а;), і <С/, образует инверсию, если сх< > а/. Число всех пар элементов перестановки, образующих инверсию, называется числом инверсий в перестановке и обозначается inv(cxi, а?, ап). Так, inv(3, 5, 1, 4, 2, 6,

8, 7) = 7 (инверсии образуют пары (З, 1), (3, 2), (5, 1), (5, 4),

Перестановки, содержащие четное число инверсий, называются четными, содержащие нечетное число инверсий — нечетными.

Подстановкой на множестве {1, 2, п} называется взаимно однозначное отображение множества на себя. Удобно задавать подстановку прямым указанием замен для каждого элемента, посредством записи образа под прообразом. Так, запись

1, 2, 3, 4, 5, соответственно, на 5, 1, 3, 2, 4; порядок расположения ее столбцов безразличен. В такой записи в «числителе» и в «знаменателе» оказываются перестановки. Удобно в «числителе» записывать элементы в натуральном расположении.

Последовательное применение двух подстановок приводит к подстановке, называемой их произведением. Так,

/ 1 2 3 4 5 6 \ / 1 2 3 4 5 6 \ _ / 1 2 3 4 5 6\ \5 2 1 6 4 3j"U 1 2 4 3 5 J-VS 1 6 5 4 2)

(мы считаем первой действующей ту подстановку, которая записана слева). Почти очевидно, что при умножении подстановок имеет место ассоциативность. Действительно, пусть а, х и ср — подстановки на-множестве {1, 2, п}. Сделать (от)ср— все равно, что сначала сделать а, потом т, затем ср; сделать же о (тер) — все равно, что сначала сделать о, потом тер, т. е. к результату применения о применить т и затем ср.

Тождественная подстановка, при которой каждому элементу сопоставляется он сам, играет роль единицы в этом умножении. Если запись подстановки а перевернуть, т. е. ее числитель сделать знаменателем, а знаменатель числителем, мы придем к обратной подстановке а~1, произведение которой на а как в одном, так и в обратном порядке, дает единичную подстановку. Умножение подстановок, вообще говоря, некоммутативно, например,

V2 1 ЗМ2 3 \) \Ъ 2 і)' \2 З l)\2 1.з)~\ 1 3 2)-

Число всех возможных подстановок на множестве из п элементов равно п\, ибо таково число возможных знаменателей при фиксированном числителе.

(5, 2), (4, 2), (8, 7)).

2 3 4 1 3 2

задает подстановку, которая заменяет элементы