Теория перечисления Пойя (1127205), страница 3
Текст из файла (страница 3)
. . xjnn,(1j1 j1 !)(2j2 j2 !) . . . (njn jn !)1Xn/dϕ(d)xd , ϕ ôóíêöèÿ Ýéëåðà,nd|n((n−1)/21,11 x22xhi åñëè n íå÷¼òíî,P (Dn ) = P (Zn ) +n/2n/2−1122+ x1 x2, åñëè n ÷¼òíî,4 x2P (Zn ) =1 8x1 + 9x42 + 6x24 + 6x24 + 8x21 x23 (íà âåðøèíû),α241 12P (O : E) =x1 + 3x62 + 8x43 + 6x24 + 8x21 x52 + 6x34 (íà ð¼áðà),α241 6P (O : F ) =x1 + 3x21 x22 + 6x21 x4 + 6x32 + 8x23 (íà ãðàíè).α24P (O : V ) =ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Ðàçäåëû I1Äåéñòâèå ãðóïïû íà ìíîæåñòâå2Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿêîìáèíàòîðíûõ çàäà÷3Ïðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿêîìáèíàòîðíûõ çàäà÷4Çàäà÷è ñ ðåøåíèÿìè48 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà49 / 76Ïðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Òåîðåìà ÏîéàÊ ìíîæåñòâó T , |T | = N , ãðóïïå G, |G| = n è äåéñòâèþG : T äîáàâèì ìíîæåñòâî R = {c1 , . . . , cr }, ìåòîê (¾êðàñîê¿),αè ñîâîêóïíîñòü ôóíêöèé F = RT ïðèïèñûâàíèÿ ìåòîê(ðàñêðàøèâàíèé) ýëåìåíòàì T .◦G, äåéñòâóÿ íà T , äåéñòâóåò è íà RT ◦ : RT × G = RT .Ïðèäàäèì âåñ ýëåìåíòàì R : w(ci ) = yi , i = 1, r.Òåîðåìà (Ðåäôèëäà-Ïîéà; 1927, 1937)Öèêëîâîé èíäåêñ äåéñòâèÿ ãðóïïû G íà RT åñòüP (G : RT ) = P (G : T, x1 , . . .
, xN )ααxk =y1k +...+yrk , k=1,NÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà50 / 76Ïðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Òåîðåìà Ïîéà...ÑëåäñòâèåÅñëè âñå âåñà âûáðàíû îäèíàêîâûìè (y1 = . . . yr = 1), òîx1 = . . . xN = r è W (F ) ÷èñëî êëàññîâ ýêâèâàëåíòíîñòèC(G : RT ) = C(G : T ) = P (G : T, r, . . . , r) .ααα ëåììà Á¼ðíñàéäà.×òî ìîæíî îïðåäåëèòü (ïîäñ÷èòàòü) ñ ïîìîùüþ:ëåììû Á¼ðíñàéäà îáùåå ÷èñëî íåýêâèâàëåíòíûõðàçìåòîê (ðàñêðàñîê);òåîðåìà Ðåäôèëäà-Ïîéà ÷èñëî ðàçìåòîê äàííîãî òèïà,ò.å. ñîäåðæàùèõ äàííîå êîëè÷åñòâî ýëåìåíòîâêîíêðåòíîãî öâåòà.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà51 / 76Ïðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Ä. Ïîéà(Polya Gyorgy, 18871985) âåíãåðñêèéìàòåìàòèê.Ïîñëå îêîí÷àíèÿ Áóäàïåøòñêîãîóíèâåðñèòåòà ðàáîòàë âÂûñøåé òåõíè÷åñêîé øêîëå â Öþðèõå,à ñ 1940 ã.
â Ñòýíôîðäñêîìóíèâåðñèòåòå (ÑØÀ).Äü¼ðäü ÏîéàÂí¼ñ çàìåòíûé âêëàä â òåîðèþ ÷èñåë, ôóíêöèîíàëüíûé àíàëèç,ìàòåìàòè÷åñêóþ ñòàòèñòèêó (ðàñïðåäåëåíèå Ïîéà) èêîìáèíàòîðèêó (òåîðåìà ÐåäôèëäàÏîéà).Ïîéà ìíîãî ðàáîòàë ñî øêîëüíûìè ó÷èòåëÿìè ìàòåìàòèêè èâí¼ñ áîëüøîé âêëàä â ïîïóëÿðèçàöèþ íàóêè.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà52 / 76Ïðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Óñëîæíèì çàäà÷ó îá îæåðåëüÿõ N = 5, r = 3( 5 áóñèí 3 öâåòîâ).Öâåòà êðàñíûé, ñèíèé, çåë¼íûé.
Îæåðåëüÿ îäèíàêîâû, åñëèîäíî ïîëó÷àåòñÿ èç äðóãîãî ïîâîðîòîì è/èëè ïåðåâîðîòîì.Ñêîëüêî èìååòñÿ îæåðåëèé, èìåþùèõ ðîâíî 2 êðàñíûå áóñèíû?Çàäà÷à îá îæåðåëüÿõÐåøåíèå. Áûëî: G = D5 , öèêëîâîé èíäåêñ1P = 10x51 + 4x5 + 5x1 x22 ,âñåãî îæåðåëèé P (3, . . . , 3) = 39 (òîëüêî ïîâîðîò 51).x1 = y1 + y2 + y3 , x2 = y12 + y22 + y32 , . . . , x5 = y15 + y25 + y35 .x1 = y + 2, w(êðàñíûé) = y1 ,y1 = y,x2 = y 2 + 2,w(ñèíèé)= y2 , ⇒⇒y2 = y3 = 1,...w(çåë¼íûé) = y3 ,x5 = y 5 + 2.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà53 / 76Ïðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à îá îæåðåëüÿõ: 5 áóñèí 3 öâåòîâ...1 5x1 + 4x5 + 5x1 x22105Xxk →7 y k + 2, k = 1, 5; P (y) =ui y i , u2 = ?P (x1 , . . . , x5 ) =i=11 u0 + u1 y + u2 y 2 + . .
. + u5 y 5 =101 =(y + 2)5 + 4(y 5 + 2) + 5(y + 2)(y 2 + 2)2 =101 =. . . + C52 23 y 2 + . . . + 5(y + 2)(y 4 + 4y 2 + 4) =101 =. . . + (10 · 8 + 5 · 2 · 4)y 2 + . . . .10P (y) =u2 =80 + 40= 12.10ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà54 / 76Ïðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ðàñêðàñêå êóáàÂåðøèíû êóáà ïîìå÷àþò êðàñíûìè è ñèíèì öâåòàìè.Ñêîëüêî ñóùåñòâóåò123ðàçíîïîìå÷åííûõ êóáîâ;êóáîâ, ó êîòîðûõ ïîëîâèíà âåðøèíû êðàñíûå;êóáîâ, ó êîòîðûõ íå áîëåå 2 êðàñíûõ âåðøèí?Ðåøåíèå.
Öèêëîâîé èíäåêñ äåéñòâèÿ ãðóïïû O íà âåðøèíûêóáàP (O : V ) =α11 8x1 + 6x24 + 9x42 + 8x21 x23 .24×èñëî ðàçíîïîìå÷åííûõ êóáîâ #Col(3) = P |x1 =...=x8 =2 =552= 23 .24ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ðàñêðàñêå êóáà... 81( 24x1 + 6x24 + 9x42 + 8x21 x23 )2w(êðàñíûé) = y, w(ñèíèé) = 1, xk = y k + 1, k = 1, 8:1#Col(4, 4) =(y + 1)8 + 9 · (y 2 + 1)4 + 6 · (y 4 + 1)2 +24+ 8 · (y + 1)2 (y 3 + 1)2 =1. . .
+ 28y 2 + C84 y 4 + . . . + 9(. . . 4y 2 + 6y 4 + . . .)+=24. . . + 6 · 2y 4 . . . + 8(. . . + 2y + y 2 + . . .)(. . . + 2y 3 + . . .) .1168u4 =[ 70 + 9 · 6 + 6 · 2 + 8 · 2 · 2 ] == 7.24243#Col(6 2, ∗) = u0 + u1 + u2 . u0 = u1 = 1.1u2 =. . .+28y 2 +. . .+9(. . .+4y 2 . . .)+8(. . .+y 2 +. . .) =2428 + 36 + 872=== 3.2424#Col(6 2, ∗) = 1 + 1 + 3 = 5.55 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà56 / 76Ïðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ÷èñëå ìîëåêóëÇàäà÷à.Ðàññìîòðèì ìîëåêóëû 4-âàëåíòíîãî óãëåðîäà C:××C×CH3×ClCCH3Clãäå íà íà ìåñòå × ìîãóò íàõîäèòñÿ CH3 (ìåòèë), C2 H5 (ýòèë),H (âîäîðîä) èëè Cl (õëîð).
Íàïðèìåð äèõëîðáóòàí.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ÷èñëå ìîëåêóë...(ïðîäîëæåíèå)Íàéòè1îáùåå ÷èñëî M âñåõ ìîëåêóë;2÷èñëî ìîëåêóë ñ H = 0, 1, 2, 3, 4 àòîìàìè âîäîðîäà.57 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà58 / 76Ïðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ÷èñëå ìîëåêóë...Ðåøåíèå. Êàêàÿ ãðóïïà äåéñòâóåò è íà êàêîì ìíîæåñòâå?T = h t, f i , t3 = f 2 = e, ãäåt âðàùåíèå íà 120◦ âîêðóã îñè,ïðîõîäÿùåé ÷åðåç âåðøèíóè öåíòð òåòðàýäðà (MM);f âðàùåíèå íà 180◦ âîêðóã îñè,ïðîõîäÿùåé ÷åðåç öåíòðû äâóõïðîòèâîïîëîæíûõ ð¼áåð ().P (T : V ) =α1 4x1 + 8x1 x3 + 3x22 .12Ïî÷åìó ïåðåä x1 x3 êîýôôèöèåíò 8, âåäü îñåé MM âñåãî 4?ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà59 / 76Ïðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ÷èñëå ìîëåêóë...
(ãðóïïà âðàùåíèÿ òåòðàýäðà)Öèêëîâîé èíäåêñ äåéñòâèÿ ãðóïïû T íà âåðøèíû òåòðàýäðà get, t2fT ype(g)h 4, 0, 0, 0 ih 1, 0, 1, 0 ih 0, 2, 0, 0 iP (x1 , . . . , x4 ) =w(g)x41x1 x3x22Êîë-âî14·2=831 4x1 + 8x1 x3 + 3x2212ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà60 / 76Ïðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ÷èñëå ìîëåêóë... (ãðóïïà âðàùåíèÿ òåòðàýäðà)...1Èìååì N = 4, äåéñòâèå T íà âåðøèíû òåòðàýäðà:1 4P (x1 , . . . , x4 ) =x1 + 8x1 x3 + 3x22 .12Âñåãî ìîëåêóë ( 4 ðàäèêàëà) 1 416 · 27= 36 .M = P (4, . . . , 4) =4 + 8 · 4 · 4 + 3 · 42 =12122Âåñà: y1 = H, y2 = y3 = y4 = 1.Ïîäñòàíîâêà â P : xk = Hk + 3, k = 1, 4.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà61 / 76Ïðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ÷èñëå ìîëåêóë...
(ãðóïïà âðàùåíèÿ òåòðàýäðà)...P (x1 , x2 , x3 ) =112x41 + 8x1 x3 + 3x22 .Ïðîâîäèì ïîäñòàêîâêó xk 7→ H k + 3, k = 1, 2, 3.2 i1 hP (H) =(H + 3)4 + 8 (H + 3) H3 + 3 + 3 H2 + 3=121 4H + 4 · H3 · 3 + 6 · H2 · 9 + 4 · H · 27 + 81 +=12+8 H4 + 3H3 + 3H + 9 + 3 H4 + 6H2 + 9 == 1 · H4 + 3 · H3 + 6 · H2 + 11 · H + 15.Èòîãî èìååòñÿ ìîëåêóë ñ ÷èñëîì àòîìà âîäîðîäà:ñ 4-ìÿ 1 øò., ñ 3-ìÿ 3 øò., ñ 2-ìÿ 6 øò.,ñ 1-ì 11 øò., áåç àòîìîâ âîäîðîäà 15 øò.,âñåãî 1 + 3 + 6 + 11 + 15 = 36.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÇàäà÷è ñ ðåøåíèÿìèÐàçäåëû I1Äåéñòâèå ãðóïïû íà ìíîæåñòâå2Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿêîìáèíàòîðíûõ çàäà÷3Ïðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿêîìáèíàòîðíûõ çàäà÷4Çàäà÷è ñ ðåøåíèÿìè62 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÇàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÏ-1Êàæäîå âðàùåíèå êóáà ïåðåñòàâëÿåò åãî ãðàíè, ò.å. çàäà¼òãðóïïó ïåðåñòàíîâîê.Îïðåäåëèòü ñòàáèëèçàòîð íåêîòîðîé ãðàíè â ýòîé ãðóïïå.Ðåøåíèå.Ïóñòü a ãðàíü êóáà.Ïåðåñòàíîâêè, îñòàâëÿþùèå íåïîäâèæíîé ãðàíü ñóòüe, t, t2 , t3 , ãäå t âðàùåíèå íà 90◦ âîêðóã îñè, ïðîõîäÿùåé÷åðåç äâå ïðîòèâîïîëîæíûå ãðàíè.Òàêèì îáðàçîì, Stab (a) = h t i ∼= Z4 .63 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà64 / 76Çàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÏ-2Íàéòè öèêëîâîé èíäåêñ ñàìîäåéñòâèÿ ãðóïïû ñèììåòðèèïðàâèëüíîãî òðåóãîëüíèêà.Ðåøåíèå.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
