Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки (1127096), страница 9
Текст из файла (страница 9)
Поэтому из равенства (1) получаем, что ф»=е тогда и только тогда, когда одновременно ф» г ф» а ф» — в (2) Если перестановки фь фе, ..., ф, есть циклы длины йь )гм ..., й, соответственно, т. е. имеют порядки й„й„... ..., й„.то наименьшее число п, для которого одновременно выполняются все равенства (2), равняется, очевидно, наименьшему общему кратному чисел йы йы * й,.
Следовательно, мы доказали, что порядок перестановки ф, которая раскладывается в произведение циклов длиною Яь Йм ..., й, есть наименьшее общее кратное чисел йь ма, ° ° °, й ° пор. гр = К (пор, фт, пор. !рю ..., пор, ф,), 4 Пример. Пусть 1 2 3 4 5 6 7 8 (3 6 4 1 8 7 2 5)' Разложим ф в произведение циклов: гр = (1, 3, 4) (2, 6, 7) (6, 8).
Отсюда пор. ф=К(3, 3, 2) =6. Ь. Упражненпя 1.. Найти порядок каждой иэ перестановок: (! 2 3 4 5 6 7 8 9) (3 5 7 9 6 8 1 2 4) ' (! 2 3 4 5 6 7 8 9 101 (3 5 4 6 7 8 9 2 1 10!' 2. Найти порядки всех перестановок на множестве из 6 элементов. 3. Какой наивысший порядок могут иметь перестановки на мно. жестве из 10 элементов? 4.
Найти перестановку, обратную к циклу (а,, аз, ..., а„). 5. Если произведение перестановок ф и ф не зависит от порядка записи множителей, то порядок файф есть делитель наименьшего общего кратного порядков ф и ф В общем случае нельзя утверждать, что пор. (файф) =К (пор, ф, пор.
ф). Привести примеры. 6. Сколько существует перестановок 15-го порядка на множестве из 8 элементов? 7. Вывести формулу для нахождения порядка перестановки, пользуясь механическим толкованием действия возведения в степень. 8. Если и — простое число, то для каждого й, 0<а<я, перестановка (п„а,, ..., а„)а есть цикл длины л. Если число л — составное, то эта перестановка будет циклом для чисел й, взаимно простых с и, и произведением циклов одинаковой длины в ином случае.
Доказать это. 9. Доказать, что для каждой перестановки ф, которая раскладывается в произведение ! циклов одянаковбй длины э, найдется цикл ф длины Ь и натуральное число й, такое, что ф =ф". Единственный ли такой йикл? 10: 12 мальчиков перебрасываются разноцветными мячами, каждый из них бросает свой мяч всегда одному и тому же партнеру, все мячи бросаются одновременно, и никакие два мальчика не бросают мяч одному игроку. Через какое наименьшее число ходов игры все мячи окажутся в руках тех же мальчиков, что и в начале? 11.
Колода нз 36 нарт тасуется следующим образом. Колода берется лицевой стороной вниз в левую руку и карты сверху по одной перекладываются в правую руку, причем в праной руке они поочередно кладутся то сверху, то снизу тех карт, которые к этому л~оменту уже скопились в правой руке. Сколько раз нужно повтоРить такую перетасовку, чтобы в колоде был восстановлен первона.
чрльный порядок? 49 12. Какое наименьшее число перегруппировок тридпати физкультурников (см, упр. 12 б 3) нужна осуществить, чтобы в шеренге был восстановлен начальный порядокг Какой ответ получится в случае, когда фнакультурников 36? В 7. ОБРАЗУЮЩИЕ СИММЕТРИЧЕСКОЙ ГРУППЫ 3 ад а ч а. На стенах круглого зала картинной галереи висели картины.
Как-то решили разместить их в другом порядке, меняя местами картины, которые висят рядом. Всегда ли можно с помощью таких перемещений разместить картины, как задуманог Р е ш е н и е. Занумеруем картины в первоначальном порядке числами 1, 2, ..., и. Пусть на место первой картины нужно повесить картину с номером г„ на место второй — кар- 2 тину с номером г, и т. д., наконец, 12 на место а-й картины — картину с номером 1„(1„(а, ..., 1„— разные числа из множества (1, 2,... ..., и)). Перемещаясь вдоль стены обозначенным способом в одном направлении картины последовал тельно занимает все места, на которых висят картина. Поэтому Ф картину с номером 1, можно поРис. 18 весить на место первой картины (рис.
18). Выбирая направление перемещения картины с номером г, так, чтобы не двигать каРтинУ с номеРом ты каРтинУ с номеРом 1, можно повесить на место второй. Аналогично, выбирая такое направление перемещения, чтобы не двигать картины с номерами 1, и г„картину с номером 1', можно повесить на место третьей. Продолжая этот процесс дальше, каждую картину можно повесить на нужное место. Следовательно, ответ на вопрос, поставленный в задаче, утвердительный. Сформулируем теперь эту задачу на языке перестановок. Занумеруем места, на которых висят картины, так, чтобы нумерация мест совпадала с нумерацией картин в первоначальном положении. Размещение картин, при котором картина с номером г, висит на первом месте, картина с номером 1', — на втором и т. д., картина с номером ㄠ— на л-м месте, однозначно описывается перестановкой а= — .) 1 2 3 ...
и) У га 'а °" 1л/ 50 в частности, первоначальное размещение картин характеризуется тождественной перестановкой. Если в положении, которое описывается перестановкой (1), поменять местами картины, которые стоят на й-м и (й+1)-м местах (1(й(п), то перестановка а» которая будет характеризовать это новое положение, будет результатом умно. жения перестановки и слева на транспозицию (й, Й+1): !! 2 ... а — 1 а+! а 2+2 ... а! 'А й "- Га-т 1ь 1а~т Ь+э " глl 1 2 ... а — 1 а Ф+! 2+2 ... а! =( ! 2 ... а — ! а+! а 5+2 ...
и/ (:::,,::. ) 1 2 ... а — 1 а а+! 1+2 ... и) й 1з " га-~ 1ь 1а и !а+и " гл l Если переход от первоначального положения к желаемому, которому отвечает перестановка <р, осуществляется за а шагов, то можно записать 6, ° 6, ... 6, ° е=<р, где 6» 6„..., 6, — некоторые транспозиции. Следовательно, вопрос задачи можно сформулировать так: можно ли разложить произвольную перестановку в произведение транспозиций? Аналогичные вопросы интересно решать .не только для транспозиций, но и для произвольных множеств перестановок. Оп р ед еле ни е. Подмножество Т множества всех перестановок называется системой образующих симметрической группы Я, если каждую перестановку из о можно разложить в произведение перестановок из Т.
В 2 б было установлено, что системой образующих является совокупность всевозможных циклов. Каждый цикл (а» а„..., а,) можно разложить в произведение транспозиций: (аз, ам ..., а,) =(а» аг) (а» аз) " .. (а» а,) (проверьте!). Пользуясь этим, каждую перестановку, разложив ее сначала в произведение циклов, можно представить в виде прои1ведения транспозиций. 4 Пр имер 1. Разложить в произведение транспозиций перестановку 7! 2 3 4 5 6 7 8! 18 7 2 1 6 5 3 41' 5! Раскладываем ~р в произведение циклов: »р = (1, 8, 4) (2, 7, 3) (5, 8). Далее, имеем (1, 8, 4) = (1, 8) (1, 4), (2, 7, 3) ='(2, 7) .
(2, 3). Следовательно, »р = (1, 8) (1, 4) .(2, 7) *(2, 3) .(5, 8), ° Из этого примера видно, что в разложении перестановки в произведение транспозиций порядок множителей является существенным. Далее, будем обозначать символом Я„симметрическую группу перестановок на множестве М=(1, 2, ..., п). В этой группе будем выделять системы образующих, которые будут состоять только из транспозиций определенного вида.
Например, последовательности транс- позиций 1 (1, 2), (2, 3), (3, 4), ..., (п — 1, и), 11 (1, 2), (1, 3), (1, 4), ..., (1, и), как легко убедиться, будут системами образующих для Я„. Действительно, перестановку ((, !) можно разложить в 'произведение транспознций системы 11 так: ((, !) = (1, () ° (1, 1) ° (1, 1). (2) (Убедитесь, что перестановки, которые стоят справа и слева в этом равенстве, одинаково действуют на каждый элемент из М.) Поскольку любую перестановку ~р можно разложить в произведение транспозиций вида ((, !), то, заменив в этом разложении все транспозиции в соответ- ствии с равенством (2), получим разложение <р в произ- ведение транспозицнй системы 11.
В свою очередь, произвольную транспоаицию из по- следовательности 11 можно разложить в произведение перестановок системы 1 по равенству (1, А)=(1, 2) (2, 3) ... ° (й — 1, й) (й — 1, й — 2) ... (2, 1). (3) Проверим, правильно ли равенство (3). Пусть 6; = (», (+1). Перестановка (~р=6, ° 6, °... 6», ° 6»» ... 6» действует на элементы 1 и й так: 1 — 2 — 3 —...-=-А=-й=-д...— й, », »» »» » , »» , »» а, Ю 1 й — й — й —... =-Й=-»й — 1=-...— 1.
»~ О»»» б»» 6» а»» а» 1 Остальные элементы множества будут неподвижными точками для Ч~. Следовательно, ряд 1 также есть система образующих для Я . Наиболее интересными системами образующих являются такие, из которых нельзя выбросить ни одной перестановки, чтобы новая система снова была системой образующих. Эти системы называются неприводимыми. Они могут состоять из разного количества перестановок.
В частности, существуют системы образующих, которые состоят из двух перестановок (они всегда неприводимы). Например, такой будет система 111 я = (1, 2), ~ = (1, 2, 3, ..., и). Действительно, если 1 ( /( п — 2, то (1)(У = ) + 1, (2)~1=/+2, а поэтому ~~ а ° ф/)-'=(1+1, 1+2). Таким образом, каждая перестановка системы 1 раскладывается в произведение перестановок и, р, потому что элемент ~/ имеет конечный порядок, например 1, так что (~1)-'= ((3/)' '. В общем случае описать все неприводимые системы образующих симметрической группы Я„не удается. Но неприводимые системы образующих Я„, целиком состоящие из транспозиций, описываются достаточно просто. В й 5 было введено понятие графа как совокупности точек на плоскости, некоторые из которых соединены стрелками. Такие графы называют ориентированными, поскольку на стрелку, соединяющую две точки, можно смотреть как на путь с фиксированной ориентацией, которая указывается направлением стрелки. Вдоль такого отрезка разрешается проходить только в одном .направлении — в том, которое указано стрелкой.
Здесь нам понадобится понятие неориентированного графа, которое введем следующим образом. Неориентированным графом называется множество как угодно размещенных на плоскости точек, некоторые из которых соединены линиями любой формы. Два неориентированных графа считаются неразличимыми, если оии отличаются друг от друга только формой соединительных линий или способом размещения точек на плоскости. Выбранные на плоскости точки называются вершинами графа, а соединяющие их линии — его ребрами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
