С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 20
Текст из файла (страница 20)
(6)(6, о,... )(о, о ,2, о,t, tf2==(123) (456)(1)(23)(45)(6)( 2, 2, о,... )... )w(g)#х61х231xix~8312=Задача4.21.Haum,и число различ ных вариантовrx;pacrx;и рёбер rх;уба в12pac-цвета.2Р е ш ен и е. Цикловой индекс:Р( О а: R)=#Col(2) =1[xi+6xl + Зх~ + бхiх~ + Sxj] .242 12 + 6 . 23 + 3 . 26 + 7 . 2723 . 23=218.'4.4.(IIIЗада ч апоток) Теория перечисления Пойа4.22.Найти tttиcлo разлиtttных вариантов распраспи вершин пуба вР е ш е ни е .2и3rцвета .Цикловой индекс:1 [ х 81 + 6х 42 + 9х 42 + 8х 21 Хз2] .24Р( О~ V) =+6.2 +9.2 +2282#Col(2)4.23.43 . 2з38 + 6 . 32 + 9 . 343.8#Col(3)Зада ч а225Сполъпи.ми723,+ 8 . 34= 333.гео.метриtttеспи разлиttt'ны.миспособами три абсолютно одинаповъtе .мухи .могутусестъс.яввершинах правилъногосе.миугол ъниnа 7нарисованного на листе бумаги?Ре ш ен и е.
Множество Т - верш ины семиугольника, на7которые действует группа 1 7 = ( t), t = е .gЕ 17еt, tw(g) #T ype(g)xi( 7, О , . . . )2, ... ,t6(Х70, ... , 0, 1 )Цикловой индекс самодействия1[7Pz 7 (xl, ... , Х7) =х17J+ 6х71 7:1~7/d=~ cp(d)xd .7Число различных раскрасок впри условии окраски ровнох 1 н у+ 1, Х7 н у+1вdl72 цвета (муха есть/нет) ,3 вершин из 7 есть коэффициент из при уз после подстановки716Pz7 :226IIIпоток: Глава4.Теория перечисления Пойа1[ (у+ 1 ) 7 + 6(у+1) JР(у)7изЗадача4.24.7!7 . 3! . 4!=1[ ... +С7з у з +75.6= 5.2.3J....Воповые гра1tи правилъ1tой 6- уго.шьной пи ра.мидъt опрашиваются в npac1tыu)синий и зелё1tыйцвета.
Определитъ(а)число различ'liъtх(б)число пирамид с oд1tou(в)число пира.мид) у поторых не .ме1tее трёх npac1tыx2-и 3- цвет?-lъtх пира.мид)·npac1touгра?iъ'tо;CJгра1tеи.Решен и е.И меем транзитивное самодействие1 6.(а) Общее число пирамид.Р (16) =dl61 [ х 6 + х з + 2 хз2 + 2 х6 J .126(6, в) Число пирамид с 1 и 3 ~ красными гранями.Полагаем у 1 = у, У2 = Уз = 1 (следим только за красными гранями) , х1 =у+ 2, х2 = у 2 + 2, хз =уз+ 2.4.4.(IIIпоток) Теория перечисления Пойа21 [Uo + U 1У + U2Y + ...
+ u y== б66]227==12263356 [ (2 + 2 + 2 + 4) +6·2 у+ (16. 15 + 2. 3. 2 ) у + ... J.u0== 84/6 == 14, u 1 == 25== 32,u2== (240+24)/6 == 44.Число пирамид с:(б) одной красной гранью -u 1 == 32,(в) не менее, чем 3 красными гранями-(uo + и 1 + и 2 )Задача4.25.#Col(3)-== 130- (14 + 32 + 44) == 130 - 90 == 40.И.ме1отся плоспие бусин/ы, оrк;рашен/н/ые содной стороны в прасный, синий и зелёный цвета .
Изних составляют о:нсерелъя, содер:н~ащие по8в равноотстоящих точrк;ах оrк;ру;и~ности. Определитъа)б)число различнъtх 3-rцв етных ожерелий;..~число ожерелии,у rк;оторых не .менее трех rк;рас -ных бусин?Р ешен ие . Здесь вездетранзитивное самодействиециклической группы1...8.D(8)<р( 1 ) == <р(2) == 1, <р(4) == 2, <р(8) == 4 ,== { 1, 2, 4 ,8 },1~Р (1...8) ==~ <p(d)88/dxd==dl81 [ х 8 + х 4 + 2х 2 + 4х8 J .2148а) Общее число ожерелий :#Col(3)==38 + 3 4 + 2 . 9 + 4 . 38== 834.228поток: ГлаваIII4.Теория перечисления Пойаб) Подсчитаем число Х ожерелий, в которых числокрасных бусин не более3 (т.
е . О , 1 и 2) и вычтем полученное количество из 834.Полагаем Yl == у, У2 == Уз == 1 (следим только за бусинами красного цвета).Найдёмкоэффициентывпроизводящемхk== yk+ 2'ио, и1, и2многочленеWприприУо, Yl, У2подстановкеk == 1' . . . ' 8.Р (Zв) == 1 [ х 81 + х42 + 2х 42 + 4х 8 ]8w1== 8 [(у+2)8+(у2+2)4+2(у4+2)2+4(у8+2)]== Uo28+ U1Y + U2Y + ... + иву ==14272863[ (2 +2 + 2 · 2 +8)+8 · 2 у + (С~ · 2 +4·2 )у + ...235u 0 == 2 + 2 + 1 + 1 == 36,и 1 == 128,J.U2 == 28 · 8 + 4 == 224 + 4 == 228.Отсюда392 == 442.Зада ча#Col(34.26.~) == 834-(36+128+228) == 834-Гршни гк;уба расгк;рашивают в два цвета -гк;рас'Нъtu и си'Ниu . Сгк;олъгк;о существует гк;убов1)различ'Но огк;раше'Н'НЫХ?2) угк;оторых(#Col(~Ре ш ен и е.'Не.ме'Нее4гра'Неuгк;рас'Ные4))?Цикловой индекс :P (O ~ F) ==..1 [ х 61 + 6х 21 х4+ 3х 21 х 22 + 6х 32 + 8 х 2]33 234.4.(IIIпоток) Теория перечисления Пойа1) #Col(2) = 26 + 12.
2з+ 3 . 24 + 25303. 232) Полагаем w(1)1,~у,229~ 10.3~w(2)1,~Xkyk+k~ 1 , 6 .w1~ 24 [ (у+ 1 )6+ 6(у + 1 )2(у4+ 1 )+3(у+ 1 )2(у2+ 1 )2++ 6(у2 + 1)3 + 8(у3 + 1)2 J.#Col(? 4)~ и4+иs+ив - число кубов с 4, 5 и 6 красными гранями соответственно . О чевидноР аскрывая~ u6 ~u51.W , находим:2+3(у + 2у + 1 )(у + 2у + 1)+6442263+ 6(у + 3у + 3у + 1) + 8(у + 2у + 1) J.16 ~ 2.815 + 6 + 9 + 185+ 2+ 3+ 63·88Итого #Col(? 4) ~ 1 + 1 + 2 ~ 4.Задача4.27.Для распраспи стороп пвадрата па степл.яппоu пластиппе исполъзу1от3'ЦВета-npacnыu,сипиu и зелёпыu .
Сполъпо .мо::нспо получитъ1)разпораспрашепных пвадратов?2)пвадратов с1праспы.м ребром иneболеепих?Реш ен и е.Цикловой индекс :P(D4)~1[ х 41 +82х4 + 3х 22 + 2х 21 х2 J2си230III1) #С ol (3)поток: Глава==14.Теория перечисления Пойа22[3 + 2 · 3 + 3 · 3 + 2 · 3 · 3 ]4881 + 6 + 27 +548==1688==2) При раскраске в 3 цвета:X k ==Следим только за красным(Yl)87 + 818====21.Yt+y~+y~, k == 1, 4.и синим (у2) цветами:у}+ у~+ 1, k == 1, 4. Находим и1о + и11 + и12 ·14W ==[(YI+(y2+ 1)) +2(yf+yi+ 1)+822+ 3(у~ +(у~+ 1)) + 2(yl + (У2 + 1)) (Yi +У~+ 1)] ВXk ==нас интересуют только члены сYI(красное ребро -одно)нас интересуют только члены с у~ , у§ и у~ при у 1(синих рёбер вО, 1, 2)1-8 [4 .
7 + 4 . 3]==4 · 108==5.4.4.(IIIЗада чапоток) Теория перечисления Пойа4.28.231При с оедип.я.я 'к; свободпымсв.яз.ям углерода бепзолъпого 'х;ОЛЪ'Цаатомы водорода Н или метилCI-1 3 ,моа+епо получитъ моле'х;улы ра зпыхвеществ ('х;силол, бензол и др.) .С'х;ОЛ'Ь'х;О химичес'х;и разпых моле'х;ул можпо полу1)читъ та'х;им путём?С'х;ОЛЪ'х;О2)О,... , 6изпих моле'х;улсприсоедипёппъtмиатомами во дорода?Решен и е.
Самодействие группы диэдр а4221) Имеем D6 = (t,f , s), t = f = sгруппа диэдра порядкаtf6,D6.=е, D6где- вращение на 60° вокруг центр а квадрата;-симметрия относительное прямой, проходящейчерез середины противоположных сторонs= 12--( 3 оси);симметрия относительное прямой, проходящейчерез противоположные вершин( 3 оси).Пр онумеруем последовательно вершины пр ав ильного6- угольника 1, ...
, 6.П ерестановки ниже указаны для случая, когда осьfпроходит через середины сторонs - через вершин ы 1 и 4.(2-3) и (5-6), а ось232IIIgЕD6еt t5't2 t4't3fsпоток: Глава4.Теория перечисления ПойаперестановкаType(g)(1) . .. (6)(123456)(135) (246)(14) (25) (36)(14)(23)(56)(1) (4) (26) (35)(6,0, . . . 0)(о, . . . ' о , 1)( 0, 0, 2, . .
. 0)(о, 3, о , . .. о)(о, 3, о , ... о)( 2, 2, о , ... )Всего молекулw(g)подстановка х 1-#612213312xlxl6х23хз2х23х2х2== ... ==1 2х6== 2(Н и метил СНз) :м== 64 + 4 + 8 + 32 + 3 . 16 == 39 == 13.3·432) Число молекул с О , . . . , 6 атомами водорода- обозначение Yl == Н , У2 == 1 и подстановка Xk == Hk + 1,k == 1, 6 в Р .W ==1126[ (Н + 1 ) +3(Н + 1 ) (Н + 1 ) +4(Н + 1 ) +322223+ 2(Н + 1) + 2(Н + 1) J ==42653== Н + Н + 3 . Н + 3 . Н + 3 . Н + н + 1 .26Итого : молекул с числом атомов водорода (как радикала) - Н3== 0, 1, 5шт. , всегоЗадачаных и-И 6 -ПО 1 ШТ., Н== 2, 3И4 - ПО13.4.29. Сгх;олъгх;о существует12 синих бусин ?о;нсерелий из б гх;рас 4.4.(IIIпоток) Теория перечисления ПойаРешен и е.233Цикловой индекс самодействия группы диэдра (было ранее)n1 [хn/2 + х 2х n/2-1] , n21 24n6 + 12====ср( 1 ) ==ср( 2) ==18, D(18)ср( 6) ====..четно,2,2,ср( 9) ==6,ср( 1 8) ==6.==1 [ х 18 +х 9 +2х 6 +2х 3 +6х 2 +6х 1 J + 1 [ х 9 +х 2 х 8 J12182123694361 [ х118 + 10х2+9 2хз+62х6+36х9+2 6х18+1 9х1х22 8J.36+ 1,Xk ==У k==P (D18)нечетно,1, 2, 3, 6, 9, 18 },ср( 3) ==1,1,По формуле :==== {••136W==[ (у+ 1)18 + 10(у2 + 1)9 + 2(у3 + 1)6 + 2(у6 + 1)3++ 6(у9 + 1)2 + 6(у18 + 1) + 9 (у + 1 )2(у8 + 1)8 J+9 (с~+ cg) ) у6] ==1====636 [ ..
. + (18654 + 840 + 6 + 30 + 756)у J== 56 1у6==Ответ. 561 .поток: Глава234IIIЗада ча4.30.Теория перечислении ПойаНайти число расrк;расоrк; rк;уба в rк;рас'Н'ЬlU иси'НиU 'ЦВета СР ешен ие.4.5rк;раС'Н'Ьl.Ми рёбра.ми .Ранее был найден цикловой индекс действиягруппы О на рёбр а куба :P(O ~ R)Yk==xkW ==6х 3 + 3х 6 + 6х 2х 5 + 8х 4 ] .== 1 [ х 12+14212324+ 1,1[ (у+ 1)12 + 6(у4 + 1) з + 3(у2 + 1)6 +24+ 6(у + 1 )2(у2 + 1)5 + 8(у3 + 1)4] ==1524 [ .
.. + (792 + 6 . 2 . 10) у ]== ...Ответ:38.== ...+ (33 + 5)у5792 + 120+24== .. .5+ 38у .5.1 . (IIIпоток)Глава2355Частично упорядоченныемножестваОсновные понятия теории ч.у. мно5.1жеств5.1 . Пару Р == ( Р, ~ ), где Р - непумножество, а ~ - рефлексивное , антисимметричОпределениестоеное и транзитивное бинарное отношение на нём, называFот частич'Но упорядоче'Н'НЫМ м'Ножеством ( сокращённо ч . у. М'НО:JfСеством, англ . poset).Рефлексивность(R ): х ~ х;Антисимметричность (AS): (х ~у) & (у~ х) ==? х ==у;Транзитивность (Т): (х ~у) & (у~ z) ==? х ~ z.Пример• ( Р (М), С) - классический пример5.1.ч.у.
множества (упорядочивание множеств6'КЛ?·Ort.te'НU?{) , М -=j: .0);• ( rN,~)и ( rN,) -подва упорядочивания одногомножества.• Пусть М - множество людей, h(x) -w(x)- вес человека х .О п ределим на отношение р на М :рост, а236Глава5.Ч.у. множествах РУ ===? ( h ( х) ~ h (у)) & (w ( х) ~ w (у)).Является ли р отношением частичного порядкана М?Нет.неррефлексивноявляетсяхру & урхитранзитивно,антисимметричным~ноотношением:х == у (могут найтись два человека с одинаковыми ростом и весом) .Отношения со свойствами (R) и (Т) называют предпор.ядrх;а.ми.Понятное обозначение:а<Ь<=>#(а ~ Ь) & (а• если (х ~ y)V(y ~ х), то х и у сравrни.мы (хrvЬ)у) ,иначе они rнесравrни.мы (х ~ у);•полrныu (лuнeurнъtu) пор.ядоrх;, если \1 Х, у:Х•если в Р нет ни одной пары различных сравниrvу;мых элеме нтов , то это тривиально упорядоченноемножество;•хrнепосредствеrнrнонепосредственнох ~z~у ===?(zследует за х),== х) Vупредшествует(zх ~у,(уесли==у);• { х Е Р а ~ х ~ Ь } - и н тер в ал [ а, Ь] ;Ч .
у. множество, все интервалы которого конечны-лоrх;алъно rх;оrнечное;• v1 < ... <ностьVn def== [v1,попарноцепъ в Р ;. . . , Vn J -цепъn,а совокуп-несравнимых элементов-аrнти5.1 . (III поток)237• цепь .магх;си.малъна.я (насыщенная), если при добавлении к ней Л}обого элемента она перестаётбыть цепью;• ~ -двойственный к ~ порядок: ~d{::}~-оР ис .5.1.Диагр аммы 3-элементных ч . у. множествII1)2)3)....)NI><I7)8)v .5)Р ис .л .••••I..•6)9)10)11)13 )1....)15)5.2. Диаграммы12)16)всех 4-элементных ч . у. множеств238Глава1605.Ч.у.
множествао:3690201214541015925:з1Рис.5.3. Диаграмма D(180) всех делителей числа2 2180 == 2 3 5. Показаны одна из максимальных цепейи интервал [ 3, 60 ]GF(2)Р ис.5.4.ДиаграммаХассевсехподполейGF ( 218 ) , упорядоченных по вкл1очению .поля5.1 . (III поток)239Ч.у. множества: особые элементыОпредел ен ие( Р,~)5.2 .Э лементиЕназывают :•мапсималъным, если и ~ х8МU'НU.МаЛ'Ь'НЫМ, еСЛИ и ~ Х•наиболъшим, если х ~ и,•uаимеuъшим, если х ~ иР**ч . у.множестваи == х,и == Х,для л1обых х Е Р.Наибольший( 1) и наименьший (О) - граниtttные элементъt.
В конечном ч . у. множестве имеется как ми нимумпоодномумаксимальному иминимальномуэлеме нту.161812896415101431121357171Рис.ший5.5. Ч .у. множество ( { 1, ... , 18}, ) . 1 - наименьэлемент, 11 ... 18 - максимальные .Глава2405.Ч.у. множестваРанжированные ч.у. множества.Цепное условие Жордана-Дедекинда Все максимальные цепи между л1обыми двумя сравнимыми элементами элементами локаль:но конечного ч.у. множества имеют одинаковую длину.Еслич .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
