Перестановки
Рассмотрим последовательность натуральных чисел 1, 2, 3 ... , n и зададимся вопросом: сколькими способами можно переставить попарно числа в этой последовательности, чтобы получить новую последовательность? Другими словами, сколько существует различных последовательностей из всех натуральных конечных чисел n?
Прежде чем ответить на этот вопрос, дадим одно важное определение из комбинаторики.
Определение. Всякое расположение натуральных чисел 1, 2, 3, ... , n в некотором определенном порядке называется перестановкой из n чисел (или из n символов). В общем случае перестановкой считают множество объектов любой природы, скажем
Ведь можно переставлять и эти объекты (не обязательно числа). А просто пронумеровать каждый объект (смотри индексы у X) и составить перестановки из натуральных чисел, как по определению.
Например, числа 1, 2, 3, 4 можно переставить следующим образом: 1, 3, 2, 4 или 2, 4, 1, 3 и т.д. Теперь давайте ответим на вышестоящий вопрос: сколько можно составить таких перестановок? Ответ очевидно будет n!. Действительно, рассмотрим перестановку в общем виде:
И в качестве i1 возьмем любое число из 1, 2, 3, ... , n. Очевидно, что n способами можно поставить на первое место в перестановке любое число. Таким образом у нас остается n - 1 чисел в натуральном ряду. На второе место, вместо i2 извлекаем n - 1 любых чисел, и столькими же способами можно выбрать число на второе место в подстановке и т.д. Значит чтобы выбрать на первые два места в перестановке числа мы можем перебрать n(n - 1) способов. Рассуждая индуктивно, приходим к выводу что можно составить n(n - 1)(n - 2)...3*2*1, т.е. n! комбинаций различных перестановок.
Таким образом, перестановок из чисел 1 и 2 существует всего две, это 12 и 21. Из трех чисел можно составить 3! = 6 перестановок. Из четырех можно составить 4! = 24 перестановок и т.д. С ростом n число перестановок очень быстро растет, уже при n = 10 имеется 3628800 перестановок!
Транспозиции. Чётные и нечётные перестановки
Определение. Операция перехода от одной перестановки к другой, при которой два числа меняются местами, а остальные остаются на своих местах, называется транспозицией.
Например, запишем следующую транспозицию следующим образом:
( 1 6 2 4 3 5 ) => ( 1 3 2 4 6 5 )
где 6 и 3 поменялись местами. Или пример шести транспозиций, переводящие перестановку ( 5 1 7 4 2 3 6 ) в ( 3 4 1 5 7 6 2):
Таким образом, вытекает следующая:
Теорема 1. От произвольной перестановки можно перейти к любой другой при помощи нескольких последовательно выполненных транспозиций.
Доказательство мы опустим в этой статье, интересующийся читатель может найти доказательство в любом учебнике по теории перестановок. Далее мы везде будем опускать доказательства теорем для сокращения объема статьи.
Определение. Пусть имеется некоторая перестановка чисел из 1, 2, 3, ..., n. Если некоторое число i из этой перестановки больше, чем некоторое число j из этой же перестановки (i > j), причем i предшествует j, то говорят, что эта пара чисел составляет инверсию. Число пар, образующих инверсию, называют числом инверсий перестановки.
Например, перестановка ( 4 5 1 3 6 2 ) содержит 8 инверсий. А именно,
( 4 1 ) ( 4 3) ( 4 2 ) ( 5 1 ) ( 5 3 ) ( 5 2 ) ( 3 2 ) ( 6 2 )
Перестановка ( 3 8 5 2 4 6 7 1 ) имеет 15 инверсий.
Кстати, число пар в перестановке равно числу сочетаний из n чисел по 2, т.е.
Определение. Перестановка называется чётной, если она имеет чётное число инверсий. Иначе называется нечётной.
Таким образом, выше в примерах первая перестановка чётная (число инверсий 8), а вторая нечётная (число инверсий 15).
Из этих определений вытекает две важные теоремы о перестановках.
Теорема 2. При выполнении одной транспозиции чётная перестановка переходит в нечётную, а нечётная перестановка переходит в четную, т.е. другими словами перестановка переходит в перестановку противоположного наименования.
Следствие. При чётном числе транспозиций перестановка переходит в перестановку того же наименования, при нечётном числе транспозиций перестановка переходит в противоположное наименование.
Действительно, если мы совершим одну (нечётное число раз) транспозицию, то получим перестановку противоположного наименования. Таким образом совершая нечётное количество раз, мы всегда получаем перестановку с противоположным наименованием. Иначе, при чётном числе транспозиций - наименование перестановки не меняется.
Теорема 3. Число всех чётных перестановок из n чисел равно числу всех нечётных перестановок, и равно следовательно n!/2
Пример применения перестановок к определению детерминантов матриц n-го порядка
Прежде чем перейти к понятию детерминантов (определителей) матриц введем понятие матрицы n-го порядка.
Определение. Матрицей называют объект состоящий из элементов, записанных в определенном порядке в виде таблицы со строками и столбцами. Если число столбцов совпадает с числом строк, то матрицу называют квадратной. Число строк и столбцов квадратной матрицы определяют порядок матрицы. Например, матрица 3-го порядка выглядит следующим образом:
Истоки матриц лежат с решения систем линейных уравнений и понятия определителей (детерминантов) ввели для облегчения решения таких систем уравнений.
Для примера, рассмотрим такую систему линейных уравнений:
Умножим первое уравнение на b2, а второе на -b1 и сложим правые и левые части этих уравнений. Получим
Точно также, умножая первое уравнение на -a2, а второе на a1, затем почленно складывая оба уравнения получим
Отсюда
Назовем разность в знаменателях для x и y определителем матрицы и обозначим следующим образом
Аналогично, разности в числителях для x и y называем определителями и обозначаем следующим образом
Следовательно, решение вышеуказанной системы линейных уравнений можно переписать в более короткой форме, используя понятие определителя
Теперь давайте выявим закономерности при составлении определителя:
- Количество элементов в произведениях равно порядку матрицы. Количество этих произведений, очевидно равно n!
- Эти произведения составляются из элементов взятых по одному из каждой строчки и по одному из каждого столбца.
- Эти произведения снабжаются знаком + или - по определенному правилу (см. ниже)
Итак, теперь мы можем дать четкое определение определителю матрицы n-го порядка
Определение. Определителем матрицы A n-го порядка называется сумма всех n! произведений элементов этой матрицы, взятых по одному из каждой строки и по одному из каждого столбца, при этом каждое произведение снабжено знаком плюс или минус по определенному правилу.
По какому правилу определить знак произведения мы сейчас выясним. Для этого вернемся к нашим перестановкам и заметим что каждое произведение можно представить как некоторая перестановка из чисел. Давайте еще раз выпишем в общем виде произведение, помня что каждый элемент берется по одному из каждой строки и каждого столбца:
В обозначении каждого элемента матрицы первым индексом всегда идет номер строки, второй индекс - номер столбца. В этой общей записи произведения вторые индексы у элементов пробегаются поочередно от 1 до n. Таким образом из вторых индексов можно составить n! перестановок, начиная с так называемой тождественной перестановки ( 1 2 3 4 ... n )
Также мы помним, что перестановки имеют такое понятие как чётные и нечётные перестановки. Отсюда, анализируя определители 3, 4-го и выше порядков, можно сформулировать следующее:
Правило знаков. Произведение P берется со знаком плюс, если перестановка составленная из вторых индексов чётная, и со знаком минус, если перестановка нечётная.
Подстановки
Возьмём две различные перестановки и одну подставим под другой следующим образом (в общем виде)
Например подстановка при n = 5
Здесь цифра 3 переходит в цифру 5. Цифра 5 переходит в 2. 1 переходит в 3 и т.д. Другими словами мы имеем взаимно однозначное отображение одного множества цифр на другое множество цифр. Таким образом дадим строгое определение подстановки на языке математики
Определение. Всякое взаимно однозначное отображение множества А первых n натуральных чисел на себя называется подстановкой n-ой степени. Причем первую перестановку в подстановке мы всегда можем переставить в тождественную, путем транспозиций. Разумеется вторая подстановка должна взаимно однозначно отображаться на первую. Следовательно все подстановки можно записать как
Отсюда видно, что число подстановок равно числу перестановок второго ряда, т.е. как мы знаем оно равно n!.
Примером подстановки n-ой степени служит тождественная подстановка
Определим умножение подстановок, которое представляет само собой очень большой интерес. Например, мы имеем две подстановки
Если мы последовательно проведем два взаимно однозначных отображений, сначала в первой подстановке, затем последовательно во второй, то получим третью подстановку. Например в подстановке A выше 1 соответствует 2, но во второй подстановке B этой 2-ке соответствует 3. Таким образом в результирующую подстановку пойдет 3. Затем 2 => 1 из подстановки А, а 1 => 1 в подстановке B. Поэтому в AB во второй столбец пойдет 1. И так далее. В результате получим
Заметим, что если мы в произведении поменяем местами подстановки на BA, то получим совсем другой результат, а именно
Отсюда делаем вывод, что произведение подстановок в общем случае некоммутативны. В математике такие множества подстановок называют неабелевые. Напротив, если умножение элементов какого-то множества равны, т.е. AB = BA, то элементы коммутативны и такие множества называют абелевые.
Зато умножение подстановок ассоциативно. Это означает, что если мы хотим умножить три подстановки A, B и C, то справедливо равенство
A(BC) = (AB)C = ABC
Т.е. неважно, что Вы сначала перемножаете BC, а потом А на результат, или сначала AB, а потом результат на C. Поэтому в математике опускают скобки, если элементы ассоциативны. Это правило распространяется на любое число сомножителей в общем случае.
Произведение любой подстановки на тождественную, причем слева или справа, даёт саму же эту подстановку
AE = EA = A
Ещё введем понятие обратной подстановки, умножение которой на исходную подстановку, причём неважно, справа или слева, дает в результате тождественную подстановку
Таким образом, для подстановки
Обратной подстановкой будет
Эти понятия весьма важны для усвоения дальнейшего материала, когда будет вводиться понятие группы.
Чётные и нечётные подстановки
Точно также, как мы вводили понятие чётности перестановки, введем понятие чётности подстановок.
Определение. Подстановка А будет чётной, если общее число инверсий в двух строках любой её записи чётно, а нечётной - в противоположном случае.
Так как выше мы договорились все подстановки приводить к подстановкам, в которых перестановка в первом ряду является тождественной, то чтобы определить четность подстановки, необходимо и достаточно определить четность перестановки во втором ряду. Это будет справедливо, так как тождественная перестановка всегда чётная, а как мы знаем сумма двух четных чисел дает чётное число, а сумма чётного и нечётного числа даёт в итоге нечётное. На этом свойстве нам необходимо и достаточно узнать чётность второй перестановки в подстановки.
Покажем еще одно правило нахождения четности подстановки, которое следует из свойств транспозиции. Как мы помним, транспозиция обозначается (i j). К любой подстановки можно прийти из тождественной применяя последовательно операции транспозиции во второй перестановки. Например
Но как мы помним, по теореме 2, каждая транспозиция меняет чётность перестановки, а стало быть и чётность подстановки. Таким образом приходим к выводу, что
При всех разложениях подстановки в произведение транспозиций чётность числа этих транспозиций будет одна и та же, причём она совпадает с чётностью самой подстановки.
Таким образом, чтобы узнать чётность подстановки, необходимо и достаточно подстановку представить как произведение транспозиций от тождественной подстановки. Узнать количество сомножителей этого произведения и мы узнаем чётность подстановки.
Группы подстановок
Определение. Группа - это конечное (или бесконечное) множество G, которое обладает следующими аксиоматическими свойствами:
- В этом множестве определена алгебраическая операция умножения (в мультипликативной терминологии), это означает что умножение одного элемента этого множества а на другой элемент этого же множества b, дает в результате элемент с из этого же множества G, т.е. с = ab.
- Произведения всех элементов группы ассоциативны. Т.е. a(bc) = (ab)c = abc.
- Условие существования нейтрального элемента, обозначаемого как 1. Т.е. a*1 = 1*a = a.
- Условие существования обратного элемента к каждому элементу множества. Это можно записать как ab = ba = 1, где b - обратный элемент.
В аддитивной терминологии алгебраической операцией является сложение (сумма), нейтральным элементом является 0 и аналогом обратного элемента является так называемый противоположный элемент -a. Причём если группа рассматривается в аддитивной терминологии, то она всегда абелевая.
На самом деле достаточно двух первых условий при определении группы. Третье и четвертое условие вытекает как следствие из двух первых. Но для полного понимая понятия группы мы написали 4 свойства.
Примеры групп.
- Группа целых чисел (групповая операция - обычное сложение чисел).
- Группа отличных от нуля рациональных чисел (групповая операция - умножение рациональных чисел).
- Группа поворотов правильного треугольника (групповая операция - композиция поворотов)
- Клейновская группа порядка 4. Таблица умножения этой группы следующая
Мы можем составить из всех подстановок некоторую группу. Действительно, давайте рассмотрим все подстановки 3-ей степени
Теперь составим все произведения этих подстановок и вынесем в таблицу умножения, которая выглядит следующим образом:
Вы сами можете убедится перемножив одну подстановку с другой. Пусть, например
Тогда
Сверяем с таблицей и убеждаемся что действительно
Теперь замечаем, что
- Все произведения подстановок дает в результате подстановку из того же множества (условие группы 1)
- Последовательное произведение нескольких подстановок ассоциативно (условие группы 2)
- Во множестве присутствует нейтральный элемент, а именно тождественная подстановка P0 (условие группы 3)
- Для каждой подстановки во множестве найдется обратная ей подстановка (условие группы 4), например
Следовательно, мы можем сделать заключение что подстановки составляют некоторую группу, которая называется группа подстановок. Группа чётных подстановок из n элементов называется знакопеременной или альтернирующей группой.
Изоморфизм групп. Теорема Кэли.
Определение. Пусть дано взаимно однозначное соответствие из двух групп G и G'
Если между двумя группами G и G' выполнено условие сохранения умножения, то говорят об изоморфизме (изоморфное соответствие).
Т.е. каково бы в группе G не было соотношение вида
В группе G' найдутся элементы которые соответствуют соотношению
Причем элементы группы G взаимно однозначно отображаются на группу G'. Таким образом вытекает следующая
Теорема 4. При изоморфном отображении группы G на группу G' нейтральному элементу одной группы соответствует нейтральный элемент другой группы, и всякой паре взаимно обратных элементов одной группы соответствует пара взаимно обратных элементов другой группы.
Наконец, в конце статьи приведу весьма важную теорему во всей теории групп.
Теорема Кэли. Всякая конечная группа изоморфна некоторой группе подстановок (или подгруппе так называемой симметрической группы Sn).
Согласно этой теореме мы можем любую группу симметрии представить в виде группы подстановок, чем мы и займемся в следующей статье, которую я планирую вскоре написать.
Список использованной литературы
- П.С. Александров "Введение в теорию групп", Москва "Наука", 1980 г., 143 стр.
- П. Ланкастер "Теория матриц", Москва "Наука", 1982 г., 271 стр.
- З.И. Боревич "Определители и матрицы", Москва "Наука", 1970 г., 200 стр.
- М.Хамермеш "Теория групп и ее применение к физическим проблемам", 587 стр., М.; Мир, 1966
- А.Г. Курош "Курс высшей алгебры", Москва "Лань", 2008 г., 433 стр.