Дискретно-непрерывная математика (стр. 31 )

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

и

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

Пусть дана подстановка

А= (2.12)

Если

Р= (2.13)

есть какая-нибудь подстановка тех же чисел 1, 2, 3, ... , п, то подстановка (2.12) может быть записана в виде

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

А=

Рассмотрим множество, которое состоит из двух каких-нибудь чисел набора 1, 2,... , п, положим для определенности из чисел i и k. Такое множество назовем парой чисел, а именно парой, которая состоит из элементов i и k; обозначим ее (i, k).

Здесь с понятием пары не связано никакое предположение о порядке следования элементов пары: (i, k) и (k, i) суть два записи одной и той же пары. Такие пары элементов, взятые из числа данных п элементов, называются также сочетаниями из п элементов по 2.

Число всех пар, которые можно составить из данных п элементов, нетрудно подсчитать. Сначала вычислим, сколько различных упорядоченных подмножеств из двух элементов содержится в множестве из п элементов. Обозначим число таких подмножеств через А2п и покажем, что

А2п = п(п-1).

Действительно, для того чтобы распределить два элемента, взятых из данных п элементов, по двум местам, можно сначала выбрать какой-нибудь один элемент и поместить его на первое место. Это можно сделать п способами. На второе место теперь остается п — 1 «кандидатов» и значит, п — 1 способ выбора второго элемента. Следовательно, всего мы получим п(п— 1) способов размещения, что и требовалось доказать.

Пусть С2п — число всех пар, которые можно составить из п элементов. Покажем, что

С2п= А2п

или, что то же самое,

А2п =2 С2п

В самом деле, чтобы образовать упорядоченное множество, которое содержит два элемента из данных п, необходимо выделить какие-либо два с этих п элементов, что можно сделать С2п способами, а затем упорядочить выделенные два элемента, что можно сделать двумя способами. Итак,

А2п =2 С2п

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

Пара, которая состоит из элементов i и k, называется правильной по отношению к подстановке А, если разности i — k и аі — аk имеют один и тот же знак; это значит: если i<k, то должно быть aі<ak; если же i > k, то должно быть аі > ak. В противном случае говорят, что наша пара неправильна в подстановке А или образует в ней инверсию. Следовательно, если пара (i, k) образует инверсию, то имеем или i<k и ai>ak или, наоборот, i > k и aі<ak. Рассмотрим, в качестве примера, подстановки группы S3.

В подстановке Р0= нет ни одной инверсии — все пары правильны.

В подстановке Р1= имеется единственная инверсия (2, 3), так как при і = 2, k = 3 имеем аі = 3 и ak = 2.

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

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

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

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

Мы видим, что в группе S3 четные подстановки (Р0, Р3 и Р4) образуют подгруппу. Наша задач - доказать, что это замечание справедливо для любой группы Sn.

Доказательство опирается на некоторые следующие предварительные замечания.

Знаком подстановки А называется число +1, если подстановка А четная, и число —1, если она нечетная.

Отвлекаясь от обычного словоупотребления, назовем теперь знаком рационального числа r число +1, если число r положительно, число — 1, если r отрицательно, и число 0, если r = 0. Знак числа r в только что установленном смысле обозначим так: (зн r).

При этих обозначениях ясно, что знак подстановки А равен произведению знаков всех чисел , причем дробь

=

строится по одному разу для каждой пары, взятой из чисел 1, 2, 3, ... , п.

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

Теорема 1. Знак произведения двух подстановок равен произведению знаков сомножителей.

Доказательство. Пусть даны две подстановки:

А= , В=

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

А• В=

Знаки А и В равны соответственно произведениям всех знаков

и

Но так как можно также написать

В=

то имеем:

знак В равен произведению всех знаков .

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

(зн А) • (зн В) =произведению всех (зн ) • (зн ) =

= произведению всех (зн • зн ) =

= произведению всех (зн ).

Но последнее произведение есть знак подстановки

т. е. подстановки А • В, что и требовалось доказать.

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

А• А-1 = Е

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

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

Отсюда следует, что совокупность всех четных подстановок из п элементов есть подгруппа группы Sn всех вообще подстановок из п элементов. Группа четных подстановок из п элементов называется знакопеременной или альтернирующей группой подстановок из п элементов, и обозначается через Ап.

Теорема 2. Порядок группы Ап равен .

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

1) каждой четной подстановке будет соответствовать нечетная подстановка;

2) двум различным четным подстановкам будут соответствовать различные нечетные подстановки;

3) каждая нечетная подстановка В окажется поставленной в соответствие одной (и только одной) четной подстановке, а именно: четной подстановке Р-1• В.

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

2.4. Изоморфные и циклические группы

Рассмотрим, с одной стороны, группу поворотов R3 правильного треугольника, а с другой стороны, группу, которая содержится в группе всех подстановок из трех цифр подгруппу А3, которая состоит из трех элементов Р0 , P3, P4. Мы обозначили элементы группы R3 через а0, а1, а2. Установим теперь между элементами группы R3 и элементами группы А3 следующее взаимно-однозначное соответствие: