Теория перечисления Пойя (1127205)
Текст из файла
ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÒåìàIIIÒåîðèÿ ïåðå÷èñëåíèÿ Ïîéà1 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÐàçäåëû I1Äåéñòâèå ãðóïïû íà ìíîæåñòâå2Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿêîìáèíàòîðíûõ çàäà÷3Ïðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿêîìáèíàòîðíûõ çàäà÷4Çàäà÷è ñ ðåøåíèÿìè2 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÄåéñòâèå ãðóïïû íà ìíîæåñòâå: äâà îïðåäåëåíèÿÃðóïïà G = h G, ◦, e i, |G| = n.Ìíîæåñòâî T , |T | = N .
ìíîæåñòâî âñåõ áèåêöèé (ïåðåñòàíîâîê)ýëåìåíòîâ T .Symm(T ) ñèììåòðè÷åñêàÿ ãðóïïà ìíîæåñòâà T :Bij(T )Symm(T ) = h Bij(T ), ∗, 1T i ,Îïðåäåëåíèå (I)α ∈ Hom ( G, Symm(T ) ).Äåéñòâèå α ãðóïïû G íà ìíîæåñòâå T : ñèìâîëè÷åñêè G : T.α3 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÄåéñòâèå ãðóïïû íà ìíîæåñòâå: äâà îïðåäåëåíèÿ...Îïðåäåëåíèå (II)α = h G, T ; ◦, ?, e i ,ãäå◦G × G → G ãðóïïîâàÿ îïåðàöèÿ;?G × T → T íîâàÿ îïåðàöèÿ.Àêñèîìû äëÿ îïåðàöèé:e ? t = t;(g ◦ h) ? t = h ∗ (g ? t).Çàïèñü îïåðàöèè ?: g(t) = t 0 .Àêñèîìû: e(t) = t è (g ◦ h)(t) = h(g(t)).Ò.å.
ýëåìåíòû g ãðóïïû G ïîðîæäàþò ïåðåñòàíîâêè íà T ,îáëàäàþùèå âûøåóêàçàííûìè ñâîéñòâàìè.4 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÄåéñòâèå ãðóïïû íà ìíîæåñòâå: ñõåìà5 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà6 / 76Äåéñòâèå ãðóïïû íà ìíîæåñòâåÄëÿ äàííîé ïåðåñòàíîâêè g :Ââåä¼ì îòíîøåíèå ýêâèâàëåíòíîñòè ∼g íà T deft ∼g t 0 = ∃ k g k (t) = t 0Ñìåæíûå êëàññû ýêâèâàëåíòíîñòè ∼g íàçûâàþòg -öèêëàìè.×èñëî âñåõ ñìåæíûõ êëàññîâ îáîçíà÷èì C(g).Êîëè÷åñòâà öèêëîâ äëèíû 1, 2, .
. . , N îáîçíà÷àþòν1 , ν2 , . . . , νN èëè ν1 (g), ν2 (g), . . . , νN (g).Óïîðÿäî÷åííóþ ñîâîêóïíîñòü êîëè÷åñòâ öèêëîâh ν1 , ν2 , . . . , νN i íàçûâàþò òèïîì ïåðåñòàíîâêè g èîáîçíà÷àþò T ype(g).Ïîíÿòíî, ÷òî C(g) =NPk=1νk (g) èNPk=1k · νk (g) = N .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà7 / 76Äåéñòâèå ãðóïïû íà ìíîæåñòâåÒèï ïåðåñòàíîâêè: ïðèìåðÏóñòüT = { 1, .
. . , 10 },g =1 2 3 4 5 6 7 8 9 109 6 1 8 5 2 7 10 3 4== (1, 9, 3)(2, 6)(4, 8, 10)(5)(7)ÒîãäàT ype(g) = h 2, 1, 2, 0, . . . , 0 i,C(g) = 2 + 1 + 2 = 5,|T | = 2 · 1 + 1 · 2 + 2 · 3 = 10.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÏëàòîíîâû òåëà ïðàâèëüíûå 3-ìåðíûå ìíîãîãðàííèêèÝòî òåòðàýäðÀ ýòî êóáèêÎêòàýäð äâîéñòâåíåí êóáó8 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà9 / 76Äåéñòâèå ãðóïïû íà ìíîæåñòâåÏëàòîíîâû òåëà ïðàâèëüíûå 3-ìåðíûå ìíîãîãðàííèêèÏëàòîíîâû òåëàòåòðàýäðêóá è îêòàýäðèêîñàýäð è äîäåêàýäðÎêòàýäðÃðóïïà âðàùåíèÿT (òåòðàýäðà)O (îêòàýäðà)Y (èêîñàýäðà)ÈêîñàýäðÏîðÿäîê ãðóïïû4 · 3 = 128 · 3 = 2412 · 5 = 60ÄîäåêàýäðÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà10 / 76Äåéñòâèå ãðóïïû íà ìíîæåñòâåT ãðóïïà âðàùåíèÿ òåòðàýäðàT = h t, f i, t3 = f 2 = e, ãäå:t âðàùåíèå íà 120◦ âîêðóã îñè,ïðîõîäÿùåé ÷åðåç âåðøèíóè öåíòð òåòðàýäðà (MM);òàêèõ îñåé 4.f âðàùåíèå íà 180◦ âîêðóã îñè,ïðîõîäÿùåé ÷åðåç öåíòðû äâóõïðîòèâîïîëîæíûõ ð¼áåð ();òàêèõ îñåé 3.|T | = (3 − 1) · 4 + (2 − 1) · 3 + 1 = 12.Òåòðàýäð äâîéñòâåíåí ñàìîìó ñåáå ⇒ äåéñòâèå íà ãðàíè =äåéñòâèå íà âåðøèíû.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà11 / 76Äåéñòâèå ãðóïïû íà ìíîæåñòâåÄåéñòâèå T íà ãðàíè (èëè âåðøèíû) òåòðàýäðà: òèïûïåðåñòàíîâîê2 : T ype(t) = T ype(t2 ) = h1, 0, 1, 0i;M: T ype(f ) = h0, 2, 0, 0i.|T | = 2 · 4 + 1 · 3 + 1 = 12.Òåòðàýäð äâîéñòâåíåí ñàìîìó ñåáå ⇒äåéñòâèå íà ãðàíè =äåéñòâèå íà âåðøèíû.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåO ãðóïïà âðàùåíèÿ êóáàO = h t, f, r i , t4 = f 2 = r3 = e, ãäåt âðàùåíèå íà 90◦ âîêðóã îñè,ïðîõîäÿùåé ÷åðåç ñåðåäèíû äâóõïðîòèâîïîëîæíûõ ãðàíåé (22),f âðàùåíèå íà 180◦ âîêðóã îñè,ïðîõîäÿùåé ÷åðåç ñåðåäèíû äâóõïðîòèâîïîëîæíûõ ð¼áåð (◦◦),r âðàùåíèå íà 120◦ âîêðóã îñè,ïðîõîäÿùåé ÷åðåç äâå ïðîòèâîïîëîæíûåâåðøèíû (MM)Ñêîëüêî îñåé êàæäîãî òèïà? 3, 6 è 4 ñîîòâåòñòâåííî.|O| = 3 · 3 + 1 · 6 + 2 · 4 + 1 = 24.12 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÄåéñòâèå O íà âåðøèíû êóáà: òèïû ïåðåñòàíîâîê2 : T ype(t) = T ype(t3 ) == h0, 0, 0, 2, 0, . . .i,T ype(t2 ) = h0, 4, 0, . . .i;◦ : T ype(f ) = h0, 4, 0, . . .i;M: T ype(r) = T ype(r2 ) = h2, 0, 2, 0, . . .i.13 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÏî âñåé ãðóïïå G:Îòíîøåíèå ýêâèâàëåíòíîñòè ∼G íà T deft ∼G t 0 = ∃ g : g(t) = t0 .GÊëàññû ýòîé ýêâèâàëåíòíîñòè íàçûâàþò îðáèòàìè.×èñëî îðáèò (êëàññîâ ýêâèâàëåíòíîñòè) C(G).Åñëè C(G) = 1 (ëþáîé ýëåìåíò T ìîæåò áûòü ïåðåâåä¼í âëþáîé), òî äåéñòâèå G : T íàçûâàþò òðàíçèòèâíûì.αÊëàññ ýêâèâàëåíòíîñòè, â êîòîðóþ ïîïàäàåò ýëåìåíò t áóäåìîáîçíà÷àòü Orb (t).14 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà15 / 76Äåéñòâèå ãðóïïû íà ìíîæåñòâåÔèêñàòîð è ñòàáèëèçàòîð. Ëåììà Á¼ðíñàéäàÁóäåì ðåøàòü óðàâíåíèå g(t) = t.Ïðè âûïîëíåíèè ýòîãî ðàâåíñòâà ìîæíî ôèêñèðîâàòü t èëè g .1Ôèêñèðóåì g , ò.å. íàõîäèì âñå ýëåìåíòû ìíîæåñòâà T ,êîòîðûå ïåðåñòàíîâêà g îñòàâëÿåò íà ìåñòå (ôèêñàòîð):def{ t ∈ T | g(t) = t } = Fix (g) ⊆ T .2Ôèêñèðóåì t, ò.å. íàõîäèì âñå ïåðåñòàíîâêè g , êîòîðûåîñòàâëÿþò äàííûé ýëåìåíò íåïîäâèæíûì (ñòàáèëèçàòîð):def{ g ∈ G | g(t) = t } = Stab (t) ⊆ G.Ñïðàâåäëèâû ðàâåíñòâà1 X 1 X Fix(g)=Stab(t)C(G) =;|G||G|g∈Gt∈Tïåðâîå íàçûâàåòñÿ ëåììîé Á¼ðíñàéäà (èëè Êîøè-Ôðîáåíèóñà).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà16 / 76Äåéñòâèå ãðóïïû íà ìíîæåñòâåÓ. Á¼ðíñàéäÓèëüÿì Á¼ðíñàéä(William Burnside, 18521927) àíãëèéñêèé ìàòåìàòèê-àëãåáðàèñò.¾Íàïèñàë ïåðâûé òðàêòàò î ãðóïïàõíà àíãëèéñêîì ÿçûêå è áûë ïåðâûì,êòî ðàçðàáîòàë òåîðèþ ãðóïï ññîâðåìåííîé àáñòðàêòíîé òî÷êè çðåíèÿ¿.Òàêæå çíàìåíèò ôîðìóëèðîâàíèåìïðîáëåìû Á¼ðíñàéäà (1902):Áóäåò ëè êîíå÷íîïîðîæä¼ííàÿ ãðóïïà, â êîòîðîé êàæäûéýëåìåíò èìååò êîí÷åíûé ïîðÿäîê, îáÿçàòåëüíî êîíå÷íîé?Îòâåò îòðèöàòåëüíûé (1992).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà17 / 76Äåéñòâèå ãðóïïû íà ìíîæåñòâåÑòàáèëèçàòîð åñòü ïîäãðóïïà ãðóïïû G12Fix (g) ôèêñàòîð ïåðåñòàíîâêè g ∈ G (ïîäìíîæåñòâî T );Stab (t) ñòàáèëèçàòîð ýëåìåíòà t ∈ T(ïîäìíîæåñòâî G).Ëåììà (î ñòàöèîíàðíîé ïîäãðóïïå ýëåìåíòà t)Stab (t) 6 G.ÄîêàçàòåëüñòâîÇàôèêñèðóåì t ∈ T è ðàññìîòðèì g, h ∈ Stab (t).
Òîãäàg(t) = h(t) = t è h−1 (t) = t. Ñëåäîâàòåëüíî,(g ◦ h−1 ) ∗ t = t ⇒ g ◦ h−1 ∈ Stab (t) . Stab (t) > 1, ïîñêîëüêó âñåãäà e ∈ Stab (t).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÝëåìåíò ìíîæåñòâà: äëèíà îðáèòû è ñòàáèëèçàòîðËåììàÄëèíà îðáèòû Orb (t) ðàâíà èíäåêñó Stab (t) â ãðóïïå G, ò.å. Orb (t) = G : Stab (t).ÏðèìåðÏóñòü V ìíîæåñòâî âåðøèí êóáà. Íàéòè ñòàáèëèçàòîðâåðøèíû v êóáà ïðè äåéñòâèè ãðóïïû O íà V .Ðåøåíèå: Stab (v) ∼= Z3 ãðóïïà âðàùåíèé íà 0◦ è ±120◦âîêðóã äèàãîíàëè êóáà, ïðîõîäÿùåé ÷åðåç äàííóþ âåðøèíó.Óòâåðæäåíèå (ñëåäñòâèå ëåììû)×èñëî ýëåìåíòîâ â ãðóïïå âðàùåíèÿ ïðàâèëüíîãîV · E0 , ãäå V ÷èñëî âåðøèí, àìíîãîãðàííèêàåñòü E0 ÷èñëî ð¼áåð, âûõîäÿùèõ èç îäíîé âåðøèíû.18 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà19 / 76Äåéñòâèå ãðóïïû íà ìíîæåñòâåÄåéñòâèå ãðóïïû íà ìíîæåñòâå: ïðèìåðÄåéñòâèå ãðóïïû V4 íà ìíîæåñòâå T = { t1 , . . . , t6 }◦eababeeababaaeabbbbabeaababbaeg∗teababt1t1t2t3t4t2t2t1t4t3t3t3t4t1t2t4t4t3t2t1t5t5t6t5t6t6t6t5t6t5ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÄåéñòâèå ãðóïïû íà ìíîæåñòâå: ïðèìåð...T ype(e) = h 6, 0, 0, 0, 0, 0 i ,T ype(a) = h 0, 3, 0, 0, 0, 0 i ,T ype(b) = h 2, 2, 0, 0, 0, 0 i ,T ype(ab) = h 0, 3, 0, 0, 0, 0 i .C(e) = 6 , C(a) = C(ab) = 3 , C(b) = 4 .Stab (t1 ) = Stab (t2 ) = Stab (t3 ) = Stab (t4 ) = e 6 V4 ,Stab (t5 ) = Stab (t6 ) = h e, b i 6 V4 .Fix (a) = Fix (ab) = ∅ , Fix (b) = { t5 , t6 } , Fix (e) = T .
Orb (t1 ) = 4 = 4 , Orb (t5 ) = 4 = 2 .121 X 6+2Fix (g) == 2,44g∈G1 X 4·1+2·2Stab (t) == 2.44t∈T20 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Ðàçäåëû I1Äåéñòâèå ãðóïïû íà ìíîæåñòâå2Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿêîìáèíàòîðíûõ çàäà÷3Ïðèìåíåíèå òåîðåìû Ïîéà äëÿ ðåøåíèÿêîìáèíàòîðíûõ çàäà÷4Çàäà÷è ñ ðåøåíèÿìè21 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Ïðèìåð ïðèìåíåíèÿ ëåììû Á¼ðíñàéäàÇàäà÷à ïðî ñëîâàÑîñòàâëÿþòñÿ ñëîâà äëèíû l > 2 èç àëôàâèòàA = { a1 , . .
. , am }.Ñëîâà ñ÷èòàþòñÿ ýêâèâàëåíòíûìè, åñëè îíè ïîëó÷àþòñÿ îäíîèç äðóãîãî ïåðåñòàíîâêîé êðàéíèõ áóêâ.Îïðåäåëèòü ÷èñëî S íåýêâèâàëåíòíûõ ñëîâ.Ðåøåíèå.T ìíîæåñòâî ñëîâ äëèíû l â àëôàâèòå A, N = |T | = ml .Íàäî ïðåäñòàâèòü ýêâèâàëåíòíîñòè êàê îðáèòû íåêîòîðîãîäåéñòâèÿ ïîäõîäÿùåé ãðóïïû G íà T .Î÷åâèäíî, g 2 = e è ïîýòîìó ïîäõîäèò G ∼= Z2 = { e, g }.Äåéñòâèå: g ïåðåñòàâëÿåò â ñëîâå êðàéíèå áóêâû.22 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Ïðèìåð ïðèìåíåíèÿ ëåììû Á¼ðíñàéäà...×èñëî S íåýêâèâàëåíòíûõ ñëîâ åñòü ÷èñëî êëàññîâýêâèâàëåíòíîñòè C(G) äåéñòâèÿ Z2 : T α Fix (e) = T = ml , Fix (g) = ml−2 · m = ml−1 .ml + ml−1ml−1 (m + 1)1 X Fix (g) ==.S = C(Z2 ) =222g∈GÄëÿ l = 3, m = 2 ⇒ S =4·32= 6 (èç âñåãî 8)Ïóñòü A = {a, b}.
Ïîêàçàíû ñëîâà è êëàññû.aaaaababaabbbaababbbabbb23 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà24 / 76Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Öèêëîâîé èíäåêñÑóùåñòâóåò óíèâåðñàëüíûé ñïîñîá âû÷èñëåíèÿ ÷èñëà C(G) êîëè÷åñòâà êëàññîâ ýêâèâàëåíòíîñòè (= îðáèò).Ñîïîñòàâèì êàæäîé ïåðåñòàíîâêå g ∈ G âåñ w(g) ïî ïðàâèëó:T ype(g) = hν1 , . .
. , νN i ⇒ w(g) = xν11 · . . . · xνNN .{z}|ìîíîìÎïðåäåëåíèåÑðåäíèé âåñ ïîäñòàíîâîê â ãðóïïå íàçûâàåòñÿöèêëîâûì èíäåêñîì äåéñòâèÿ G : T :α1 X1 X ν1P (G : T, x1 , . . . , xN ) =w(g) =x1 · . . . · xNνN .α|G||G|g∈Gg∈GÄëÿ ïðîäâèíóòûõ: ýòî ïðîèçâîäÿùèé ïîëèíîì ìíîãèõïåðåìåííûõ.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Öèêëîâîé èíäåêñ: îáîçíà÷åíèÿ è ñâîéñòâàÄðóãèå îáîçíà÷åíèÿ: PG (x1 , .
. . , xN ) è PG , P (G).?G∼= G 0 ⇒ PG = PG 0 äà, åñëè äåéñòâèÿ îïðåäåëåíûîäèíàêîâî (ñîãëàñîâàíî).?PG = PG 0 ⇒ G ∼= G 0 íåò, åñòü êîíòðïðèìåð.Êàê ïðèìåíÿòü ëåììó ¾íå-Á¼ðíñàéäà?¿Äëÿ ïðèìåíåíèÿ óíèâåðñàëüíîãî ñïîñîáà âû÷èñëåíèÿ C(G)íàäî ïðåäñòàâèòü ýêâèâàëåíòíûå ýëåìåíòû ìíîæåñòâà êàêêëàññû ýêâèâàëåíòíîñòè äåéñòâèÿ íåêîòîðîé ãðóïïû G íàýòîì ìíîæåñòâå.25 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷×èñëî íåýêâèâàëåíòíûõ ðàñêðàñîêÏóñòü çàäàíî äåéñòâèå G : T ãðóïïû G íà ìíîæåñòâå T .αÏðèïèøåì êàæäîìó ýëåìåíòó T îäíî èç r çíà÷åíèé(íåôîðìàëüíî: ïîêðàñèì â îäèí èç r öâåòîâ).Âñåãî, î÷åâèäíî, èìååòñÿ rN ðàñêðàñîê.Íå áóäåì ðàçëè÷àòü ðàñêðàñêè, åñëè ïðè ïðåîáðàçîâàíèèg : t → t0 t0 ðàñêðàøåí òàêæå êàê è t. Íàïðèìåð, ïîâîðîòíà 90◦ ••••••••íå äà¼ò íîâîãî ðàñêðàøèâàíèÿ âåðøèí êâàäðàòà.Âîïðîñ: Ñêîëüêî ñóùåñòâóåò íåýêâèâàëåíòíûõ ðàñêðàñîê =êëàññîâ ýêâèâàëåíòíîñòè C(G)?26 / 76ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü III: Òåîðèÿ ïåðå÷èñëåíèÿ Ïîéà27 / 76Ïðèìåíåíèå ëåììû Á¼ðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Âû÷èñëåíèå C(G) ÷åðåç öèêëîâîé èíäåêñÊàæäûé êëàññ ýêâèâàëåíòíîñòè ýòî g -öèêë; èõC(g) = ν1 + .
. . + νN øòóê.Êàæäàÿ ïåðåñòàíîâêà g ∈ G ñ òèïîì h ν1 , . . . , νN i áóäåòèìåòü rν1 íåïîäâèæíûõ òî÷åê.Ñëåäîâàòåëüíî, ïî ëåììå Á¼ðñàéäà, ÷èñëî ïîëó÷åííûõ êëàññîâýêâèâàëåíòíîñòè, ò.å. íåýêâèâàëåíòíûõ ðàñêðàñîêÒåîðåìàC(G : T ) = P (G : T, x1 , . . . , xN )ααx1 =...=xN =r= PG (r, . . . , r).Íàïðèìåð, PG (1, .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
