На прошлой лекции мы с вами подробно поговорили о семействе графов на симметрической группе, которые называются Star графами. Мы рассмотрели их свойства, а также некоторые примеры. Сегодня точно так же подробно мы с вами поговорим о перестановках, а также о свойствах, которые нам нужны будут в течение этого курса. А именно мы будем интересоваться разложением перестановок в произведения независимых циклов, а также их сопряженности. По определению перестановкой Пи на множестве X, состоящим из n элементов, называется "взаимно однозначное отображение множества X на себя". Обычно перестановку представляют в виде таблицы, которая состоит из двух строчек. В первой строчке у нас все элементы от единицы до n по возрастанию, а во второй строке содержатся образы этих элементов. И когда перестановка представлена в таком табличном виде, обычно ее называют подстановкой. Нам же будет удобно записывать перестановку в виде одной строки, эта строка будет содержать образы элементов множества х. Напомню, что группа, симметрическая группа содержит все n факториал перестановок на множестве из n элементов, и бинарной операцией этой группы является произведение перестановок, а единичным элементом является тождественная перестановка: 1, 2 и так далее n. Таким образом, у нас с вами определена симметрическая группа, а теперь давайте мы поговорим о разложении любой перестановки в произведение независимых или непересекающихся циклов. Итак, известен следующий факт. Он состоит в том, что любая перестановка раскладывается в произведение нетривиальных непересекающихся циклов, причем единственным образом с точностью до порядка следования этих циклов. При этом циклом i1, i2 и так далее il называется перестановка, которая переводит элемент i1 в i2, i2 в i3 и так далее. Например, если мы с вами рассмотрим перестановку 1, 3, 2, 4, 5, то она у нас раскладывается в произведение одного нетривиального цикла длины два, а все остальные циклы будут являться тривиальными и они опускаются в разложение. Таким образом, циклическое представление нашей перестановки в данном случае — это просто транспозиция. И тут же уместно сразу сказать, что вообще говоря, помимо разложения перестановки произведений независимых циклов существует также произведение транспозиции, но только это разложение в произведение транспозиции уже не будет являться единственным. Например, если мы с вами возьмем перестановку 2, 3, 4, 5 и 1, или в ее циклическом виде это будет 1, 2, 3, 4, 5, то мы можем с вами придумать несколько различных вариантов разложения в произведение транспозиции. Два из таких вариантов вы сейчас видите у себя на слайде. Так вот, разложение перестановок в произведение непересекающихся циклов определяет цикловой тип перестановок, и об этом мы с вами поговорим на следующей лекции. Сейчас же мы только отметим, что эта важная характеристика задает перестановку с точностью до сопряженности. И вот сейчас об этом понятии, о сопряженности, мы поговорим более подробно. Пусть у нас имеются с вами две перестановки: Пи и Тау. Тогда по определению они являются сопряженными, если существует некоторая другая перестановка Сигма такая, что между этими двумя перестановками возникает соотношение, которое вы сейчас видите на слайде, а именно: перестановка Пи может быть представлена как произведение перестановки Сигма, Тау и обратной к Сигма. И сопряженность является отношением эквивалентности группы. Это означает, что вся группа разбивается на классы эквивалентности, на классы сопряженности так, что всякий элемент принадлежит одному единственному классу сопряженности. При этом два класса сопряженности совпадут тогда и только тогда, когда между элементами существует сопряжение, и они не пересекаются в противном случае. А теперь мы с вами готовы сформулировать очень важный теоретический результат, который нам необходим в дальнейшем. Две перестановки сопряжены в симметрической группе тогда и только тогда, когда их разложение в произведение независимых непересекающихся циклов содержит одинаковое число циклов длины k для любого k. Давайте с вами рассмотрим два примера классов сопряженности симметрической группы для малых размерностей, скажем, для n, равное три и n, равное четыре. Когда мы говорим о симметрической группе степени три, это значит, что у нас имеется три факториал перестановок, то есть всего их шесть, и эти шесть перестановок у нас разобьются на три класса сопряженности. В первый класс попадет единственная перестановка, тождественная, все элементы зафиксированы в ней. А второй класс сопряженности составят перестановки двух элементов, это значит транспозиции, у нас их всего три транспозиции в этом случае. И, наконец, перестановки трех элементов попадут в третий класс сопряженности. Таким образом, три класса сопряженности для симметрической группы степени три. Теперь давайте рассмотрим симметрическую группу степени четыре. Она у нас содержит 24 перестановки, которые раскладываются в пять классов сопряжения. Первый класс сопряженности вновь содержит только тождественную перестановку. Второй класс сопряженности содержит все перестановки двух элементов, это значит все транспозиции, в данном случае у нас их шесть таких транспозиций, это транспозиции вида 12, 13, 14, 23, 24 и 34. Третий класс содержит в себе перестановки трех элементов. Здесь у нас восемь таких перестановок, и вы все их видите на слайде. Четвертый класс будет содержать перестановки четырех элементов, их вновь будет шесть. Пожалуйста, внимательно посмотрите и убедитесь в том, что действительно это перестановки четырех элементов. И пятый класс. Последний класс будет содержать попарные перестановки, их будет три, вы их тоже сейчас видите на слайде. Таким образом, мы с вами рассмотрели примеры классов сопряженности симметрической группы степени три и степени четыре. А в целом же каждый класс сопряженности соответствует в точности одному разложению перестановок на непересекающиеся циклы. И как это разложение у нас связано с разбиениями целого положительного числа n, а также с таблицами Юнга — вот мы об этом с вами поговорим в следующий раз.
