В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 31
Текст из файла (страница 31)
лучаем сюръектпвпость те, а из (3.22) — ивъективиостьг ы, кггы юХ, те(хг) те(хг)ы хг тх- (те(хг)) =т, (те(ха)) хз) в кроме топг, в салу (3.20) Уй, йыС имеем УхщХ (тгы) (к) т,(ть (к) ) 2(йх) = (йй) х тел(х], а следовательно, Тгй, йгыС т„ т. е. мы пакюалн, что т — гомаморфизм. Таким образом, в тех случаях, когда зто удобно, булем ои. ределять действие группы иа множестве заданием игиоморфиз ма т, а в других случаях в непосредственным заданием отображепия (2, х)-ьдх, удовлетворяющего условиям (3.19), (3.20).
гю Заметим далее, что из (3.19), (3.20) сзедует Удщ6, Ухв, «вщХ х, У«в~«в У-в.т, (3.24) (так как, используя ха=ухи получаем й 'х,=у-'(ухв) = (у-'у)хв ехв «,). 3.2.3. Орбиты. Лемма Бернсайда а числе орбит Две точки кь хмюХ называются эквивалентными относительно ерунпвг 6, действующей на множестве Х (или 6-экеиоаленгнмми).
если Бу юС(х,=у«в. Иэ (3.19), (3.20), (3.24) непосредственно получаем, что 6-эививалентность явлются отношением эквивалентности из Х ((3.19) показывает рефлексизность этога отношения, (3.24)— снмметричносп, а иэ (3.20) следует транзнтивиость: х,=у,хь хв=увхв .«в=уз(увхв) = (увув)кС. и, счедовательно, уназаниое отношение разбивает Х на классы эквивалентяости, которые назыныст С-орбитции Орбиту, содержюцую элемент хвщХ, будем обозначать через 6 (хв], т.
е. 6 (хв) = (ухв(уеиС). Пример 3.20. Орбитой точки (О,!) а примере 3.!9 является Х, окружность с центром в тачке О радиуса 1, проходящая через точку 1 (0, !) (р .. 3. ). Пусть теперь К вЂ” венечное ыножестло элементов, 6 †конечн группа, действующая нз Х. РесХг смотрим еадачу об определении числа й! С-орбит. Обозначим через Р/(у), где ущС, число элементов из Х, остающижя на месте при лействии у, т. е. Ф(у) =((«щХ ( ) ух=х)(. Рве. 3.4 ! 10! Люл днв доквыввввспм евнин вотрветмтс всвоноватваввн» угвермжвнв Утвеужденне 3.12.
ПУюь хвеиХ, 81(хо) (УлвС(У«в=«в). Тогда 31(«в) — подгруппа еруппы 6 (сганионарнал подгруппа точки хв). В силу с«в=«в (см. (329)) имеем ею31(хв). Пусть уь увш щ31(хв). Тогда, испольэУЯ (320), полУчаем (Увбв)хв= =у,(у,хв) =у~«в=«в, т. е. увувщ31(«в). Пусть ущЗг(«в). Тщ да у«, хв, откуда. используя (3.24), получаем хе=у-'хв, а следовательно, у †'вю51(хв]. 1чв '~~'х(х) '~»' 'Я .1...) тмо Кма оюд мх Я ~ а(лх = х) а(хт .т) Х т а Х )ж(к) ) С(г,)мл, о О(„) ыт О(аймл мп(т) Кюп Утаерждение 313.
Лусть хоыХ. Тогда (0(хо)(=)б() ДЯ(х.) (. Рассмотрим левые смежные классы группы б по подгруппе Н=Я(хо). Поставим в соответствие каждой точке хаиб(хо) смсжнмй класс уНонб)Н, где у — элемент на 0 такой. ыо х ухо. Покажем, что каждому элементу хо поставлен в соответствие единственный смежный класс н тем самым задано некоторое отображение р: 0(хо)"ьб/Н. Действительна, пусть для искоюрого элемента у,~б выполняется х=у,хо Тогда угхо =ухи откуда (у-оу,)хо ко, а следовательно, 3 обожав(хо)= =Н. Но тогда уоезуН, а значит, Х,Н=ХН.
Покажем теперь, что укаэанное отображение ор: 0(ко) С(Н является взаимно. однозначным. отаУда н бУдст следовать, что (О (хо) ( =(011Н( =(0()(Н). Пусть у„уоожб, хо=йохо. хо=бато, хгчьхо. Покажем, что у Нчьуой Действительно, если Х,Н=Х,Н, то уо 'Х )(Х,Н=Н, откуда у, 'у оиН. На тогда (уо 'уо)хо=хо. а следовательно, Ухо=йохо.
что пРотивоРечит Услоапю х,чьхо. Таким образом, доказана ипъеитивносгь отображения ор. Для докаэетельсгаа его сюръективносги осталось заметить, что ЫЗНеиб)Н ХН является образом точки ухоеэб(хо). утверждение 3.14, Лугть хоыХ Тогда Ыхеиб(хо) (51(х))= = (Я(х,)(. Пусть хоиб (х,).
Тогда найдется уоеиб. к=йохо. Рассмотрим произвольный элеммгг уж51(х). Тогда ух=к, а следовательно, (ууо)хо=у(йохо) =ух=а=йохо, откуда (уо 'ууо)хо=хо, т. е. уо оууоеи51(хо). Таким образом, уо 51(х)уосд51(хо), откуда 3,51(х,)у»Я(х). (323) Пусть таперь у — произвольный элемент нз Я(хо). Тогда ухо=хо, а эиачит, э силу хо=бе 'х имеем (ууо ')х у(уо-'х)= =ухо=хо=у;ох, откуда (уоууо ')х х, т.
е. уоууо гж51(х]. Таким образом, уо51(хо)уо '~Я(х) н, используя (323), аалучаем уоЯ(хо)бог=Я(х), откуда и следует, что (Я(х)( =(51(")'( Теперь докажем лемму Бернсайда. Обтаиачим через Ха множество 0.орбит. Пусть также Туси оиб, ЫжжХ ( х х) )1, еслнух=х (О, если ухчьх. Тогда, используя утверждения 3.13 и 3.!4, писем вб(г)шХв вшб(е) 6(вв)шХ () 6(((Ш(л П) (51П ) ( - ) 6) (Хв) - (б! И, 6(вв)шХ откуда и следует справедливость доказываемой формулы. 32.4. Примеры применении леммы Берисайда дла решения комбинаторимх задач Пример 3.21.
Составляются слова длины 3 из букв а и Яь Сло. ва считаются эквивалентными, если получаются одно нз другого Переменой местами крайних буне (например, аЬЬ ЬЬа). Ои. ределнм число Ф классов эквивалентности. Пусть Х= (с=с!с с,(с ьи(а, Ь). 1=1, 2, 3) =(а, Ь)'. Расслвотрнм группу 6=(е, о), где е — единичный элемент группы 6, ачье, ав=е. Определим отображение <б, с> Хс прямого произведения 6)(Х в Х.
Пусть УссяХ ее=с, ос=ос,с,св=свс,с, (т. е. е оставляет слово с па месте, а о менвет в слове с крайние буквы местами). Покажем. что введенное отображение удовлелворяет (3.!9), (3 20). Условие (3.!9) выполняется по апре. делению. Поиажем выполнение условия (З.П)). Рассмотрим ие. тривиальный случай с 6=3=а (случаи с Х=е илн Ь=е очевидны). Тогда УсшХ (аа)с=ало=ее=с, а(ос) =ас,с,с,=с,слов=с, откуда и вытекает справедливость (3.20). По условннм задачи искомое число д( совпадает с числом б-орбит, а значит, используя лемму Бернсайда, имеем У= — (Ы(е)+Ы(а) ).
Зал!стим, что 1 2 Ф(е)=(Х(=2'=8; У (а) ( (сшХ(ос!свел =евсеев) ( = ( (свиХ(свсвсв = =с!свел)(=((сшХ(с!=се)(=2 =4, ! а следовательно, Дг= — (8-(-4)=б. 2 Прямер 3.22. Составляются ожерелья нз плоских бусна 1 трех цвепвв, при этом окрашег на только одна сторона бусин Каждое ожерелье аютоит «з з в г э пяти бусин. Определим число лв У различных ожерелий. :Пронумеруем бусины ноже. рев. за релве, начиная с некоторой бу- мв сины и увеличивая номера в процессе обхода ожерелья.в пап валерии, обратном движению часовой стрелни (рис.
3.5,а). аждой бусине можно поставить в соответствие один нв трех возьюжных цветов, например, к (красный), г (голубой), з (зеленый). Тогда любое раскрашиваиие ожерелья с пронумерованными бусннамн можно описать упорядоченным набором пвщпв длины 5, предполагая, что !-й элемент этого набора соогветст.
вуег свету 1-й бусины. Например, упорядоченная пятерка с= =<к, г, 3, к. к) означает, что первая бусина онрашена в красный цвет, вторая — в голубой н т. д. (рис. 3.5,б). Рассмотрим множество Х раскрашиваний ожерелья с пронумерованными бу. синзми. т. с. Х= (с= <сь см см сь сз) (свш(к, г, з)) = (н, г, з)з.
Очевидно, что (Х) ) (к, г, з) ('=3'=243. Рассмотрим танже группу б вращений ожерелья на плоскости (вокруг центра этого ожерелья), совмещающих его с самим собой. Пря этом под компоэицней пС(5 двух произвольных вращений ев йшб будем понимать результат послсловательно применяемых к ожерелью вращений 5, а (т. е. сначала выволняется вращение 5, а затем к полученному результату применяется вращение а). Очевидно, что группа 6 состоит нз пяти элементов — вращений (против часовой стрелки) ва углы 2п(/5, где г'=О, 1, 2, 3, 4. Обозначим элементы группы О величинами соответствуюпгих углов Заметим, что рассматриваемая в этой задаче группа 6 является коммутативной, что лелает излишним указание, в какой последовательности надо осуществлять вращения и композиции оО3.
Однако в другик задачах группа вращений может оказать. ся некоммутатианой, и тогда указание нослш!овательности вращений цри опрелслеини композиции оСЗй является необжщимым (мы, естественно, сохраним выбранное опрелеление композиции и при решении всех последующих задач). Поставим в соответствие каждому вращению ашй подстановку т, иа множестве номеров бусин (1. 2, 3, 4, 5) такую, что для любою (ы(1. 2, 3. 4, 5) г.(г) будет номером 1-й бусины ожерелья, полученного в результате вращения п, относительно исходного положения ожерелья (это можно представать себе так: одно ожерелье закреплена на плоскости и с инм совмещается некоторое подвижное ожерелье, к которому приыеияется вращение п).
Тогда г,=е, тз,л = (1 2 3 4 5), тею = (1 3 5 2 4), тюи = (1 4 2 5 3), гюгз = (! 5 4 3 2). Обозначим Т= (е, тпю тып, твчз, тичэ ). Непосредственной проверкой убеждаемся, что отображение и т. группы О на У является биекдией. Заметим далее,. что (по определению композиции О и отображения п-ьч.) выяолняегся )га,йшбт т т э ге* — ! ээв (3.2б) Иэ откуда снелует, что группа 6 нзоморфнв группе ущБз (для до. казатедьсгва того, что Т вЂ” группа, можно всспольжматьск фор мулоа (320), а таиже тем, что т, е). Но тогда группы О н 1" для нас неразличимы н для щюстоты будем считать, что О У. Определим отображение <И, с> Хс прямого пронзаеяенгм ОхХ в К. Пусть ТгсшХ, Тгбщб бе=И<со щ, сз.
са сз> <с [г), с . (т) са,(з), с,(4), с 50 >, т. е. УсшХ, Ут. шб т.с — раскрашнванне, получающееся в ре. зультате вращения о ожерелья с раскрашиванием с. Например, тьсз <н, к Я, г, е>=<я, и, и, к, г> (Рис. 3 б, а — Рщаувши. евине с=< к, к, н, г, з>, рис. Зб,б — раскрвшнванне тачзс) Покажем, что введенное щображение <И, с> Ис прямого провзведенпя О)(Х в Х удаилттваряш (3.20) (выполнение (3.13) очевилно). Покажем справедливость (320).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
