Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки (1127096), страница 8
Текст из файла (страница 8)
В отличие от перестановок общего вида, произведение взаимно простых перестановок не зависит от порядка множителей. Действительно, пусть ф и ф — взаимно простые пере- становки и а — произвольный элемент множества М. Если а — подвижная точка для перестановки ф, то положим (а)ф=Ь; элементы а, Ь вЂ” неподвижные точки для ф, ибо (а)фФа и (Ь)фФЬ. Поэтому имеем (а) (ф ф) = ((а)ф)ф = (Ь)!р = Ь, (а) (ф ф) = ((а)ф)ф = (а)ф = Ь, т. е.
в этом случае (а)(ф ф) =(а)(ф ф) 42 Если а — неподвижная точка перестановки ~р, то положим (а)ф=с (если а является неподвижной точкой и для перестановки ф то а=с) и аналогично получим, что элементы а, с не меняются под действием перестановки <р, а поэтому (а) (~р ф) = Иа)~р) ф = (а) ~р = с, (а) (ф ° ср) = ((а)ф) гр = (с)ср = с. Так что и в этом случае перестановки р ° ф и ф ° <р действуют на элемент а~М одинаково, а это и означает, что Таблицу произведения двух взаимно простых перестановок ср, ф составить очень просто. Для этого во втором ряду таблицы «р ф нужно записать на своих местах (т.
е. на тех местах, на которых они стоят в таблицах для <р, ф) все подвижные точки перестановок <р, ф а остальные места заполнить неподвижными точками. Например, Пусть теперь ~р — произвольная перестановка на множестве М. Разобьем М на части Мь М„..., М„каждая из которых является орбитой некоторого элемента из М. Это разбиение имеет такие свойства: а) каждый элемент из М принадлежит одному из подмножеств М; (1 = 1, 2, ..., з); б) если 1~/, то М; и Мг ие имеют обШих элементов; в) для каждого а ен М, (1 есть один из номеров 1, 2, ..., з) элемент (а) ~р также принадлежит Мь По последнему свойству можно рассмотреть ограничение ~р; перестановки ~р на каждое из подмножеств М;; ср; есть, очевидно, циклическая перестановка на Мь Она определяется перестановкой ~р однозначно.
В свою очередь, каждую из перестановок чЧ можно расшири~ь иа все множество М. Обозначим это расширение через чч (1 =1, 2, ... „ь), Далее такие перестановки также будем называть циклическими и обозначать их так, как и обычные циклы. Следовательно, перестановка будет циклической в этом понимании тогда и только тогда, когда она имеет граф такого вида, как на рис. !7. 43 Очевидно, множество подвижных точек каждой из перестановок ф совпадает с множеством М;; по свойству в) пеРестановки гРг и Ч, гав!, взаимно пРосты. ПользУЯсь приведенным выше правилом для умножения взаимно простых перестановок, получаем гР=гРг'Чгг" ° "гР . Поскольку перестановки Чг„ ~„ ..., гр, — попарно взаимно простые, это произведение не зависит от порядка множителей.
Таким образом, доказана такая Т еор ем а. Каждую перестановку на конечном множестве М можно разложить в произведениевзаимно простых циклов, причем это разложение однозначно с 'г3 ~~~~ ~ I гх 7' точностью до поРЯдка множителей. Набор чисел )г„й„... ..., )г„являющихся длинами циклов,на которые Рис. 17 разложена данная пере- становка, называется ее типом и обозначается ((г„ )г„ ...г й,).
4 Пример 8. Разложить в произведение циклов перестановку 71 2 3 4 5 6 7 81 (2 3 1 6 7 4 5 8/' Находим разные орбиты для Чг. Имеем (1)Чг =- 2, (2)гр = 3, (3)гр = 1; (4)гр = 6, (6)гр = 4; (5)Ч=7, (7)т=5, (8)Ч=8 Так что орбиты определяют подмножества (1, 2, 3), (4, 6), (5, 7), (8). Ограничениями перестановки гр на эти множества будут такие перестановки: ' Чгг=(2 3 1) грг=(6 4) Ч>г=(7 5) Чгг=(~).
Р а с ш и реп и я ми этих перестановок на множество М будут перестановки 1 2 3 4 5 6 7 8 (2 3 1 4 5 6 7 8)' 1 2 3 4 5 6 7 8 Чгг = (4, 6) = (! 2 3 6 5 4 7 8), 1 2 3 4 5 6 7 8 Чг — — (5, 7)=~! 2 3 4 7 б 5 8)' /1 2 3 4 5 6 7 81 '11 2 3 4 5 6 7 8) Поэтому можно записать ф=фд фз фэ фа=(1, 2, 3) (4, 6) ° (5, 7) (8) = = (1, 2, 3) (4, 6) (5, 7). Последняя запись однозначно определяет перестановку лишь тогда, когда известно, на каком множестве она действует.
)ь Упражнения 1. Может ли произвольный раф быть графом иакого-нибудь преобразования? 2. Перестановка задана графом, Как построить граф обратной перестановки? 3, Указать правило лля нахождения графа произведения преобразований, каждое из которых задано своим графом, не строя таблиц этих преобразований. 4. Построить графы преобразований, заданных таблицами: /1 2 3 4 5 6 7 8! /1 2 3 4 5 6 7 8) 15 6 ! 8 3 7 2 4/' ) 16 8 5 4 3 7 ! 3/' /1 2 3 4 5 6 7! /! 2 3 4 5 6 7 8 91 ) 16 4 3 7 5 ! 2/' )16 4 1 8 4 3 4 9 9/' 5. Каждая перестановка, граф которой связан, цнклична, Дока- вать это.
6. Длиной орбиты называется число ее элементов. Найти наибольшее и наименьшее значения сумм длин разных орбит для пре. образований множества из л элементов. 7. Преобразование ф множества М будет перестановкой тогда и только тогда, когда сумма длин разных ее орбит равняется (М ), Доказать это. 8. Пусть ф — произвольное преобразование множества М.
Существует такое множество Р ~ М и такое натуральное число й, что (а)фыр Р для каждого и ш Р и ограничение фа на Р есть перестановка. Доказать эта. 9. Разложить в произведение взаимно простых циклов и найти типы таких перестановок: (4 3 2 5 !)' ™ 15 6 ! 4 3 2) ' /! 2 3 4 5 6 7 8 9! 17 9 3 ! 5 8 4 2 6/' 10. Описать общий вид графа про анального преобразования (так, как это сделано для пбрестановок). 11. Сколько существует перестановок на множестве из гл эле- ментов, которые имеют заданный тип (л,, л„ ..., ла), где лт < лз( ( ....С ла (ясно, что л,+из+...+ла=т). 12.
В группе За=8 ((1, 2, 3, 41) найти число перестановок каж- дого возможного типа, 13. Определить тип перестановки, .характеризующей расположе- ние тридцати физкультурников после двукратной перегруппировки (см, упражнение 12 4 3), 45 5 6. ПОРЯЛОК ПЕРЕСТАНОВКИ Для каждого преобразования ~р можно рассмотреть его степени; и-й степенью преобразования ~р называется произведение Ф'%'Ч" ° "% где п — натуральное число.
Далее будем обозначать его ~". Из определения степени преобразования вытекают такие равенства: а) ~~л <~т ~рл.ни. б) (1ра)л2 <рыл Положим также для каждого преобразования я ~рь Для перестановбк (произвольных биекций) понятие степени можно обобщить и на случай целых отрицательных чисел, положив е-'=в-' ч в =ь-т-ь') ' Равенства а) н б) в этом случае будут верны для проиаоольных целых показателей.
Если ~р — некоторая перестановка на множестве М, ~М ~ (оо, то ~' для каждого целого п также есть перестановка на М. Таких перестановок лишь конечное число, т. е. в последовательности гр, <р', ~р', ф', ... не все перестановки разные, Пусть для некоторых натуральных чисел й, 1 (й(() выполняется равенство <рь=~р'. Тогда (р")-'= р-', (р')-'р" = (р")-'р', откуда ср'-'=в, т. е.
для каждой перестановки ~р 3(М), где М вЂ” конечное множество, найдется по меньшей мере одно натуральное число в, такое, что ср'=е. Наименьшее нз таких натуральных чисел называется порядком перестановки <р. ' Степени циклической перестановки (а„а„...,а„) находят по формуле (а„ам ..., а„)" =(аю аьсн ..., а„, аь ..., аь 1). Это равенство можно толковать так. Если какая-нибудь шестерня, которая имеет и зубцов, поворачивается вокруг своего центра, то, занумеровав зубцы числами 4б 1, 2, 3, ..., л и зафиксировав некоторое начальное положение зубцов, ее повороты можно однозначно описывать перестановками на множестве (1, 2, ..., а).
Циклическая перестановка 1л З 4 очевидно, описывает поворот на угол 2н/л (зубец с номе ром 1 встает на место зубца с номером 2 и т. д.). Не нарушая общности, будем считать, что шестерня поворачивается по часовой стрелке. Чтобы повернуть шестерню на угол 2йп/л, надо й раз осуществить поворот на угол 2п/и в одном направлении, так что перестановка ал, й)0, отвечает такому положению шестерни, когда на месте первого зубца стоит й-й, на месте второго (й+ 1)-й и т. д. Если шестерню повернуть л раз вокруг центра на угол 2н/л,' то она займет начальное положение. Таким образом, для каждого цикла (аь а„..., ал) выполняется равенство (ан ам ..., ал)л = е.
При этом для натуральных чисел, меньших л, это равенство невозможно. Для А(0 перестановки а" описывают повороты шестерни на углы 2пй/л против часовой стрелки. По доказанному в предыдущем параграфе произвольную перестановку можно разложить в произведение попарно взаимно простых циклов: % = и ' чч " ° " 'р .
Для любых номеров 1, 1 произведение перестановок ~рь ~р7 не зависит от порядка множителей. Пользуясь этим, 1-ю степень перестановки <р для каждого целого и можно записать так: ч" =(ч 'ч "° 'ь) " ° " (йч'т "° 'ь) = (<р1'И" ° "%) '(%'%з" ° "%з)' °" М '<рл" ° "<рл) = л л л <рл .
<рл, .,рл (1) Это равенство также допускает механическое толкование. Поскольку циклы ~рь ч~„..., ~р, взаимно просты, их степени описывают повороты вокруг центров з шестеренок с соответствующими количествами зубцов, причем этн шестерни не связаны одна с другой. Поэтому степенями перестановки ~р описываются повороты целой системы 47 шестеренок. Зубцы каждой из шестеренок можно занумеровать так, чтобы все повороты осуществлялись в одном направлении.
Порядок является очень важной-характеристикой перестановки. Чисел и, таких, что ф» =а, для произвольной перестановки ф существует 'много, но все они делятся на порядок перестановки. Докажем это методом, от противного. Допустим, что существует такое натуральное число й, для которого справедливо равенство фа в' причем й не делится на порядок г перестановки ф. По определению порядка перестановки я)г, поэтому й=) +в, 0<в< . Тогда имеем фь=фо»'=ф" ° ф'. Но гры (фх) г аг а Таким образом, е=ф"=ф'.
Однако 0<в<с, и мы пришли к противоречию, которое и доказывает сформулированное утверждение. Выведем теперь правило для нахождения порядка произвольной перестановки. Прежде всего, заметим, что произведение нескольких взаимно простых перестановок может равняться тождественной перестановке лишь тогда, когда каждая из перестановок единична. Это вытекает из того, что произведение ф взаимно простых перестановок фь ф„..., ф, действует на каждую свою подвижную точку так, как действует на нее та перестановка фп для которой эта точка является подвижной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
