Теория перечисления Пойя (1127205), страница 2
Текст из файла (страница 2)
. . , 1) = 1: åñëè âñå ýëåìåíòû ïîêðàñèòü âîäèí öâåò, òî òàêèõ ðàñêðàñîê îäíà.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà28 / 76Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à ïðî ñëîâàÑîñòàâëÿþòñÿ ñëîâà äëèíû l > 2 èç àëôàâèòà { a1 , . . . , am }.Ñëîâà ñ÷èòàþòñÿ ýêâèâàëåíòíûìè, åñëè îíè ïîëó÷àþòñÿ îäíîèç äðóãîãî ïåðåñòàíîâêîé êðàéíèõ áóêâ.Îïðåäåëèòü ÷èñëî S íåýêâèâàëåíòíûõ ñëîâ.ml + ml−1.2Äðóãîå ðåøåíèå: G = { e, g } ∼= Z2 ;Áûëî ðåøåíèå: S =l−2z }| {T : . . .
.|{z}lÝëåìåíò g ãðóïïû GegT ype(g)w(g)h l, 0, . . . , 0 ixl11h l − 2, 1, 0, . . . , 0 i xl−21 x2i1 h lÖèêëîâîé èíäåêñ: P (x1 , . . . , xl ) =x1 + x1l−2 x12 .2S = P (m, . . . , m).# ìîíîìîâ11ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà29 / 76Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Êëàññè÷åñêàÿ êîìáèíàòîðíàÿ çàäà÷à îá îæåðåëüÿõÎæåðåëüå îêðóæíîñòü, íà êîòîðîé íà ðàâíûõ ðàññòîÿíèÿõ ïîäóãå (â âåðøèíàõ ïðàâèëüíîãî ìíîãîóãîëüíèêà) ðàñïîëàãàþòñÿ¾áóñèíû¿.. Ñêîëüêî ðàçëè÷íûõ îæåðåëèé ìîæíîñîñòàâèòü èç N áóñèí r öâåòîâ?Çàäà÷à îá îæåðåëüÿõÂàðèàíòû.
Îæåðåëüÿ íåðàçëè÷èìû, åñëè îäíî ïîëó÷àåòñÿ èçäðóãîãî ñàìîñîâìåùåíèåì:1 ïîâîðîòîì â ïëîñêîñòè (áóñèíû ïëîñêèå,îêðàøåíû ñ îäíîé ñòîðîíû) ñàìîäåéñòâèå öèêëè÷åñêîé ãðóïïû ZN ;2ïîâîðîòîì è ïåðåâîðîòîì â ïðîñòðàíñòâå(áóñèíû êðóãëûå) ñàìîäåéñòâèå ãðóïïû äèýäðà (äâîéíîéïèðàìèäû) DN .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà30 / 76Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à îá îæåðåëüÿõ: N = 5, r = 3Ñêîëüêî ðàçíûõ îæåðåëèé ìîæíî ñîñòàâèòü èç 5 áóñèí 3öâåòîâ?T âåðøèíû ïðàâèëüíîãî ïÿòèóãîëüíèêà. #Col(3) =?¶ Îæåðåëüÿ îäèíàêîâû, åñëè îäíî ïîëó÷àåòñÿ èç äðóãîãî ïîâîðîòîì.Ðåøåíèå.
G ∼= Z5 = hti, t5 = e, n = 5.Ýëåìåíò ãðóïïûet, t2 , t3 , t4# ìîíîìîâ14Öèêëîâîé èíäåêñ: P (x1 , x2 , x3 , x4 , x5 ) = 15 x51 + 4x5 .T ype(g)h 5, 0, 0, 0, 0 ih 0, 0, 0, 0, 1 i#Col(3) = P (3, . . . , 3) =w(g)x51x535 + 4 · 33 · 85== 3 · 17 = 51.55ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à Îëèìïèàäû ¾Ïîêîðè Âîðîáü¼âû ãîðû 2009¿Äëÿ 50 äåòåé äåòñêîãî ñàäà çàêóïëåíû 50 îäèíàêîâûõòàðåëîê. Ïî êðàþ êàæäîé òàðåëêè ðàâíîìåðíî ðàñïîëîæåíî 5áåëûõ êðóæî÷êîâ.
Âîñïèòàòåëè õîòÿò ïåðåêðàñèòü êàêèå-ëèáîèç ýòèõ êðóæî÷êîâ â äðóãîé öâåò òàê, ÷òîáû âñå òàðåëêè ñòàëèðàçëè÷íûìè.Êàêîå íàèìåíüøåå ÷èñëî äîïîëíèòåëüíûõ öâåòîâ ïîòðåáóåòñÿèì äëÿ ýòîãî?31 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Êàê äîëæíû áûëè ðåøàòü øêîëüíèêèÐåøåíèå.Ïóñòü òðåáóåòñÿ r öâåòîâ.Îòáðîñèì r âàðèàíòîâ ðàñêðàñêè â îäèí öâåò.×èñëî îñòàëüíûõ âàðèàíòîâ áåç ó÷¼òà âîçìîæíîñòè ïîâîðîòà òàðåëêè: r5 − r;r5 − r5(êàæäûé âàðèàíò ïîâòîðÿåòñÿ 5 ðàç).ñ ó÷¼òîì ïîâîðîòà:Èòîãî: #Col(r) =r5 − rr5 + 4r+r =;55Ïðè 2 äîïîëíèòåëüíûõ öâåòàõ #Col(3) = 51.32 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà33 / 76Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à îá îæåðåëüÿõ: N = 5, r = 3, 2-é âàðèàíò· Îæåðåëüÿ îäèíàêîâû, åñëè îäíî ïîëó÷àåòñÿ èç äðóãîãîïîâîðîòîì è/èëè ïåðåâîðîòîì.G ãðóïïà äèýäðà D5 = ht, f i, t5 = f 2 = e, n = |D5 | = 10.Ýëåìåíò ãðóïïû get, t2 , t3 , t4f, tf, .
. . , t4 fÂñåãîT ype(g)h 5, 0, 0, 0, 0 ih 0, 0, 0, 0, 1 ih 1, 2, 0, 0, 0 iw(g)x51x5x1 x22# ìîíîìîâ145101 5x1 + 4x5 + 5x1 x22 .1035 + 4 · 3 + 5 · 33#Col(3) = P (x1 , . . . , x5 )|x1 =...=x5 =3 == 39.10Öèêëîâîé èíäåêñ: P =Çàïîìíèì ýòîò îòâåò.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà34 / 76Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ðàñêðàñêå ñòîðîí êâàäðàòà.Ñòîðîíû êâàäðàòà ðàñêðàøèâàþò â r öâåòîâ.Ñêîëüêî ñóùåñòâóåò ðàçëè÷íî îêðàøåííûõ êâàäðàòîâ?Çàäà÷à î ðàñêðàñêå ñòîðîí êâàäðàòàÐåøåíèå.
Ãðóïïà ñàìîñîâìåùåíèÿ êâàäðàòà â ïðîñòðíñòâå ãðóïïà äèýäðà D4 = h t, f, s i, êîòîðàÿ ïîðîæäàåòñÿ òðåìÿîáðàçóþùèìè:t : âðàùåíèå íà 90◦ âîêðóã öåíòðà ñèììåòðèè (â âûáðàííîìíàïðàâëåíèè ïî èëè ïðîòèâ ÷àñîâîé ñòðåëêè);f : îñåâàÿ ñèììåòðèÿ îòíîñèòåëüíî îñè, ïðîõîäÿùåé ÷åðåçñåðåäèíû ïðîòèâîïîëîæíûõ ñòîðîí;s : îñåâàÿ ñèììåòðèÿ îòíîñèòåëüíî îñè, ïðîõîäÿùåé ÷åðåçñåðåäèíû ïðîòèâîïîëîæíûõ âåðøèí.t4 = f 2 = s2 = e,|D4 | = 8 = n.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ðàñêðàñêå ñòîðîí êâàäðàòà...Ïðè ñàìîäåéñòâèè ãðóïïû D4 (N = 4) å¼ ýëåìåíòû áóäóòèìåòü ñëåäóþùèå âåñà:e : åäèíè÷íàÿ ïåðåñòàíîâêà îñòàâèò âñå ñòîðîíû íà ìåñòå,ò.å.
èìåþòñÿ 4 öèêëà äëèíû 1, âåñ x41 (1 ïåðåñòàíîâêà);t, t3 : ñòîðîíû öèêëè÷åñêè ïåðåõîäÿò äðóã â äðóãà ïî è ïðîòèâ÷àñîâîé ñòðåëêå, äëèíà öèêëà 4, âåñ x14 (2 ïåðåñòàíîâêè);t2 : ñòîðîíû ïåðåõîäÿò â ïðîòèâîïîëîæíûå, ÷òî äà¼ò äâàöèêëà äëèíû 2, âåñ x22 (1 ïåðåñòàíîâêà);f : äâå ïðîòèâîïîëîæíûå ñòîðîíû íà ìåñòå, îñòàëüíûå äâåìåíÿþòñÿ ìåñòàìè, ò.å. èìåþòñÿ äâà åäèíè÷íûõ öèêëà èîäèí äëèíû 2, âåñ x21 x12 (2 îñè);s : â äâóõ ïàðàõ ñìåæíûõ ñòîðîí ýëåìåíòû ìåíÿþòñÿìåñòàìè, ÷òî äà¼ò äâà öèêëà äëèíû 2, âåñ x22 (2 îñè).35 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà36 / 76Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ðàñêðàñêå ñòîðîí êâàäðàòà...Öèêëîâîé èíäåêñ ñàìîäåéñòâèÿ D4 :1 4PD4 (x1 , .
. . , x4 ) =x1 + 2x4 + 3x22 + 2x21 x2 .8×èñëî ðàñêðàñîê êâàäðàòà â r öâåòîâ:1 4PD4 (r, . . . , r) =r + 2r + 3r2 + 2r3 .8 ÷àñòíîñòè, â äâà è òðè öâåòà:16 + 4 + 12 + 1624 + 2 · 2 + 3 · 22 + 2 · 23== 6.88443 +2·3+381 + 6 + 81168#Col(3) ==== 21.888#Col(2) =ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ðàñêðàñêå êóáà(ðàñêðàñêà ãðàíåé êóáà â äâà öâåòà).Ãðàíè êóáà ðàñêðàøèâàþò â 2 è 3 öâåòà.Ñêîëüêî ñóùåñòâóåò ðàçëè÷íî îêðàøåííûõ êóáîâ?Çàäà÷àÐåøåíèå.
Íàïîìèíàíèå: G = O = h t, f, r i, |O| = 24.t âðàùåíèå íà 90◦ âîêðóã îñè,ïðîõîäÿùåé ÷åðåç ñåðåäèíû äâóõïðîòèâîïîëîæíûõ ãðàíåé (22, 3 îñè);f âðàùåíèå íà 180◦ âîêðóã îñè,ïðîõîäÿùåé ÷åðåç ñåðåäèíû äâóõïðîòèâîïîëîæíûõ ð¼áåð (◦◦, 6 îñåé);r âðàùåíèå íà 120◦ âîêðóã îñè, ïðîõîäÿùåé ÷åðåç äâåïðîòèâîïîëîæíûå âåðøèíû (MM, 4 îñè).37 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ðàñêðàñêå êóáà: îáîçíà÷åíèÿ ýëåìåíòîâÎáîçíà÷èì ÷åðåç F ìíîæåñòâî ãðàíåé êóáà; |F | = N = 6.Âûáåðåì íåêîòîðóþ ãðàíü êóáà (êâàäðàò) è îáîçíà÷èì å¼ ¬,à ïàðàëëåëüíóþ åé .Ïåðåíóìåðóåì ïîñëåäîâàòåëüíî âåðøèíû ãðàíè ¬ ÷èñëàìè1, .
. . , 4, à âåðøèíû ãðàíè ÷èñëàìè 5, . . . , 8 òàê, ÷òîâåðøèíà ñ íîìåðîì i ñìåæíà ñ âåðøèíîé ñ íîìåðîìi + 4, i = 1, 2, 3, 4.Ïåðåñòàíîâêè äàëåå óêàçàíû äëÿ ñëó÷àÿ, êîãäà îñü âðàùåíèÿhti ïðîõîäèò ÷åðåç ñåðåäèíû ãðàíåé ¬ è ,hf i ïðîõîäèò ÷åðåç ñåðåäèíû ð¼áåð ( 3-7 ) è ( 1-5 ),hsi ïðîõîäèò ÷åðåç âåðøèíû (1) è (7),à ãðàíè îáîçíà÷åíû:(1-2-6-5) ÷åðåç ®, ïàðàëëåëüíàÿ åé ãðàíü °,ãðàíü (2-3-7-6) ÷åðåç ¯, ïàðàëëåëüíàÿ åé ãðàíü ±.38 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ðàñêðàñêå êóáà: îáîçíà÷åíèÿ âåðøèí è ãðàíåé39 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ðàñêðàñêå êóáà: îáîçíà÷åíèÿ îñåét4 = f 2 = r3 = e40 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà41 / 76Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ðàñêðàñêå êóáà: ðàñêðàñêà ãðàíåé |F | = N = 6g∈Oet, t3t2fr, r2Âñåãîïåðåñòàíîâêà(¬). . . (±)(¬)()(®¯°±)(¬)()(®°)(¯±)(¬)(®±)(¯°)(¬®±)(¯°)T ype(g)h 6, 0, . . . ih 2, 0, 0, 1, 0, ih 2, 2, 0, .
. . ih 0, 3, 0, . . . ih 0, 0, 2, 0, . . . iw(g)x61x21 x4x21 x22x32x23#w(g)13·2=6364·2=8241 6x1 + 6x21 x4 + 3x21 x22 + 6x32 + 8x23 .241 6#Col(2) = P (2, . . . , 2) =2 + 12 · 23 + 3 · 24 + 8 · 22 = 10,241 6#Col(3) = P (3, . . . , 3) =3 + 12 · 33 + 3 · 34 + 8 · 32 = 48.24P (x1 , . . . , x6 ) =ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà42 / 76Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Öèêëîâîé èíäåêñ äåéñòâèÿ ãðóïïû îêòàýäðà íà ìíîæåñòâî R ð¼áåð êóáà ( |R| = N = 12):g∈Oet, t3t2fr, r2ÂñåãîT ype(g)h 12, 0, . . .
ih 0, 0, 0, 3, 0, 0 ih 0, 6, 0, . . . ih 2, 5, 0, . . . ih 0, 0, 4, 0, . . . iw(g)x121x34x62x21 x52x43#w(g)13·2=6364·2=824Öèêëîâîé èíäåêñ:P (O : R) =α1 12x1 + 6x34 + 3x62 + 6x21 x52 + 8x43 .24ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà43 / 76Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Öèêëîâîé èíäåêñ äåéñòâèÿ ãðóïïû îêòàýäðà íà ìíîæåñòâî V âåðøèí êóáà ( |V | = N = 8):g∈Oet, t3t2fr, r2ÂñåãîT ype(g)h 8, 0, . .
. ih 0, 0, 0, 2, 0, 0 ih 0, 4, 0, . . . ih 0, 4, 0, . . . ih 2, 0, 2, 0, . . . iw(g)x81x24x42x42x21 x23#w(g)13·2=6364·2=824Öèêëîâîé èíäåêñ:P (O : V ) =α1 8x1 + 6x24 + 9x42 + 8x21 x23 .24ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à (ïåðå÷èñëåíèå ãðàôîâ).Ñêîëüêî èìååòñÿ íåîðèåíòèðîâàííûõ íåïîìå÷åííûõ ãðàôîâ (áåçïåòåëü è êðàòíûõ ð¼áåð) ñ òðåìÿ âåðøèíàìè?Ðåøåíèå. T ñòîðîíû òðåóãîëüíèêà, N = 3.G∼= S3 âñå ïåðåñòàíîâêè ñòîðîí,n = 3! = 6.G : T ñàìîäåéñòâèå ãðóïïû S3αÃðàôû íåîðèåíòèðîâàííûå r = 2 ïîìåòêè ¾åñòü ðåáðî/íåò ðåáðà¿S3 = { e, (abc), (acb), ((a)(bc)), ((b)(ac)), ((c)(ab)) }44 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà45 / 76Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Ïåðå÷èñëåíèå ãðàôîâ...S3 =e, (abc), (acb), ((a)(bc)), ((b)(ac)), ((c)(ab))| {z } | {z } | {z } | {z } | {z }tt2fÝëåìåíò ãðóïïû ge = (a)(b)(c)t, t2f, tf, t2 fÂñåãîP (x1 , x2 , x3 ) =w(g)x31x13x11 x12#w(g)12361 3x1 + 2x13 + 3x11 x12 ,6P (2, 2, 2) = 4.= h t, f it2 ftfT ype(g)h 3, 0, 0 ih 0, 0, 1 ih 1, 1, 0 iÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà46 / 76Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Ïåðå÷èñëåíèå ãðàôîâ...Ïåðå÷èñëèì îðèåíòèðîâàííûå: ïóñòîé ãðàô è ãðàôû◦[[]◦◦◦u◦w ◦◦ [[]◦◦◦ [[]◦ u◦◦ [[]◦ u◦◦◦[[]◦[[] âñåãî 7 ãðàôîâ, íåîðèåíòèðîâàííûõ 4.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà47 / 76Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Öèêëîâûå èíäåêñû ñàìîäåéñòâèÿ Sn , Zn , Dn èäåéñòâèÿ O íà ýëåìåíòû êóáàP (Sn ) =XN(j1 ,...,jn )∈ n01j1 +2j2 +...+njn =nxj11 xj22 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
