С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 18
Текст из файла (страница 18)
4 + (2 - 1) . 3 + 1 == 12.Действие Т на грани (или вершины) тетраэдра: тип ы перестановакT ype(t) == T ype(t ) == (1, О , 1, О);6 : Type(f) == (0, 2, О , О) .D :2Тетраэдр двойственен самому себе ~ действие на грани==действие на вершины .4.2.(IIIпоток) Теория перечисления Пойа195О - группа вращения октаэдра(~ куба)QоО2== (t, f, r), t == f == r ==4- вращение наt90°3е, где :вокруг оси, проходящей через середины двух противоположных гранейо(D- D) , такихосейf -вращение на3;180° вокругоси , проходящей черезсередины двух противоположных рёбер (о-о) , такихосей6;r -вращение на120°вокруг оси, проходящей черездве противоположные вершиныо( 6-6) таких осей 4.== 3 .
3 + 1 . 6 + 2 . 4 + 1 == 24.Пример 4.3 (Действие О на вершины куба: типы перестановок).D : Туре( t) == Туре( t ) == (0, О, О, 2, О, . . .) ;2Type(t ) == ( 0,4,0, ... );3о: Туре(!)==6: T ype(r)Посколькувгр уппеЕ0·V ,(0,4,0, . . . );== T ype(rн ой вершины и)== ( 2, О , 2, О , .
. . ).G == Gx · [G : Gx],вращениягде2Е0правильного-V -то число элементовмногогранникаестьчисло рёбер , выходящих из одчисло вершин многогранника.196поток : ГлаваIIIЦикловой индекс.соб вычисления числа4.Теория перечисления ПойаСуществует универсальный споC(Q) -количества классов эквивалентности (== орбит).Сопоставим каждой перестановкеggЕвесw(g)по п р авилу:Type(g)=(v1, ... , vN)=?w(g)м ономОпределение4.3.Средний вес подстановак в группе называется rциnловъt.м икдеnсо.м действияg : Т:аP(Q :Т,Xl, ... ' XN)аgEG1 ~v1VN== G L...t xl ..... х N.gEG(Это производящий полином многих переменных)Б удемтакжеPg(xl, ...
,При мерXN) и4.4.использоватьобозначенияPg, P(Q).Вычислим цикловой индекс действия группы всех преобразований правильного треугольника всебя(т.е. оставляr-ощих его неподвижным) , на его стороны .Решен и е.grv53-N == 3.n == 3! == 6.Т - стороны треугольника,все перестановки сторон,4.2.(IIIпоток) Теория перечисления Пойавg :Т -197самодействие группы SзаТреугольн икссамодвойственная фигур аа::::}действие на сто ро ны==Аrv{==действие на вершинысьУ : Т::::}rvе, (аЬс) , (асЬ) , ( (а) (Ьс) ) , ( (Ь) (ас) ) , ( (с) (аЬ) ) }v""1t'-,v;\..,t2v"1v\..,f,.1v"_",1t2ftf( t , f)gЕSзе== (а)(Ь)(с)2t t'2f, tf, t fType(g)( 3,о , о)(О, О ,1)( 1, 1,О)w(g) #МОИОМОВxf12xl3xlxl1 23В сего6- цикловой индекс самодействия группыS3,или, чтото же, группы симметрии треугольника .Зачем нужен цикловой индекс?Пусть заданы множество Т , группаgи действиеg: Т.а1.Припишем каждому элементу Т одно из r значений (неформально : покрасим в один из r цветов).Всего , очевидно , имеетсяrNраскрасок.198III2.поток: Глава4.Теория перечисления ПойаН е будем различать раскраски , если при преобразовании g :раскрашен также как иt ----+ t' t'Н апри мер, поворот наt.не даёт нового рас90° -крашивания вершин квадрата :ф--- ®---ф--- ®®--- ®Вопрос: Сколько существует неэквивалентных раскрасок:=классов эквивалентности?Ответ: Это значение вычисляется через цикловой индекс.
И меем-1. Каждый класс эквивалентности - это g-цикл; ихC(g) == vl + ... + v 1v штук .2.КаждаяперестановкаЕg\ v1, . . . , vн) будет иметь.()F lX g ==lllх1C(g)· . . . ·стипомrC(g)Fix (g)неподвижных точек : каждыйности это g-цикл, ихQклассэквивале нт-иZINХNх1= ... = х н=rОтсюда , по лемме Бёрсайда, число полученных классовэквивалентностиC(Q: Т)а==неэквивалентных раскрасок:P(Q : Т, х1, ...
, x Jv)а•х1 =... =х лг=r(III поток) Теория перечисления Пойа4.2.Например,Pg(1 , . . . , 1)199== 1: если все элементы покрасить в один цвет, то таких раскрасок одна.Задачи на применение циклового индексаЗадача 4.1 (про слова; решение, используr-ощее цикловой индекс). Определитъ числослов длиuыl ): 2S uеэпвивалеuтн/ЫХв q-бупве'Н?-lО.м алфавите, если эпвивале'Нтrны.ми счита1отс.я слова, получающиес.я другиз друга п ереста'Новпой прайuих бупв.qlВыло решение:S==+ ql-l2•Z-2__л.__Новое решение: Q == { е, g} ~т: оЬ ...
о о.lL2;v',.1lgEQеgType(g)w(g)xixl- 2xl(Z,O, ... , O)(Z - 2, 1, 0, .. . , О)1S == P (q, ... , q) ==МОИОМОВ112Цикловой индекс: Р (х 1 , . .. , xz) ==ql#122[xi + xi- хИ .+ ql-l2•Классическая комбинаторная задача об ожерельях•Ожерел 'ье-окружность, на которой на равныхрасстояниях по дуге (в вершинах правильногомногоугольника) располага1-отся <<бусины>> .•Задача об ожерельях: скол ько различных ожерелий можно составить изNбусин r цветов?200IIIпоток : ГлаваТеория перечисления Пойа4.• Какие ожерелья считать неразличимыми?Варианты: если одно получается из другого самосовмещением-1) только поворотом в плоскости (бусины плоские, окрашены с одн ой стороны == к;аруселъ)-самодействие группы1.N;2) поворотом и переворотом в пространстве (бусины круглые) - самодействие группы диэдра (двойной пира.миды) DN.За да ча 4.2 (об ожерельяхN == 5, r == 3;1-й вариант) .Ск;олък;о разных ожерелий .можно составитъ изсин35буцветов?1.
Ожерельяодинаковы, если одно получается из другого поворотом.Ре ш ен и е.QЭлементrv1. 5 ==5(t), t ==е, n== 5.МОНОМОЕеО)х511t t2 t3 t4( о, о, о, о,1)xs4'''w(g)#T ype(g)( 5, О, О, О,ZsЦикловой индекс: Р(х1, .. . , xs) ==5#Col(3)== Р (3,. . . , 3)==315[ xf+ 4xs ].+4 .353 . 8553 ·17 ==51.4.2.(IIIпоток) Теория перечисления Пойа201Зада ча 4.3 (Олимпиады << Покори Воробьёвы горы2009>>) . Дл.я 50 детеu детспого сада зшк;упле'Н/Ы 50оди'На'к;овых тарелоп. По 'к;раю 'к;а;;JСдоu тарел'к;и рав'Но.мер'Но располо;;JСе'Но5белых 'к;РУ:JfСОЧ'к;Ов . Во спитате ли хотят пере'к;раситъ 'к;а'к;ие-либо из этих 'к;ружоч'к;овв другоu rцвет та'к;, чтобы все тарел'к;и стали различ'Ны.ми.Ка'к;ое 'Наи.ме'Нъшее число допол'Нителъ'НЪlХ rцветовпотребуется им дл.я этого?Как должны были решать школьники.Пусть требуется rцветов . Отбросим rвариантовраскраски в один цвет.
Чи сло остальных вариантов5без учёта возможности поворота тарелки : r - r;r5••с учетометсяИтого :поворота :==r55 раз).#Col(r)-r5-(каждый вариант по вторя-r- - - +r5полнительных цветах #Соl(З)Задача2.-r551.+ 4r5и при2до-4.2 (об ожерельях N == 5, r == 3; 2-й вариант).Ожерелья одинаковы, если одно получается из другого поворотом и/или переворотом.202IIIпоток: ГлаваРешение.
Q -4.Теория перечисления Пойагруппа диэдра D 5== (t, J) ,t5== f ==2е,n == Ds == 10.ЭлементType(g)Ds( 5, о , о , о,е234t t t t' ' '4j, t j, .. . ' t f(О, О , О , О,( 1, 2, о , о ,w(g) #о)xf1) xs2о)XlX2МОНОМОЕ145В сего10Цикловой индекс: Р1[ xf10==#Col(3) == P(x1, ... ,xs)+ 4xs + 5xlx~ J.х 1 = ... = Xs =3==35 + 4 . 3 + 5 . 331039.Задача 4.4 (о раскраске сторон квадрата). Сторо'н/ы существует различrно ок;рашеrнных пвадратов) если ихстороrнъt распрашивают вРешение.стве -rчветов?Группа самосовмещения квадрата в прострнгруппа диэдраD4== ( t, j, s), D 4 == 8,котор ая порождается тремя образуiQЩими :t : вращение на 90° вокруг центра в выбранном н аправлении;f : симметрияотносительно оси , проходящей через середины противоположных сторонs :- 2оси;симметрия относительно оси , проходящей через середины противоположных вершин- 2оси.4.2.(IIIпоток) Теория перечисления ПойаПри самодействии группы203D 4 (N == 4) её элементыбудут иметь следующие веса :е:единичная перестановка оставит все стороны на месте, т.
е . имеi-отся 4 цикла длины 1, весxi(1перестановка);:стороны циклически переходят друг в друга пои против часовой стрелке, длина цикла4,(2 перестановки);стороныпереходятвпротивоположные,1вес х 4••что даетдва цикла длины 2, вес - х§ (1 перестановка);f : две противоположные стороны на месте,две меняiотся местами, т. е .остальныеимеются два единичных цикла и один длины 2, вес -xix§ (1перестановка, 2 оси);s :в двух парах смежных сторон элементыменяютсяместами , что даёт два цикла длины 2, вес ( 1 перестановка, 2 оси) .Цикловой индекс самодействияPn4 (х1, ... , х4)==1[ х 41 +82х4Число раскрасок квадрата вPn 4 (r, .. . , r)== 1 [ r 48rD4:+ 3х 22 + 2х 21 х2 J .цветов:+ 2r + 3r 2 + 2r 3 J .В частности, в два и три цвета :#Col(2)#Col(3)242 + 4 .
2 + 24==2+2+221.6,х§204IIIпоток: ГлаваЗадача4.5(раскраска граней куба в два цвета) . Грапипуба распрашивают в4.и2Теория перечисления Пойа'Цвета .3Сполъпо существует paзлutttno опраш еппых пубов?Реш е ние .Напоминание : Q ==О==(t, f , r),О== 24.QО == (t, f , r) , t == f == r == е, где:t -в р ащение на 90° вокруг оси, про24о3ходящей через середины двух про-/).тивоположных гранейоf -( D- D) , такихосейвр ащение на3;180° вокругоси , проходящей черезсередины двух противоположных рёбер (о-о) , такихосей6;r -вращение на120°вокруг оси, проходящей черездве противоположные вершиныОбозначимFчерезF(.L- .6)множествотаких осейграней4.куба;== N == 6.
Выберем некоторую грань куба (квадрат) и обозначим её Ф, а параллельную ей-®.Перенумеруем последовательно вершины грани Ф числами1, ... , 4,а вершины грани® -числами•5, ... , 8uтак , что в е ршина с номером ~ смежна с в е ршинои с но -меромi+ 4,i == 1, 2, 3, 4.П ерестановки далее указаны для случая , когда осьвращения(t)проходит через середины граней Ф и®,(f) проходит через середины рёбер ( 3-7 ) и ( 1-5 ) ,(s) проходит через вершины (1) и (7),а грани обозначены :(1-2-6-5) через® , параллельная ейгрань - ®, грань (2-3-7-6) - через @ , параллельная ейгрань-®.4.2.(IIIпоток) Теория перечислении Пойа205\5нижняяф43rf5gEOперестав:овкаType(g)е(Ф) ...( 6, о,t t3't2fr r'2Всего(®)...
)(Ф)(®)(®®®®)( 2, о, о , 1, о ,(Ф)(®)(®®)(®®)( 2, 2, о ,(Ф®)(®®)(®®)(о,(Ф®®)(®®®)(о, о,3,w(g)#хб12Х1Х46х2х21 2х~36х2381)... )о , .. . )2, о, ... )24206IIIпоток : Глава4.Теория перечисления Пойа#Col(2)#Col(3)~1 6[32434+ 12 . 3 + 3 . 3 + 8 · 32] =10,48 .Цикловой индекс действия группы октаэдра на множестверёбер кубаR( RgE OT ype(g)е( 12, о ,t t't23r'2rN~ 12):.. . )( о , 6, о ,( о , о , 4,w(g)#х1213. 2 ~ 61( о, о, о, 3, о, о )( 2 , 5, о ,f~... )..
. )о , ... )х~х~х2х51 2х43В сего364.2~824Цикловой индекс действия группы октаэдра на множествевершин кубаV( V~Ng EOT ype(g)е( 8, о ,t t3( о , о , о , 2, о , о )f... )( о , 4, о , ... )( 2, о , 2, о , ... )'t22r r'В сего... )( о , 4, о,~ 8) :w(g)хв1х~х~х~XIX~#13. 2 ~ 6364 .2 ~ 8244.3. (IIIпоток) Теория перечисления ПойаЦикловыеиндексысамодействиядействия О на элементы кубарёбра,207Sn, ln, Dn(F -грани,иR-вершины).V -..х.'lпX ]lx]21 2 ·· · n(j 1 , ...
,jп) Е Nglj1 +2j2+ ... +njп = nР ( ln )Р(Dп)Р (О :====1 ~n/d~ VJ(d) xd ,n12VJ -функция Эйлера,dlnР(lп)+V)аР(О: Е)аР(О:F)а4.3Применение теоремы Пойа для решения комбинаторных задачК множеству Т ,действиюg :ТаТ== N,Q, G == n иR == {с 1 , ... , Cr},группедобавим множествометок (<<красок>>), и совокупность функцийF == Rт -приписывания меток (расrк;рашиваний) элементам Т .208IIIпоток: Глава4.Теория перечисления ПойаQ, действуя на Т, действует и на Rт - операцияо: Rт хGПридадим вес элементамо Rт.R: w( ci)==Yi, i == 1, r .Тео ема4.2 (Редфилда-Пойа; 1927, 1937).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
