ПРИБАВЛЕНИЕ. ПЕРЕСТАНОВКИ, МНОЖЕСТВА И ИХ ОТОБРАЖЕНИЯ; ГРУППЫ

§ 1. Перестановки

Боря, Володя и Шурик сидят в лодке в определенном порядке (считая, например, от иоса к корме лодки). Боря гребет на передних веслах, Володя — на средних, Шурнк — за рулем. Их можно пересадить шестью различными способами — существует шесть различных порядков, в которых они могут разместиться в лодке (считая все время от носа к корме), а именно:

Переход от одного из этих порядков к другому, т. е. само действие пересаживания мальчиков в лодке, называется перестановкой (или подстановкой).

Перестановка записывается так:

Это значит, что Володя сел на место Бори, Шурик — на место Володи, Боря — на место Шурика.

Следующее замечание при всей его очевидности очень важно. При этом перестановка элементов какого-нибудь множества, например множества гребцов на лодке, вполне определена, если указано, какой гребец сел на место какого. Именно это и только это указано в записи (1). Поэтому в записи (1) и вообще в записи любой перестановки совершенно несущественно, в каком порядке написаны элементы верхней строки. Та же перестановка (1) может быть, очевидно, записана и в виде

и в виде

Простейшими из перестановок являются так называемые транс позиции, это перестановки, при которых все элементы данного множества, кроме двух элементов, остаются неподвижными, а упомянутые два элемента меняются местами. Например:

В этой перестановке Боря, Володя, Шурик остались на месте, а Ваня и Витя поменялись местами.

Всякую перестановку можно осуществить, делая последовательно транспозиции (в лодке так и полагается пересаживаться, в особенности при волнении). Строгое доказательство этого факта (индукция по числу элементов множества) нетрудно и может быть предоставлено читателю.

Определение. Перемножить две перестановки, первую на вторую, - значит сделать сначала первую перестановку, потом вторую.

Например, пусть даны две перестановки:

В результате перестановки на место Володи сел Боря, но в результате второй перестановки на место Бори сел Володя. Значит, после двух перестановок Володя остался на месте. На место Шурика после перестановки сел Ваня, но в результате второй перестановки на место Вани сел Витя. Значит, после двух перестановок на место Шурика сел Витя. После первой перестановки на место Бори сел Володя, на место которого вторая перестановка посадила Ваню. В результате двух перестановок, сначала потом на место Бори сел Ваня. Так же убеждаемся в том, что после перестановок на место Вити сел Боря, а на место Вани — Шурик. Итак, произведение перестановок и есть перестановка

Мы записываем этот результат так:

т. е. пишем справа первую перестановку, а слева — вторую.

Заметим, что при перестановке Володя остался на месте. Если при данной перестановке элементов какого-нибудь множества все элементы этого множества Остаются на своих местах, то перестановка называется тождественной. Тождественная перестановка наших трех гребцов есть

Мы будем обозначать тождественную перестановку через Е (или ). При тождественной перестановке вообще не происходит, никакой перестановки Спрашиваете»: нужно ли ее рассматривать? Оказывается, нужно, так же как нужио, например, рассматривать покой как частный Случай движения, иначе излбженйе всей механики очень осложнилось бы. Мы сейчас убедимея в

Ко всякой перестановке существует однозначно определенная обратная к ней перестановка ; перестановка возвращает элементы, перемещенные перестановкой S, на первоначальные места.

Например, перестановка, обратная к перестановке

есть перестановка

или если в записи перестановки сохранить тот же порядок элементов первой строки, какой был в записи перестановки S, то та же перестановка записывается в виде

Очевидно, если есть перестановка, обратная к перестановке S, то S есть перестановка, обратная к перестановки S и суть взаимно обратные перестановки.

Очевидно также, что, если сделать сначала какую-нибудь перестановку, а потом — обратную к ней, мы получим тождественную перестановку:

Читатель легко докажет, что для данной перестановки S обратная перестановка есть единственная перестановка , удовлетворяющая какому-нибудь из условий

Тождественная перестановка есть единственная перестановка , удовлетворяющая для любой перестановки S каждому из уравнений

При этом, разумеется, все время рассматриваются перестановки одного и того же множества (например, множества трех гребцов на иашей лодке).

Мы уже подчеркивали, что, записывая данную перестановку в виде двух строк и указывая таким образом, какой элемент данного множества каким элементом этого же множества заменяется, мы вольны в верхней строке написать элементы нашего множества в любом порядке, лишь бы под каждым элементом верхней строки был подписан тот элемент, которым он заменяется. Поэтому можно раз навсегда занумеровать элементы данного множества натуральными числами, т. е. записать их в виде

а произвольную перестановку этих элементов записать в виде

эта запись показывает, что при перестановке S элемент заменился элементом элемент — элементом и т. д.

Но при этой записи все дело сводится к перестановке не самих элементов а их номеров так что, например, все шесть перестановок произвольных трех элементов — после того как эти элементы занумерованы какими-нибудь числами быть записаны в виде

Конечно, жаль расставаться с нашими гребцами в лодке и заменять их невыразительными цифрами, но делать нечего — так все получается гораздо короче.

Теперь мы можем сказать: перестановка

в множестве состоящем из чисел , заключается в том, что каждому элементу k множества ставится в соответствие элемент того же множества притом так, что различным k соответствуют различные

Это положение вещей выражают, говоря, что перестановка (1) есть взаимно однозначное отображение множества на себя.

Можно написать

и сказать, что перестановка есть функция (2) такая, что и значения аргумента , и значения функции суть числа , причем различным значениям аргумента соответствуют различные значения функции. Перестановка (1) вполне определена, если для каждого определено Отсюда сразу следует свойство ассоциативности (сочетательности) умножения перестановок, т. е. свойство, выражаемое формулой

т. е. если сначала сделать перестановку являющуюся произведением перестановок (в этом порядке), а затем — перестановку то это все равно, что сделать сначала перестановку а потом перестановку являющуюся произведением перестановки на перестановку . В самом деле, если записать перестановки соответственно в виде функций:

то и левая, и правая часть равенства (3) есть перестановка S, ставящая в соответствие элементу k множества X элемент

т. е.

Замечание 1. Свойством переместительности (коммутативности) умножение перестановок, вообще говоря, не обладает: если

то

Замечание 2. Если натуральные числа, являющиеся элементами множества записать в их естественном порядке

то каждая перестановка множества переводит этот порядок в какой-то порядок

и, обратно, каждый порядок получается в результате вполне определенной перестановки. Итак, различные порядки, в которых можно записать элементы множества взаимно однозначно соответствуют перестановкам в этом множестве. Поэтому число этих перестановок равно числу различных порядков в множестве . Докажем, что это число равно Это ясно, если тогда имеется лишь один порядок. Ясно это и для тогда имеется два порядка: 1, 2 и 2, 1. Предположим, что наше утверждение доказано для докажем его для . Каждому порядку

в котором можно написать числа соответствует различных порядков, полученных от присоединения числа а именно порядки

Так как по предположению всех порядков в которых можно написать числа имеется то всех порядков, в которых можно написать числа будет что и требовалось доказать.

Четные и нечетные перестановки. Пусть дана перестановка

Рассмотрим какую-нибудь пару различных элементов множества т. е. два натуральных числа , каждое из которых не превосходит . Пару назовем правильной по отношению к перестановке S, если разности и имеют один и тот же знак. В противном случае говорят, что наша пара неправильна по отношению к перестановке или образует в ней инверсию. Следовательно, если пара образует инверсию, то имеем либо либо, наоборот,

В тождественной перестановке Нет ни одной инверсии — все пары правильны.

В перестановке имеется единственная инверсия (1, 2).

В перестановке имеются две инверсии: (1, 3) и (2, 3).

