2. Элементарные сведения теории перестановок.

Сейчас мы рассмотрим некоторые простейшие свойства совокупности перестановок элементов. Переставляемыми элементами мы будем считать числа натурального ряда.

Предложение 1. Число всех, перестановок элементов равно .

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

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

Пусть - некоторая перестановка чисел . Скажем, что пара элементов образует инверсию, если Число всех пар элементов перестановки, образующих инверсию, называется числом инверсий в перестановке и обозначается . Так, (инверсии образуют пары (8, 7)).

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

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

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

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

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

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

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

Предложение 2. Пусть в некоторой перестановке сделана транспозиция. Она равна произведению нечетного числа транспозиций соседних элементов.

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

и транспозиция меняет местами с и h. Обозначим через число элементов , лежащих между . Переставим местами с , затем . После этого мы придем к перестановке

Мы сделали последовательно m транспозиций. Теперь переставим с и . Придем к

Теперь «перегоним» h на место, которое занимало с, переставив h по очереди . Мы придем к перестановке

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

Предложение 3. При транспозиции соседних элементов число инверсий в перестановке меняется на одну единицу.

Доказательство. Нам нужно сравнить число инверсий в перестановках

и

Обозначим через число инверсий в парах, не содержащих элементов d и , в обеих перестановках соответственно; через число инверсий в парах, содержащих один из элементов через число инверсий в паре и через t и i — полное число инверсий. Ясно, что

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

Наконец, если , то и если , то Поэтому , что и требовалось доказать.

Следствие 1. Если в перестановке сделать транспозицию соседних элементов, то четность перестановки изменится на противоположную.

Следствие 2. Любая транспозиция изменяет четность перестановки на противоположную.

Действительно, любая транспозиция равносильна нечетному числу транспозиций соседних элементов.

Предложение 4. Число четных перестановок элементов равно числу нечетных перестановок.

Доказательство. Пусть число четных перестановок равно а, число нечетных равно b. Рассмотрим множество всех четных перестановок. Сделаем в них одну и ту же транспозицию, например, (1, 2). Мы получим нечетные перестановки, попарно различные, в количестве а штук. Так как число всех нечетных перестановок равно b, заключаем, что а .b. Теперь рассмотрим множество всех нечетных перестановок и сделаем в них транспозицию (1, 2). Мы получим b четных перестановок и, следовательно, b а. Из установленных неравенств следует, что , что и требовалось доказать.

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

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

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

В терминах подстановок предложение можно переформулировать так: любая подстановка может быть представлена в виде произведения транспозиций.

Переход от одной перестановки к другой посредством транспозиций совершенно не однозначен. Однако в силу предложения 3 четность или нечетность числа транспозиций для такого перехода инвариантна.

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