С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 19
Текст из файла (страница 19)
Ципловоu индепс деuстви.я группы Q на Rт естъР (Q : RT, Yl, · · · , Yr)==а==P(Q :Т,Xl, ... ' XN)аСле ствие.Если•Xk=Yt+ ... +y;, k=l ,Nвсевесавыбраныодинаповыми== ... == Yr == l ), то X l == . . .XN == rW(F) - число плассов эпвивалентности(YlC(Q : Rт)==C(Q :Т)аиP(Q: T,r, ... ,r)аа-лемма Б ёрнсаuда .Что можно определить (подсчитать) с помощью:леммы Бёрнсайда-общеечислонеэквив алентныхразметок (раскрасок);теорема Редфилда- Пойа -числоразметокданноготипа, т .
е . содержащих данное количество элементов конкретного цвета.4.3.(IIIпоток) Теория перечисления Пойа209Дъёрдъ Пoila(P6lya Gyorgy, 1887- 1985)-........венгерско- швеицарско-американскииматематик.После окончания Будапештскогоуниверситета работал вВысшей технической школе в Цюрихе,а с 1940 г.- в Стэнфордском университете (США).Усложним задачу об ожерельях:Зада ч а 4.1 (об ожерельях N == 5, r == 3, продолжение,более сложный вариант) .
Цвета - красный, си'Ниu, зелё'Нъtu. 0;;fсерелъ.я оди'Наrх;овъt, если од'Но получается издругого поворотом и переворотом.Сrх;олъrх;о имеется ожерелиu,имеющих ров'Нокрасные буси'Ны?Ре ш ен и е.Было:Q== D 5 ,Р (х1 , .. . , х5)всего ожерелий Р (З,цикловой индекс== 1 [ х 51 + 4х5 + Бх1х 22 J ,10... , 3) == 39(только поворот51).w (красный)w( синий)== Yl,== У2,w(зелёный)==Уз,Yl==у,У2== Уз ==1,2210IIIпоток: ГлаваХ1==у+Х2==4.Теория перечисления Пойахk2,2у + 2,1--t ykР (у) ====1 [ иа10k==1' 5;5Р (у)==• • •х5 = у5+ 2'Luiyi;i=l+ 2.1u2=? 1+ и1 у + и2у 2 + ...
+ u5y 5 J110 [(у+ 2)5 + 4(у5 + 2) + 5(у + 2) (у2 + 2)2 J12=[ . . . + (1о . 8 + 5 . 2 . 4) у10U2За да ча+ ... ] .== 8 + 10 == 12.4.6 (о раскраске куба) . Вершины х;уба помечаютх;раснъt.ми и синим чвета.ми. Сх;олъх;о существует1)2)разнопомеченных х;убовк:убов,у(#Col(3));к:оторых половинавершины праснъtе(#Col(4, 4));3) к:убов, у потор'ых не более 2 к:расных вершин?Р еше ни е .Цикловой индекс действия О на вершины кубаР(О : V; xl, · · · хв)а1)1==24-[x~+6x~+9xi+8xfx~ J.#Col(2) == Р(х1, ...
, хв)х1 =... = xs=2==4.3. (III поток) Теория перечисления Пойа24+ 6. 2 + 9. 2 + 8. 4 . 4---3 -.2_3_ _ _ _ 8221132 + 3 + 18 + 163- 23.2) w(красный) ==у, w( синий) == 1,х k == yk + 1' k == 1' 8:#Col(4, 4) ==1244[ (у+ 1) + 9 · (у + 1) + 6. (у + 1) +8224+ 8 . (у+ 1)2(у3 + 1)2 ] ==1 [ ...
+ с:у4 + ... + 9(... 4у2 + бу4 + ... )+24243... + 6 . 2у ... + 8 ( ... + 2у + у + . . .) ( ... + 2у + ... ) J .1168U4 ==== 7.[ 70 + 9 · 6 + 6 · 2 + 8 · 2 · 2] ==2424=3) #Col( ~ 2, *) == ио + и1 + и2, очевидно ио == и1 == 1.U2 == 1 [... + 28у 2 + 9 (... + 4у 2 ... ) + 8 ( ... +у 2 + ... ) J ==2428 + 36 + 8 == 3.24#Col(~ 2,*) == 1 + 1 + 3 == 5.Зада ча4.7 (о числе молекул) .
Рассмотрим моле%ул'ы4-валентного углерода С : где на на местехмогутнаходится СН 3 {метил)) С2Н 5 {этил)) Н (водород)илиCl(хлор) . Например - дихлорбутан. Найти1)общее число М всех моле%ул;2)число моле%ул с Н == О ,дорода.1, 2, 3, 4атомами во212IIIпоток: ГлаваТеория перечисления Пойа4.С Нзхх--- с ---СCl - - -х--СНзClхР е ш е ни е .К акая групп а дей ствует и на каком множестве?Т на множестве вершин тетраэдраЦикловой индекс1gЕТ1еt t'2'f-Type(g)Веса:Ylх41(0,2,0,0)х2321[xi+8х 1 хз + 3х~]12(4радикала, х 1 ~ ...
~ х 4 ~... , х4) ~44+8 .4 .4+3 .3 ·4~ Н , У2 ~ Уз ~ У4 ~Подстановка в Р:#1Х1Х3Всего М молекул2.w(g)14. 2 ~ 8О!М ~ Р (х1,1(4,0,0,0)( 1, 0,1,0)Р (Т: V ) ~1.-Xk~Hk1.+ 3, k ~ 1, 4.244) -~ 36.4.3. (IIIР(Н)l=12поток) Теория перечисления Пойа213==4[(Н + 3) + 8(Н +3З)(Н+ 3) +23(Н2+3) ]== 1 [( н4 + 4 . н 3 . 3 + 6 . н 2 . 9 + 4 . н . 27 + 81) +122434+8 (Н + 3Н + 3Н + 9) + 3 (Н + 6Н + 9) J4== 1 . Н + 3. н3==2+б .
Н + 11 . н + 15.Итого имеется молекул с числом атома водорода:с4- мя- 1 шт. , с 3- мя - 3 шт. , с1- м - 11 шт. , без атомов водорода 1 + 3 + 6 + 11 + 15 == 36.2- мя15-6шт., сшт. , всего-Задача4.8 (об ожерельях со сто и мосты{)) . Стоимостиna.мerнeu дл.я о:нс ер елиu ра вrнъt: прасrного - 1 е д. , сиrнего- 2е д. , зелёrно г оp eлиu из3015- 3е д. Сполъпо существуетo:Jfce-тапих na.мrнeu, стои.мостъ поторъtх равнаед.?Решен и е.Цикловой индекс самодействия группы диэдра (было ранее) :nДля••не четно,n == 15: D (15) == { 1, 3, 5, 15}<р( 1 )== 1,<р(3)== 2,<р(5)== 4,<р( 1 5)== 8.214IIIпоток: Глава4.Теория перечисления ПойаС учётом стоимости камней необходимая подстанов- у 1 ==у,2синий - У2 == у 'зелёный - Уз == уз,ка в цикловой индекс: красныйоткуда х k1зоизо==yk7L+ y2k + узk.c~515-i ,i2+ 2Li=Oc~,s-i,i1+ 4Li=Oc~,з-i,i+i=Oз+ s + 15 Lc~,7-i,i59 788.i=OЗадачи с решениями4.4Зада ча4.9 .
Найдите пор.ядок; стабилизаторов про изволъnой{а) вершиnы,{б) ребра,при действии группъ~ ок;таэдра Оna{в) граnи к;убасоответствующие эле.меnтъ~ .Как;ие перестаnовк;и в nих содержатс.я?Решени е .(а)Пусть О действует на вершины куба иторая вершина.v-неко4.4.(IIIпоток) Теория перечисления ПойаТогда Stab (v)ний на{ е,==s, s2215~ О - группа враще}120° (в выбранном направлении) вокругдиагонали куба, проходящей через данну1о вершину,(б)Stab (v)rv1 3.Пусть О действует на рёбра куба и r -некоторое ребро.ТогдаStab (r) ==ний н а180°{ е,~ Оf}группа враще-вокруг оси, проходящей через середины рёбер (данного и ему противоположного) куба,Stab (r)(в)rv1 2.f -Пусть О действует на грани куба инекотор ая грань .Тогда Stab==(f)па вращений на{ е, t, t 2 , t 3~}О -груп90° (в выбранном направлении) вокруг вокруг оси, п роходящей через середины граней (данной и ей противоположной) куба,Stab (!)Зада ча14.rv4.10 .
Haumuциrх;ловоu индеrх;с для следующимобразом определёнпого самодеuстви.я rчетверноu группы КлеuнаV4== { е, а, Ь, аЬ1.еае :еЬ:а1а 2 == Ь2 == ( аЬ )2 == е 2 == е, аЬ == Ьа } :ЬаЬЬаЬеаЬаЬЬаЬеаеаЬаЬаеаЬЬа :''аЬ:еаЬаЬаЬЬае'•'216поток: ГлаваIII2.ее :Ь :аеаеаеР е ш ен и е.ьаЬьаЬьТеория перечисления Пойаа:'аЬаЬа4.ьаЬ :'В езде группа КлейнаеаьаЬаеьаЬеааV4еьаЬ'аЬь•действует на своиже элеме нты.Type(g)w(g) #е4, О , О , О )1а, Ь, аЬ ( О , 2, О , О ) х§3g1)(g2)xiType(g)w(g) #1(1,0, 0, 0)2( 2, 1, О, О) xlx2 2(О, 1, О, О) Х21xiеа, ЬаЬPv1 4 ==1[ х 41 + 2х 21 х 2 + х 2 ] .4Первая группа перестановак есть нормальная подгруппа84,Задачаа вторая4.11.-нет.Найти ципловоu индепс транзитивногоса.мо деuстви.я группы 1в.Р ешен и е.Обозначим последовательно вершины правильного шестиугольника буквами А,t -поворот на60°....
, F , 1 6==(t) ,(III поток) Теория перечисления Пойа4.4.gЕz6е= (А) ... (F)g = (ABCDEF)2g = (ACE)(BDF)g3 = (AD)(BE)(CF)4g = (AEC)(BFD)5g = (AF EDCB)Type(g)( 6, о , о,w(g)(о,Задача4.12.ср( 1 )Х6х23х32х233, о, о , о , о)(о, о ,о , о , о)2,(о, о , о , о , о ,=1)о, о, о )2,1[ 632]Pz 6 =х 1 +х 2 + 2х 3 + 2х6 =6D(6) = { 1, 2, 3, 6 },х61о , о , о)(о, о , о, о , о ,(о, о ,217ср( 2)1)Х61 ~6/d~ cp(d) xd ;6= 1,dJ6ср(3)=ср(6)=2На стеrх;.л.ян/Н/ЬlХ п.ласти'Нах рисуют оди'Наrх;овые пр.я.моуго.лъ'Ниrх;и ('Не rх;вадраты) и расrх;рашиваютих стороны вr'ЦВетов .Сrх;о.лъrх;о .мож'Но 'Нарисоватъ таrх;их раз.лич'Ных пр.я.моуго.лъ'Ниrх;ов? Ко'Нrх;ретно) при r = 2 ?Решение.Н айдём цикловой индексR: SдействияагруппыRсамосовмещенийпря моугольника встранстве на его стороны.
ГруппаR=( t,f)про-пораждается образующими :t - в р ащение вокруг центра симf -отражение вокруг оси, проходя-метрии на180°,218IIIпоток: Глава4.Теория перечисления Пойащей через середины противоположных сторо н,gЕRT ype(g)w(g)е( 4, О , О , О )х41#1t( о , 2, о , о )х§1(2, 1, О , О)22fP (R : S; х1 , х2, хз, х4)Q=XlX21[ xi42оси .+ х~ + 2х~х2 J.Числ о 2- цветных прямоугольн иков-#Col(2) = P (R: S; 2, ... , 2)аЗадача16+ 4 + 16494.13 . На стеrк;.л.ян'l-t/ЫХ пластинах рисуют одинаrк;овые пр.я.моуго.лъниrк;и (не rк;вадраты) и расrк;рашиваютих вершины в3цвета .Сrк;о.лъrк;о .моа+сно нарисоватъ таrк;их различных пр.я.моуго.лъниrк;ов?(III поток) Теория перечисления Пойа4.4.Ре ш е ни е.219Н айдём цикловой индекс P (R: V ) действияагруппысамосовмещенийRпря моугольника впро-странстве на его вершины.gЕType(g)Rw(g) #е( 4, о , о , о )xi1t( О,О, О )х221f( о,о, о )х§22,2,1 42-4 [х 1 + 3х 2 JЧисло пря моугольников :81 + 27# C ol (3) == P (R : V ; 3 , ..
. , 3)4аЗадача4. 14.лена на927Квадратная стеrк;л.янна.я пластина раздеравных rк;вадратов, rк;оторые расrк;рашиваютс.я в один из2цветов.Сrк;олъrк;о существует123разнооrк;рашеннъtх пластин?45б789Реш е ние .Н а множество Т изN== 9 квадратов стеклянной пластики действует группаt4t==-f2==D4==( t,s == е, где2вращени е на90°вокруг центр а квадрата;f, s ) ,220fIII-поток : Глава4.Теория перечисления Пойасимметрия относительное прямой , проходящейчерез середины противоположных сторон;s-симметрия относительное прямой, проходящейчерез противоположные вершин .Определяем цикловой индекс действияЕ D4D4на Т .Type(g)w(g) #xgе(1) ..
. (9)( 9, О, . . . )1123( 1, о , о , 2, ... ) XlX4 2t t(5) (1397) (2684)'4t2( 1, 4, о , ... ) Х1Х2 1(5) (19) (37) (28) (79)( 3, 3, о , ... ) xfx~ 4s' f' ... (2) (5) (8) (13) (48) (79)8gперестановкаЗада ч а4.1 5 (о компостере) . Компостером пазовё.мrх;вадратпую таблицу 4 х 4, в rx;oтopou rх;ажда.я гх;летrх;а.мо :нсет бытъ либо пустой) либо содер;нсатъ в цептресимвол•.Сгх;олъгх;о существует разлиtttпых1234rх;о.мпостеров,5678910 11 12если не разлиtttатъ те)rх;оторые .могут бъtтъ noлyttteны одиниз другого са.мосов.мещепи.я.ми13 14 15 16в прострапстве?Р ешен и е.Н айдём цикловой индекс действия группыдиэдра D4 наD4164клеток компостера.= ( t, j, s), t = j = s = е,22D4= 8,4.4.(IIIеt . t3t'2fпоток) Теория перечисления Пойап ереста н о в каType(g)(1) ...
(16)(1.4.16.13) ... (6, 7 ~1 1 , 10 )(1.16) .. . (6,11 )(1. 4) .. . (10, 11)(1) .. ' (16)(2. 5) . . . (12. 15)( 16, 0 .... )( 0.0.0, 4 .... )( 0,8.0 ... )( 0. 8, 0 ... . )( 4.6.0 .... )Цикловой индекс действия группыD42211w(g)1.х41х4'4•2'~'2.х~2XfX~#12122на элементыкомпостера:Наличие/отсутствие в клетке символа• описывается их отображением в двухэлементное множество (раскраске в два цвета), поэтому число С различных компост е ров естьС====Р(2 ,2, ...
)2168192 + 4 + 3 . 32 + 256+ 25 + 3 . 28 + 211==238196 + 96 + 256==8548.К аналогичной задаче сводится задача о числе фотош аблонов рисунков соединений для интегральных схем.Задача4.16.Haumи число различных вариантов распраспи граней rк;уба в2и3Решение . Цикловой индекс:Р(О:F) ==а#Col(2)rцвета.1222III#Col(3)поток: ГлаваТеория перечисления Пойа+ 12. 3з + ·35 + 8 . 3236=4.=3·83 . (81 + 36 + 27 + 8)3 . (80 + 64 + 8)88Зада ча=57.Опр еделитъ 'Число разли'Ч'Н/ЬlХ4.17.всех гранеu правилъноu 4 - уголъноupacnpaconпира.миды Л в 3цвета.Р е ш ен ие .Занумеруем последовательно боковые граниП числами1, ...
4,g(trv14 =g), t -а основаниевращение наЕ 14е=(1)(2)(3)(4)(5)t, t 3 = (1234) (5)2t = ( 12) (34) (5)Зада ча4. 18.-Hauтu 'Число5.90°.Type(g)( 5, О, О, О,( 1, О , О, 1,( 1, 2, О, О,О)О)2О)XIX2pacnpacon всехноu правилъноu 4 - уголъноu пира.миды вРеш ен ие .w(g) #xs11XIX4 21гранеu усе'Чён3цвета.Пронумеруем грани П: боковые - с 1 по 4по часовой стрелке , основанияствующая на Пчасовой стрелке.-14 =-( t ), t -5и6.Группа , дейповорот на90°по(III поток) Теория перечисления Пойа4.4.Еg14еtt't23перестановкаType(g)(1) . .
. (6)( 6, о ,(1234)(5)(6)(2, О , О, 1, О , О)( 2, 2, о , ... )(12) (34) (5) (6)Цикловой индекс Р1==4[ х~223w(g)#х61212... )XlX4xix§1+ 2х~х4 + х~х~ J.3#Col(3)Задача3 (27 + 2 + 3)== 216.4==4.19.Найти число различных вариантов расrк;расrк;и граней тетраэдра вРешен и е.2и3P(T : F,xl , ... ,x4)==1 [ х 4 +8хlхз+3х 2 J .1212а==#Col(2)#Col(3)Зада ч а4.20 .==3424+ 11 . 23t-==. 22+ 11 . 323·44+ 11327 + 334== 5 .60415.Найти число различных вариантов расrк;расrк;и рёбер тетраэдра вРешен и е.2цвета.Группа Твращение на2 и 3 цвета .== (t, J) , t == f ==120°32е, Т== 12, гдевокруг оси, проходящей черезвершину и центр симметрии,4оси;224IIIf -поток: Глававращение на180°4.Теория перечисления Пойавокруг оси , проходящей черезсередины противоположных рёбер,Обозначим черезЕ3оси .множество рёбер тетраэдра-Е! =тая,6 - и обозначим их цифрами от 1 до 6, счичто рёбра 1, 2 и 3 иницидентны одной вершине , аось вращения , задаваемого элементомрез середины рёбери1f , проходитче6.Н айдём цикловой индекс.gETType(g)е = (1) ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