Определение. Перестановка, содержащая четное число инверсий, называется четной перестановкой; перестановка, содержащая нечетное число инверсий, называется нечетной перестановкой.

Знаком перестановки называется число если перестановка четная, и число —1, если она нечетная. Назовем теперь знаком действительного числах число , если число — 1, если число 0, если Теперь ясно, что знак перестановки равен

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

Этим замечанием мы воспользуемся для доказательства следующего предложения:

Знак произведения двух перестановок равен произведению знаков этих перестановок.

Пусть даны две перестановки:

Их произведение есть, очевидно, перестановка

Знак А равен произведению всех знаков Знак В равен произведению всех знаков Однако можно также написать

поэтому имеем: знак В равен произведению всех знаков

Отсюда сразу следует:

что и требовалось доказать.

Из доказанной теоремы непосредственно следует: произведение двух перестановок одинаковой четности есть четная, а произведение двух перестановок различной четности нечетная перестановка. Тождественная перестановка Е не содержит ни одной инверсии и, следовательно, есть четная перестановка. Далее,

т. е. произведение данной перестановки А и обратной к ней есть четная перестановка; отсюда, но только что доказанному, следует, что любая перестановка имеет ту же четность, что и обратная ей. Итак, имеет место

Теорема 1. Произведение двух четных перестановок есть четная перестановка, тождественная перестановка есть четная перестановка; перестановка, обратная четной перестановке, есть четная перестановка.

Докажем теперь следующее предложение.

Лемма. Любая транспозиция

есть нечетная перестановка.

Для доказательства заметим, что какая-нибудь пара только тогда может образовать инверсию относительно перестановки S, когда одним из элементов этой пары есть какое-нибудь из чисел . Каждую пару будем записывать в ее естественном порядке: если

Ни одна пара вида инверсией не является, так как в имеем

Среди пар инверсиями являются пары всего инверсий.

Пары где инверсиями не являются, так как в имеем . Нет инверсий среди пар .

Пара есть инверсия, но мы ее уже считали. Среди пар имеются инверсии

всего инверсий.

Наконец, ни одна из пар инверсией не является. Итак, в нашей транспозиции S имеем всего

— нечетное число инверсий.

Лемма доказана.

Из теоремы 1 и из леммы вытекает

Теорема 2. Всякая перестановка, являющаяся произведением четного числа транспозиций, является четной перестановкой, а всякая перестановка, являющаяся произведением нечетного числа транспозиций, есть нечетная перестановка.

Так как всякая перестановка есть произведение некоторого числа транспозиций, то из теоремы 2 следует, что нечетные, соответственно четные, перестановки могут быть определены как перестановки, которые являются произведением нечетного, соответственно четного, числа транспозиций.

Замечание 3. Данная перестановка может быть, вообще говоря, различным образом представлена в виде произведения транспозиций, и число множителей в различных этих представлениях может быть различным; однако из доказанного следует, что по всех представлениях одной и той же перестановки в виде произведения транспозиций четность числа множителей всегда одна и та же.

Замечание 4. Число четных и число нечетных среди перестановок данных элементов одинаково и равно . В самом деле, пусть все четные перестановки в суть

Умножив каждую из этих перестановок на одну и ту же нечетную, например на одну какую-нибудь транспозицию, которую обозначим через получим нечетные перестановки

Все эти перестановки различны между собою. В самом деле, если бы, положим, было

то, умножая обе части этого тождества на получили бы

т. е. (так как есть тождественная перестановка)

вопреки тому, что — различные перестановки. Итак, все к нечетных перестановок (5) различны между собою. Я утверждаю, что всякая нечетная перестановка есть одна из перестановок (5). В самом деле, перестановка есть четная перестановка (так как есть транспозиция, a S — нечетная перестановка), поэтому есть одна из перестановок Пусть . Умножая обе части этого тождества на транспозицию получим .

Итак, перестановки ( - это все нечетные перестановки; их число равно k, т. е. числу всех четных перестановок. Значит, есть число всех перестановок из элементов,

что и требовалось доказать.