Дополнение 2 к главе 2. Элементарные сведения из теории подстановок c) Перестановки

В теории определителей часто используют понятия и факты, относящиеся к теории конечных множеств. Пусть дано некоторое конечное множество M, состоящее из n элементов. Эти элементы могут быть пронумерованы при помощи первых n натуральных чисел 1, 2, …, n, и т.к. в интересующих нас вопросах индивидуальные свойства элементов множества M не будут играть большой роли, то обычно полагают, что элементами множества M служат сами числа 1, 2, …, n.

Помимо употреблявшегося расположения чисел 1, 2, …, n в их нормальном порядке, их можно упорядочить и многими другими способами. Так, числа 1, 2, 3, 4 расположить следующими способами: 3, 1, 2, 4 или 2, 4, 3, 1 и т.д. всякое расположение чисел 1, 2, …, n в некотором порядке называется перестановкой из n чисел.

Предложение 1. Число всех перестановок n элементов равно (читается «эн-факториал»).

 Действительно, общий вид перестановки из n элементов есть , где каждый из есть одно из чисел 1, 2, …, n, причем ни одно из этих чисел не встречается дважды. В качестве можно взять любое из чисел 1, 2, …, n; это дает n различных возможностей. Если уже выбрано, то в качестве можно взять лишь одно из оставшихся n–1 чисел, т.е. число различных способов выбрать элементы и равно произведению n(n–1) и т.д. 

Пусть – некоторая перестановка чисел 1, 2, …, n. Пара элементов , i<j, образует инверсию, если . Возьмем, например, перестановку 132; можно заметить, что число 3 находится впереди числа 2. Таким образом, в перестановке 132 наблюдается лишь одна инверсия. Число всех пар элементов перестановки, образующих инверсию, называется числом инверсий в перестановке и обозначается . Так inv(3,5,1,4,2,6,8,7)=7 (инверсии образуют пары (3,1), (3,2), (5,1), (5,4), (5,2), (4,2), (8,7)).

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

D) Подстановки

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

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

. (2.20)

При такой записи различные подстановки отличаются друг от друга перестановками, стоящими в нижней строке, и поэтому число подстановок n-й степени равно числу перестановок из n элементов, т.е. равно n!

Примером подстановки n-й степени служит тождественная подстановка:

,

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

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

(2.21)

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

и

различны: при первой число 2 переходит в 4, при второй – в 3.

Назовём подстановку n-й степени чётной, если нижняя строчка её записи (2.1) образует чётную перестановку, и нечётной, если эта строчка образует нечётную перестановку. Т.о., все множество подстановок n-й степени разбивается на два класса – на класс чётных и на класс нечетных подстановок, причём подстановок того и другого класса будет, очевидно, по Если подстановка записана в общем виде (2.2), то её чётность определяется в зависимости от чётности или нечётности числа , где s – число инверсий в верхней строке и t – число инверсий в нижней строке.

Пример 2.15. Пусть дана подстановка

.

В её верхней строке 4 инверсии, а в нижней 7 инверсий. Общее число инверсий в двух строках есть 11, а потому подстановка нечётна.

Перепишем эту подстановку в виде

.

Число инверсий в верхней строке есть 0, в нижней 5, т.е. общее число снова нечётно. Видно, что при разных записях подстановки сохраняется чётность общего числа инверсий, но не само это число. 

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

и ,

то

.

Действительно, при подстановке A элемент 1 переходит в 3, но при B элемент 3 переходит в 4, поэтому при AB элемент 1 переходит в 4, и т.д.

Можно перемножать лишь подстановки одинаковой степени. Умножение подстановок n-й степени при n3 некоммутативно. Действительно, для рассмотренных выше подстановок A и B произведение BA имеет вид

,

т.е. подстановка BA отлична от подстановки AB.

Умножение подстановок ассоциативно, т.е. можно говорить о произведении любого конечного числа подстановок n-й степени, взятых (ввиду некоммутативности) в определённом порядке.

 В самом деле, пусть даны подстановки A, B и C и пусть элемент ₁, 1₁n, переходит при подстановке A в элемент ₂, элемент ₂ при подстановке B переходит в элемент ₃, а последний при подстановке C – в символ ₄. Тогда при подстановке AB элемент ₂ переходит в ₃, при подстановке BC элемент ₂ переходит в ₄, а потому как при (AB)C, так и при A(BC) элемент ₁ будет переходить в элемент ₄. 

Очевидно, что произведение любой подстановки A на тождественную подстановку E, а также произведение E на A, равно A:

.

Назовём, наконец, обратной для подстановки A такую подстановку A^–1 той же степени, что

.

Легко видеть, что обратной для подстановки

служит подстановка

,

получающаяся из A переменной мест верхней и нижней строк.