Краткие лекции по алгебре (1078545), страница 4
Текст из файла (страница 4)
Îïðåäåëèì äåéñòâèå ïîäñòàíîâêè σ íà ïðîèçâîëüíîå ðàñ-Sêðàøèâàíèå ïî ôîðìóëå (5.2):(σf )(i) = f (σ −1 (i)).19Âûâåäåì ôîðìóëó äëÿ ÷èñëà N (σ) ðàñêðàøèâàíèé, îñòàþùèõñÿíà ìåñòå ïðè äåéñòâèè σ. Ðàçëîæèì ïîäñòàíîâêó σ â ïðîèçâåäåíèå íåçàâèñèìûõ öèêëîâ: σ = σ1 ... σk , ïðè÷åì ó÷èòûâàþòñÿè öèêëû äëèíû 1. Êàæäîìó öèêëó (i1, ..., il ) ñîîòâåòñòâóåò< σ >-îðáèòà {i1 , ..., il }, è ïðè ýòîì ñîâîêóïíîñòü âñåõ < σ >îðáèò ÿâëÿåòñÿ ðàçáèåíèåì ìíîæåñòâà M . Ïóñòü f íåêîòîðîåðàñêðàøèâàíèå ôèãóðû Ω, êîòîðîå îñòàåòñÿ íà ìåñòå ïðè äåéñòâèè íà íåãî ïîäñòàíîâêè σ. Êàê ëåãêî ïîíÿòü, äëÿ ëþáîãî öèêëàσj = (i1 , ..., il ) èìååì f (i1 ) = f (i2 ) = ...
= f (il ). Ïîñêîëüêó < σ >îðáèòû íå ïåðåñåêàþòñÿ, îíè ìîãóò áûòü îêðàøåíû íåçàâèñèìîäðóã îò äðóãà, à òîãäà N (σ) = |R|k . ÏÐÈÌÅÐ 6.2. Âû÷èñëèì, ñêîëüêèìè ñïîñîáàìè ìîæíî ðàñêðàñèòü âåðøèíû ïðàâèëüíîãî òåòðàýäðà â q ðàçëè÷íûõ öâåòîâ.Ãðóïïà G äâèæåíèé ïðàâèëüíîãî òåòðàýäðà íàéäåíà â ïðèìåðå4.6.
Ýòà ãðóïïà äåéñòâóåò íà ìíîæåñòâå {1, 2, 3, 4} âåðøèí òåòðàýäðà è ñîñòîèò â òî÷íîñòè èç ÷åòíûõ ïîäñòàíîâîê. Îíà ñîäåðæèò ýëåìåíòû e = (1)(2)(3)(4), 8 ýëåìåíòîâ âèäà σ = (1)(234) è 3ýëåìåíòà âèäà τ = (12)(34). Ñîãëàñíî äîêàçàííîìó âûøå, èìååìN (e) = q 4 , N (σ) = q 2 , N (τ ) = q 2 . Òåïåðü ìîæíî ïðèìåíèòüëåììó Áåðíñàéäà, è ìû ïîëó÷àåì ôîðìóëó äëÿ ÷èñëà N ðàñêðàøèâàíèé:1 4q2 222N = (q + 8q + 3q ) = (q + 11).1212(6.2)Ðåøåííóþ çàäà÷ó ìîæíî òðàêòîâàòü òàêèì îáðàçîì: èìåþòñÿàòîìû q ðàçëè÷íûõ ýëåìåíòîâ. Ìîëåêóëà âåùåñòâà ñîñòîèò èç÷åòûðåõ àòîìîâ, ðàñïîëîæåííûõ â âåðøèíàõ ïðàâèëüíîãî òåòðàýäðà. Ñêîëüêî ìîæåò ñóùåñòâîâàòü ðàçëè÷íûõ òèïîâ ìîëåêóë,ñîñòàâëåííûõ èç àòîìîâ äàííûõ ýëåìåíòîâ? Îòâåò äàåòñÿ ôîðìóëîé (6.2).
7. Òåîðåìà ÏîéàÏóñòü M êîíå÷íîå ìíîæåñòâî,|M | = n è G êîíå÷íàÿ ãðóïïà, äåéñòâóþùàÿ íà M . Ýòó ãðóïïóìîæíî îòîæäåñòâèòü ñ íåêîòîðîé ïîäãðóïïîé â Sn.Äëÿ ëþáîãî ýëåìåíòà g ∈ G îáîçíà÷èì ÷åðåç jk (g) ÷èñëîöèêëîâ äëèíû k â ðàçëîæåíèè ïîäñòàíîâêè g â ïðîèçâåäåíèåíåçàâèñèìûõ öèêëîâ. Êàæäîìó ýëåìåíòó g ∈ Sn ïîñòàâèì âñîîòâåòñòâèå âåñj (g)j (g)Öèêëîâîé èíäåêñ ãðóïïû.wG (g) = t1120... tnn .Ýòî ìíîãî÷ëåí ñ öåëûìè êîýôôèöèåíòàìè îò t1, ..., tn. Öèêëîâûìèíäåêñîì ãðóïïû G, äåéñòâóþùåé íà M , íàçûâàåòñÿ ìíîãî÷ëåíP (G, M, t1 , ..., tn ), îïðåäåëÿåìûé ôîðìóëîéP (M, G, t1 , ..., tn ) =1 ∑1 ∑ j1 (g)wG (g) =t1... tjnn (g) .|G| g∈G|G| g∈GÏÐÈÌÅÐ 7.1. Ïóñòü G ãðóïïà äâèæåíèé ïðàâèëüíîé ÷åòûðåõóãîëüíîé ïèðàìèäû (ñì. ïðèìåð 4.3).
Êàê ìû çíàåì, G ∼=C4 öèêëè÷åñêàÿ ãðóïïà ïîðÿäêà 4, ïîðîæäåííàÿ ïîâîðîòîì σíà óãîë π/2. Ïðè îòîæäåñòâëåíèè G ñ ïîäãðóïïîé â S5 èìååìσ = (1)(2345), σ 2 = (1)(24)(35), σ 3 = (1)(2543). Öèêëîâîé èíäåêñãðóïïû, äåéñòâóþùåé íà ìíîæåñòâå M = {1, 2, 3, 4, 5} âåðøèíïèðàìèäû, ðàâåíP (M, G, t1 , t2 , t3 , t4 , t5 ) =1 ∑wG (g) =|G| g∈G)1(wG (e) + wG (σ) + wG (σ 2 ) + wG (σ 3 ) =4) 1( 5)1( 5t1 + t1 t4 + t1 t22 + t1 t4 =t1 + t1 t22 + 2t1 t4 . =44=Ìíîæåñòâî èññëåäóåìûõ îáúåêòîâ â êîìáèíàòîðèêå ÷àñòî íàçûâàþò çàïàñîì.Ïóñòü Z çàïàñ.
Ïîñòàâèì â ñîîòâåòñòâèå êàæäîìó z ∈ Zìíîãî÷ëåí w(z) îò íåñêîëüêèõ ïåðåìåííûõ ñ öåëûìè êîýôôèöèåíòàìè. Áóäåì ìíîãî÷ëåí w(z) íàçûâàòü âåñîì ýëåìåíòà a. Ñóììà âåñîâ âñåõ ýëåìåíòîâ çàïàñà íàçûâàåòñÿ ïðîèçâîäÿùåé ôóíêöèåé çàïàñà Z è îáîçíà÷àåòñÿ ÷åðåç W (Z), ò. å.Çàïàñ. Ïðîèçâîäÿùàÿ ôóíêöèÿ çàïàñà.W (Z) =∑w(z).z∈ZÏóñòü R åùå îäíî êîíå÷íîå ìíîæåñòâî. Íà ìíîæåñòâå RMôóíêöèé f : M → R äåéñòâóåò ãðóïïà G êàê îáúÿñíÿëîñü âïðèìåðå 5.3. Ðàññìàòðèâàÿ M êàê ìíîæåñòâî ýëåìåíòîâ íåêîòîðîé ôèãóðû, à R êàê ìíîæåñòâî êðàñîê, áóäåì òàêèå ôóíêöèèíàçûâàòü ðàñêðàøèâàíèÿìè. Äâà ðàñêðàøèâàíèÿ áóäåì íàçûâàòü ýêâèâàëåíòíûìè, åñëè îíè ýêâèâàëåíòíû îòíîñèòåëüíî äåéñòâèÿ G, ò. å. ëåæàò â îäíîé îðáèòå ýòîé ãðóïïû, äåéñòâóþùåé21íà RM .
Òîãäà [RM ] ìíîæåñòâî êëàññîâ ýêâèâàëåíòíîñòè ðàñêðàøèâàíèé.Ïóñòü êàæäîìó ýëåìåíòó y ∈ R ïðèäàí íåêîòîðûé âåñ wR(y) ìíîãî÷ëåí ñ öåëûìè êîýôôèöèåíòàìè îò ôèêñèðîâàííîãî ÷èñëà ïåðåìåííûõ. Òîãäà âåñ ôóíêöèè f ∈ RM åñòü, ïî îïðåäåëåíèþ,∏w(f ) =wR (f (x)).x∈MÅñëè f1 ∼ f2, òî, î÷åâèäíî, w(f1) = w(f2), ïîýòîìó ìîæíîîïðåäåëèòü âåñ êëàññà ýêâèâàëåíòíîñòè w(F ), ãäå F ∈ [RM ], êàêâåñ ëþáîãî ýëåìåíòà f ∈ F .ÏÐÈÌÅÐ 7.2. Ïóñòü R = {r, g} ìíîæåñòâî öâåòîâ, M ={1, 2, 3, 4, 5} ìíîæåñòâî âåðøèí ïðàâèëüíîé ÷åòûðåõóãîëüíîéïèðàìèäû:23 1 54Íà M äåéñòâóåò ãðóïïà G ∼= 4 (ñì. ïðèìåð 5.1).
Ðàñêðàøèâàíèÿ 1) è 2) G-ýêâèâàëåíòíû, ðàñêðàøèâàíèå 3) èì íå ýêâèâàëåíòíî.rrgrrg1) r 2) r 3) r gggrgrCÏîëîæèì wR(r) = a, wR(g) = b. Òîãäà äëÿ âåñà w(f ) ëþáîãî èçðàñêðàøèâàíèé 1), 2), 3) è äëÿ âåñà w(F ) ëþáîãî èç ñîòâåòñòâóþùèõ êëàññîâ ýêâèâàëåíòíîñòè áóäåì èìåòüw(F ) = w(f ) = a3 b2 .Òåïåðü ìûìîæåì ñôîðìóëèðîâàòü îñíîâíîé ðåçóëüòàò.ÒÅÎÐÅÌÀ 7.1 (Ïîéà). Ïðîçâîäÿùàÿ ôóíêöèÿ çàïàñà êëàññîâýêâèâàëåíòíîñòè ðàñêðàøèâàíèé óäîâëåòâîðÿåò ðàâåíñòâóÔîðìóëèðîâêà òåîðåìû Ïîéà.∑F(w(F ) = PG, M,∑y∈RwR (y),∑y∈RÏðèìåð.(wR (y))2 , ...,∑)(wR (y))n ,y∈Rãäå P (G, M, t1, ..., tn) öèêëîâîé èíäåêñ ãðóïïû G, äåéñòâóþùåéíà M .22Äîêàçûâàòü ìû ýòó òåîðåìó íå áóäåì, ðàññìîòðèì òîëüêîïðèìåð åå ïðèìåíåíèÿ.ÏÐÈÌÅÐ 7.3.
Îáðàòèìñÿ ê ïðèìåðàì 7.1 è 7.2. Îïðåäåëèìïðîèçâîäÿùóþ ôóíêöèþ çàïàñà êëàññîâ ýêâèâàëåíòíîñòè ðàñêðàøèâàíèé â äâà öâåòà. Íà îñíîâàíèè òåîðåìû èìååì∑w(F ) = P (M, G, a + b, a2 + b2 , a3 + b3 , a4 + b4 , a5 + b5 ) =F=)1((a + b)5 + (a + b)(a2 + b2 )2 + 2(a + b)(a4 + b4 ) =4= a5 + 2a4 b + 3a3 b2 + 3a2 b3 + 2ab4 + b5 .Òàêèì îáðàçîì, ÷èñëî ðàñêðàøèâàíèé, ïðè êîòîðûõ, íàïðèìåð,òðè ýëåìåíòà îêðàøåíû â êðàñíûé öâåò, è äâà â çåëåíûé,ðàâíî êîýôôèöèåíòó ïðè a3b2, ò.
å. 3. Îáøåå æå ÷èñëî ðàñêðàøèâàíèé ðàâíî ñóììå âñåõ êîýôôèöèåíòîâ, ò. å. 12. 23ÄÎÌÀØÍÅÅ ÇÀÄÀÍÈÅÄàí ìíîãîãðàííèê Ω, ïðåäñòàâëÿþùèé ñîáîé ëèáî ïðàâèëüíóþ n-óãîëüíóþ ïðèçìó, ëèáî ïðàâèëüíóþ n-óãîëüíóþ ïèðàìèäó,ëèáî ïðàâèëüíóþ n-óãîëüíóþ óñå÷åííóþ ïèðàìèäó, ëèáî n-óãîëüíûé äèýäð (ò. å. ôèãóðó, ñîñòîÿùóþ èç äâóõ îäèíàêîâûõ ïðàâèëüíûõ n-óãîëüíûõ ïèðàìèä ñ îáùèì îñíîâàíèåì, ëèáî òàêîéæå óñå÷åííûé äèýäð (ò. å. ôèãóðó, ñîñòîÿùóþ èç äâóõ îäèíàêîâûõ ïðàâèëüíûõ óñå÷åííûõ ïèðàìèä ñ îáùèì áîëüøèì îñíîâàíèåì).1) Íàéòè ãðóïïó G äâèæåíèé ìíîãîãðàííèêà Ω.2) Íàéòè öèêëîâîé èíäåêñ ãðóïïû G, äåéñòâóþùåé íà ìíîæåñòâå M âåðøèí (âàðèàíòû 1 10), ãðàíåé (âàðèàíòû 11 20), ðåáåð (âàðèàíòû 21 30) ìíîãîãðàííèêà Ω.3) Íàéòè ÷èñëî ñïîñîáîâ ðàñêðàøèâàíèÿ ýëåìåíòîâ ìíîæåñòâàM â òðè öâåòà.4) Íàéòè ïðîèçâîäÿùóþ ôóíêöèþ çàïàñà êëàññîâ ýêâèâàëåíòíîñòè ðàñêðàøèâàíèé, åñëè èñïîëüçóþòñÿ äâà öâåòà.ΩnΩn1, 11, 21ïðèçìà3 6, 16, 26äèýäð52, 12, 22 óñå÷.
äèýäð 3 7, 17, 27 ïðèçìà (*) 43, 13, 23äèýäð3 8, 18, 28ïðèçìà54, 14, 24 óñå÷. ïèðàìèäà 4 9, 19, 29 óñå÷. ïèðàìèäà 55, 15, 25 ïèðàìèäà 6 10, 20, 30 äèýäð (**) 4* îòëè÷íàÿ îò êóáà, ** îòëè÷íûé îò ïðàâèëüíîãî îêòàýäðà24ËÈÒÅÐÀÒÓÐÀ[1] ÊÎÑÒÐÈÊÈÍ À.È. Îñíîâû àëãåáðû. Ì.: Èçä-âî ÌÖÍÌÎ,2009.[2] ÊÓÐÎØ À.Ã. Êóðñ âûñøåé àëãåáðû. Ì.: Íàóêà, 1965.[3] ÍÅÔÅÄΠÂ.Í., ÎÑÈÏÎÂÀ Â.À. Êóðñ äèñêðåòíîé ìàòåìàòèêè. Ì.: Èçä-âî ÌÀÈ, 1992.25ÎÃËÀÂËÅÍÈÅÏðåäèñëîâèå ............................................................................ 3Ìíîæåñòâà è îòîáðàæåíèÿ .....................................................
3Ïîíÿòèå ãðóïïû .................................................................... 10Òåîðåìà Ëàãðàíæà ................................................................ 13Ãðóïïû äâèæåíèé ................................................................. 14Äåéñòâèå ãðóïïû íà ìíîæåñòâå ...........................................
16Ëåììà Áåðíñàéäà .................................................................. 18Òåîðåìà Ïîéà ........................................................................ 20Äîìàøíåå çàäàíèå ................................................................ 24Ëèòåðàòóðà ............................................................................ 2526.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
