Лекции по прикладной алгебре. v1.0 (1127110), страница 11
Текст из файла (страница 11)
Ïîêàçàíû ñëîâ è êëàññû.aaaaababaabb----baababbbabbb----Ïðèêëàäíàÿ àëãåáðà160 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷àÏîêàçàòü, ÷òî åñëè ýëåìåíòû g è h ãðóïïû G ñîïðÿæåíû, òîStab (g) = Stab (h).Ðåøåíèågf = f h ⇒ Stab (gf ) = Stab (g) ∩ Stab (f ) = Stab (f h) == Stab (f ) ∩ Stab (h) ⇒ Stab (g) = Stab (h).Ïðèêëàäíàÿ àëãåáðà161 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷àÃðóïïà âðàùåíèé êóáà ãðóïïó ïåðåñòàíîâîê íà ìíîæåñòâå åãîâåðøèí. Îïðåäåëèòü òèïû âñåõ ïåðåñòàíîâîê ýòîé ãðóïïû.ÐåøåíèåO = h t, f, r i , t4 = f 2 = r3 = e, ãäåt âðàùåíèå íà 90◦ âîêðóã îñè,ïðîõîäÿùåé ÷åðåç äâå ïðîòèâîïîëîæíûåãðàíè (22);f âðàùåíèå íà 180◦ âîêðóã îñè,ïðîõîäÿùåé ÷åðåç äâà ïðîòèâîïîëîæíûåðåáðà (◦◦);r âðàùåíèå íà 120◦ âîêðóã îñè,ïðîõîäÿùåé ÷åðåç äâå ïðîòèâîïîëîæíûåâåðøèíû (MM).Ïðèêëàäíàÿ àëãåáðà162 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Èìååì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.Ïðèêëàäíàÿ àëãåáðà163 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Öèêëîâîé èíäåêñÑóùåñòâóåòóíèâåðñàëüíûéñïîñîá âû÷èñëåíèÿ ÷èñëà1 P Fix (g) = C(G) êëàññîâ ýêâèâàëåíòíîñòè(îðáèò).|G|g∈GÑîïîñòàâèì êàæäîé ïåðåñòàíîâêå g ∈ G âåñ w(g) ïî ïðàâèëó:T ype(g) = hν1 , .
. . , νN i ⇒ w(g) = xν11 · . . . · xνNN .xν11 · . . . · xνNN ìîíîì.ÎïðåäåëåíèåÑðåäíèé âåñ ïîäñòàíîâîê â ãðóïïå íàçûâàåòñÿ öèêëîâûìèíäåêñîì äåéñòâèÿ G : T :α1 X1 X ν1P (G : T, x1 , . . . , xN ) =w(g) =x1 · . . . · xNνN .α|G||G|g∈Gg∈GÄëÿ ïðîäâèíóòûõ: ýòî (êîíå÷íàÿ) ïðîèçâîäÿùàÿ ôóíêöèÿ.Ïðèêëàäíàÿ àëãåáðàÒåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Öèêëîâîé èíäåêñ: îáîçíà÷åíèÿ è ñâîéñòîÄðóãèå îáîçíà÷åíèÿ: PG (x1 , . . . , xN ) è PG , P (G).G∼= G 0 ⇒ PG = PG 0 äà, åñëè äåéñòâèÿ îïðåäåëåíûîäèíàêîâî (ñîãëàñîâàíî)PG = PG 0 6⇒ G ∼= G 0 íåò, åñòü êîíòðïðèìåðÄëÿ ïðèìåíåíèÿ óíèâåðñàëüíîãî ñïîñîáà âû÷èñëåíèÿ C(G)íàäî ïðåäñòàâèòü ýêâèâàëåíòíûå ýëåìåíòû êàê êëàññûýêâèâàëåíòíîñòè, ñîõðàíÿþùèå íåêîòîðûå õàðàêòåðèñòèêèýëåìåíòîâ ïðè ïåðåñòàíîâêàõ.164 / 225Ïðèêëàäíàÿ àëãåáðà165 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷×èñëî íåýêâèâàëåíòíûõ ðàñêðàñîêÏóñòü çàäàíî äåéñòâèåG α: TãðóïïûG íà ìíîæåñòâå T .Ïðèïèøåì êàæäîìó ýëåìåíòó T îäíî èç r çíà÷åíèé ïîêðàñèìâ îäèí èç r öâåòîâ.
Âñåãî âîçìîæíî rN ðàçëè÷íûõ ðàñêðàñîê.Íå áóäåì ðàçëè÷àòü ðàñêðàñêè, åñëè ïðè ïðåîáðàçîâàíèèg : t → t0 ýëåìåíò ñîõðàíÿåò öâåò (t0 ðàñêðàøåí òàêæå êàêt0 ). Ò.å. êàæäûé g -öèêë ðàñêðàøåí îäíèì ñïîñîáîì.••••••••Ðèñ. 1.Ïåðåñòàíîâêà g ïîâîðîò íà +90◦Âîïðîñ: Ñêîëüêî ñóùåñòâóåò íåýêâèâàëåíòíûõ ðàñêðàñîê êëàññîâ ýêâèâàëåíòíîñòè C(G)?Ïðèêëàäíàÿ àëãåáðà166 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Âû÷èñëåíèå C(G) ÷åðåç öèêëîâîé èíäåêñÊàæäûé êëàññ ýêâèâàëåíòíîñòè ýòî g -öèêë; èõ C(g) = ν1 +. . .
+ νN øòóê.Êàæäàÿ ïåðåñòàíîâêà g ∈ G ñ òèïîì h ν1 , . . . , νN i áóäåòèìåòü rC(g) íåïîäâèæíûõ òî÷åê.Ñëåäîâàòåëüíî, ïî òåîðåìå Áåðíàéñà, ÷èñëî ïîëó÷åííûõêëàññîâ ýêâèâàëåíòíîñòè, ò.å. íåýêâèâàëåíòíûõ ðàñêðàñîê(ïðèïèñûâàíèé) åñòüÒåîðåìàC(G : T ) = P (G : T, r, . . . , r).αÍàïðèìåð, PG (1, . . . , 1) = 1.αÏðèêëàäíàÿ àëãåáðà167 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷ÏðèìåðÇàäà÷à (ïðî ñëîâà)Ñîñòàâëÿþòñÿ ñëîâà äëèíû l > 2 èç àëôàâèòà A ={ a1 , .
. . , am }. Ñëîâà ñ÷èòàþòñÿ ýêâèâàëåíòíûìè, åñëè îíèïîëó÷àþòñÿ îäíî èç äðóãîãî òðàíñïîçèöèåé êðàéíèõ áóêâ.Îïðåäåëèòü ÷èñëî S íåýêâèâàëåíòíûõ ñëîâ.Áûëî ðåøåíèå: S =ml +ml−1.2l−2z }| {Äðóãîå ðåøåíèå: G = { e, g } ∼= Z2 ; T : . . . .|{z}lÝëåìåíò ãðóïïû gegT ype(g)h l, 0, . . . , 0 ih l − 2, 1, 0, . . . , 0 iÖèêëîâîé èíäåêñ: P (x1 , . . .
, xl ) =P (x1 , . . . , xl )|x1 =...=xl =m = S .w(g)xl11xl−21 x21xl1 +xl−21 x2.2#ìîíîìîâ11Ïðèêëàäíàÿ àëãåáðàÒåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à îá îæåðåëüÿõ îäíà èç êëàññè÷åñêèõ êîìáèíàòîðíûõ çàäà÷.Îæåðåëüå îêðóæíîñòü, íà êîòîðîé íà ðàâíûõ ðàññòîÿíèÿõ ïîäóãå ðàñïîëàãàþòñÿ ¾áóñèíû¿ (áóñèíû ðàñïîëàãàþòñÿ ââåðøèíàõ ïðàâèëüíîãî ìíîãîóãîëüíèêà).Çàäà÷à (îá îæåðåëüÿõ)Ñêîëüêî ðàçëè÷íûõ îæåðåëèé ìîæíî ñîñòàâèòü èç n áóñèí röâåòîâ?Âàðèàíòû. Îæåðåëüÿ ðàâíû åñëè è òîëüêî åñëèîäíî ïîëó÷àåòñÿ èç äðóãîãî12ïîâîðîòîì (áóñèíû ïëîñêèå,îêðàøåíû ñ îäíîé ñòîðîíû);ïîâîðîòîì è îñåâîé ñèììåòðèåé(áóñèíû êðóãëûå);168 / 225Ïðèêëàäíàÿ àëãåáðà169 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à îá îæåðåëüÿõ: N = 5, r = 3Çàäà÷àÑêîëüêî ðàçíûõ îæåðåëèé ìîæíî ñîñòàâèòü èç 5 áóñèí 3 öâåòîâ?T âåðøèíû ïðàâèëüíîãî ïÿòèãîëüíèêà.
#Col(3) =?1Îæåðåëüÿ îäèíàêîâû, åñëè îäíî ïîëó÷àåòñÿ èç äðóãîãî ïîâîðîòîì.ÐåøåíèåG ãðóïïà âðàùåíèÿ ïðàâèëüíîãî ïÿòèãîëüíèêà: G ∼= Z5t5 = e, n = 5.Ýëåìåíò ãðóïïû gT ype(g)w(g) # ìîíîìîâeh 5, 0, 0, 0, 0 i x511234t, t , t , th 0, 0, 0, 0, 1 i x54Öèêëîâîé èíäåêñ: P (x1 , x2 , x3 , x4 , x5 ) = 15 [x51 + 4x5 ].35 + 4 · 3#Col(3) = P (3, . .
. , 3) == 51.5= hti,Ïðèêëàäíàÿ àëãåáðàÒåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à Îëèìïèàäû ¾Ïîêîðè Âîðîáü¼âû ãîðû 2009¿Äëÿ 50 äåòåé äåòñêîãî ñàäà çàêóïëåíû 50 îäèíàêîâûõ òàðåëîê.Ïî êðàþ êàæäîé òàðåëêè ðàâíîìåðíî ðàñïîëîæåíî 5 áåëûõêðóæî÷êîâ. Âîñïèòàòåëè õîòÿò ïåðåêðàñèòü êàêèå-ëèáî èç ýòèõêðóæî÷êîâ â äðóãîé öâåò òàê, ÷òîáû âñå òàðåëêè ñòàëèðàçëè÷íûìè. Êàêîå íàèìåíüøåå ÷èñëî äîïîëíèòåëüíûõ öâåòîâïîòðåáóåòñÿ èì äëÿ ýòîãî?Ðåøåíèå (Êàê äîëæíû áûëè ðåøàòü äåòè)Ïóñòü òðåáóåòñÿ r öâåòîâ.
Îòáðîñèì r âàðèàíòîâ ðàñêðàñêè âîäèí öâåò. ×èñëî îñòàëüíûõ âàðèàíòîâ áåç ó÷¼òà âîçìîæíîñòè5ïîâîðîòà òàðåëêè r5 − r; ñ ó÷¼òîì ïîâîðîòà r 5−r (êàæäûé55âàðèàíò ïîâòîðÿòñÿ 5 ðàç). Èòîãî #Col(r) = r 5−r +r = r +4r5 ;Ïðè 2-õ äîïîëíèòåëüíûõ öâåòàõ #Col(3) = 51.170 / 225Ïðèêëàäíàÿ àëãåáðà171 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à îá îæåðåëüÿõ: N = 5, r = 3, 2-é âàðèàíò2Îæåðåëüÿ îäèíàêîâû, åñëè îäíî ïîëó÷àåòñÿ èç äðóãîãîïîâîðîòîì èëè ïåðåâîðîòîì.ÐåøåíèåG ãðóïïà äèýäðà: 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 iÖèêëîâîé èíäåêñ: P =110w(g)x51x5x1 x22# ìîíîìîâ14510[x51 + 4x5 + 5x1 x22 ].#Col(3) = P (x1 , . . . , x5 )|x1 =...=x5 =3 =35 + 4 · 3 + 5 · 33= 39.10Ïðèêëàäíàÿ àëãåáðà172 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ðàñêðàñêå êóáàÇàäà÷à (ðàñêðàñêà êóáà â äâà öâåòà)Ãðàíè êóáà ðàñêðàøèâàþò â äâà öâåòà. Ñêîëüêî ñóùåñòâóåòðàçëè÷íî îêðàøåííûõ êóáîâ?ÐåøåíèåG = O = h t, f, r i, t4 = f 2 = r3 = e, |O| = 24.t âðàùåíèå íà 90◦ âîêðóã îñè,ïðîõîäÿùåé ÷åðåç äâå ïðîòèâîïîëîæíûåãðàíè (22, 3 îñè);f âðàùåíèå íà 180◦ âîêðóã îñè,ïðîõîäÿùåé ÷åðåç äâà ïðîòèâîïîëîæíûåðåáðà (◦◦, 6 îñåé);r âðàùåíèå íà 120◦ âîêðóã îñè,ïðîõîäÿùåé ÷åðåç äâå ïðîòèâîïîëîæíûåâåðøèíû (MM, 4 îñè).Ïðèêëàäíàÿ àëãåáðàÒåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à î ðàñêðàñêå êóáà â äâà öâåòà...T ìíîæåñòâî ãðàíåé êóáà, N = 6.Ýëåìåíò ãðóïïû gT ype(g)w(g) # ìîíîìîâeh 6, 0, 0, 0, 0, 0 ix6113h 2, 0, 0, 1, 0, 0 i x21 x43·2=6t, tt2h 2, 2, 0, 0, 0, 0 i x21 x2233h 0, 3, 0, 0, 0, 0 ix26fr, r2h 0, 0, 2, 0, 0, 0 ix234·2=8Âñåãî241 6P =· x1 + 6x21 x4 + 3x21 x22 + 6x32 + 8x23 .2426 + 12 · 23 + 3 · 24 + 8 · 22#Col(2) == 10.24173 / 225Ïðèêëàäíàÿ àëãåáðà174 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à (Ïåðå÷èñëåíèå ãðàôîâ)Ñêîëüêî èìååòñÿ îðèåíòèðîâàííûõ è íåîðèåíòèðîâàííûõíåïîìå÷åííûõ ãðàôîâ (áåç ïåòåëü è êðàòíûõ ð¼áåð) ñ òðåìÿâåðøèíàìè?ÐåøåíèåT ñòîðîíû òðåóãîëüíèêà, N = 3.G∼= S3 âñå ïåðåñòàíîâêè òð¼õ âåðøèí,n = 3! = 6.G : T äåéñòâèå ïåðåñòàíîâîêαâåðøèí íà ñòîðîíû.Ãðàôû íåîðèåíòèðîâàííûå r = 2 ïîìåòêè ¾åñòü ðåáðî/íåò ðåáðà¿îðèåíòèðîâàííûå r = 3 ïîìåòêè ¾íå ðåáðà/îðèåíòàöèÿ ðåáðà¿S3 = { e, 2 ∗ (ABC), 3 ∗ ((A)(BC)) }.Ïðèêëàäíàÿ àëãåáðà175 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷S3 = { e, 2 ∗ (ABC), 3 ∗ ((A)(BC)) }.| {z }| {z }g1Ýëåìåíò ãðóïïû ge = (a)(b)(c)g1 = (abc)g2 = (a)(bc)g2 = (a)(bc)T ype(g)h 3, 0, 0 ih 0, 0, 1 ih 1, 1, 0 ih 0, 0, 1 ig2w(g)x31x13x11 x12x13# ìîíîìîâ1233a ðåáðî a ñìåíèëî íàïðàâëåíèå.
Íî T ype((a)(bc))T ype(āb̄c̄) = T ype(abc), ïîýòîìó P = 61 · x31 + 5x3 .Íåîðèåíòèðîâàííûå P (x1 , x2 , x3 ) = 61 x31 + x13 + x11 x12 ,P (2, 2, 2) = 4.Îðèåíòèðîâàííûå P (x1 , x2 , x3 ) = 61 x31 + 5x3 ,P (2, 2, 2) = 7.=Ïðèêëàäíàÿ àëãåáðà176 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Ïåðå÷èñëèì îðèåíòèðîâàííûå: ïóñòîé ãðàô è ãðàôû◦◦[[]◦◦◦u[[]◦[[]w◦[[]◦◦[[]◦ u◦[[]◦ u◦◦◦◦◦ âñåãî 7 ãðàôîâ íåîðèåíòèðîâàííûõ 4.◦Ïðèêëàäíàÿ àëãåáðà177 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Öèêëîâûå èíäåêñû ñàìîäåéñòâèÿ èäåéñòâèÿ O íà ýëåìåíòû êóáàP (Sn ) =XN(j1 ,...,jn )∈ n01j1 +j2 +...+njnxj11 xj22 .
. . xjnn,(1j1 j1 !)(2j2 j2 !) . . . (njn jn !)1Xn/dϕ(d)xd , ϕ ôóíêöèÿ Ýéëåðà,nd|n((n−1)/21,12x1 x2 åñëè n íå÷¼òíî,P (Dn ) = P (Zn ) +n/2(n−2)/2122+ x1 x2, åñëè n ÷¼òíî,4 x2P (Zn ) =1x81 + 9x42 + 6x24 + 6x24 + 8x21 x23 ,241P (O : E) =x12+ 3x62 + 8x43 + 6x24 + 8x21 x52 + 6x34 ,1α241P (O : F ) =x61 + 3x21 x22 + 6x21 x4 + 6x32 + 8x23 .α24P (O : V ) =αÏðèêëàäíàÿ àëãåáðà178 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Òåîðåìà ÏîéàÁûëî: ìíîæåñòâî T , |T | = N , ãðóïïàäåéñòâèå G : T .G, |G| = n èαÄîáàâèì: ìíîæåñòâî R = {c1 , .
. . , cr } ìåòîê (¾êðàñîê¿),|R| = r è ñîâîêóïíîñòü ôóíêöèé F = RT ïðèïèñûâàíèÿìåòîê (ðàñêðàøèâàíèé).G, äåéñòâóÿ íàT , äåéñòâóåò è íà RT : ◦ : RT × G = RT .Äàäèì âåñ ýëåìåíòàì R : w(ci ) = yi , i = 1, r.Òåîðåìà (Ðåäôèëäà-Ïîéà)Öèêëîâîé èíäåêñ äåéñòâèÿ ãðóïïûG íàRT åñòüW (F ) = P (G : RT ) = P (G : T, x1 , . . . , xN )|xk =yk +...+yrk =1αα=1 |G| XN(i1 ,...,iN )∈ N0 =Ni1 +...+iN =NiN ui1 ,...,iN y1i1 . . . yN.Ïðèêëàäíàÿ àëãåáðà179 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷ÑëåäñòâèåÅñëè âñå âåñà âûáðàíû îäèíàêîâûìè (y1 = .
. . yr = 1), òî x1 =. . . xN = r è W (F ) ÷èñëî êëàññîâ ýêâèâàëåíòíîñòèC(G : RT ) = C(G : T ) = P (G : T, r, . . . , r) .αααÑ ïîìîùüþ òåîðåìû Áåðíñàéäà ìû ðåøàëè çàäà÷è îá îáùåì÷èñëå íåýêâèâàëåíòíûõ ðàçìåòîê (ðàñêðàñîê). Îäíàêî íåëüçÿáûëî ïîñ÷èòàòü ÷èñëî ðàçìåòîê äàííîãî òèïà. Òåîðåìà Ïîéàäà¼ò ýòó âîçìîæíîñòü.Ïðèêëàäíàÿ àëãåáðàÒåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Óñëîæíèì çàäà÷ó îá îæåðåëüÿõ N = 5, r = 3Çàäà÷àÑîñòàâëÿþòñÿ îæåðåëüÿ èç 5 áóñèí 3 öâåòîâ (êðàñíûé, ñèíèé,çåë¼íûé). Ñêîëüêî èìååòñÿ îæåðåëèé, èìåþùèõ ðîâíî 2 êðàñíûåáóñèíû? Îæåðåëüÿ îäèíàêîâû, ðàâíû åñëè îäíî ïîëó÷àåòñÿ èçäðóãîãî ïîâîðîòîì è/èëè ïåðåâîðîòîì.Ðåøåíèå1Áûëî: G = D5 , öèêëîâîé èíäåêñ P = 10[x51 + 4x5 + 5x1 x22 ].Âñåãî îæåðåëèé #Col(3) = P (3, .
. . , 3) = 39.x1 = y + 2, w(êðàñíûé) = y1 ,y1 = y,x2 = y 2 + 2,w(ñèíèé)= y2 , ⇒⇒y2 = y3 = 1,...w(çåë¼íûé) = y3 ,x5 = y 5 + 2.180 / 225Ïðèêëàäíàÿ àëãåáðàÒåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷1 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 y 2 23 + . . . + 5(y + 2)(y 2 + 4y + 4) =101 . . . + (80 + 40)y 2 + . . . .=10C =u2 = 12.181 / 225Ïðèêëàäíàÿ àëãåáðà182 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷àÂåðøèíû êóáà ïîìå÷àþò êðàñíûìè è ñèíèì öâåòàìè.Ñêîëüêî ñóùåñòâóåò123ðàçíîïîìå÷åííûõ êóáîâ;êóáîâ, ó êîòîðûõ ïîëîâèíà âåðøèíû êðàñíûå;êóáîâ, ó êîòîðûõ íå áîëåå 2-õ êðàñíûõ âåðøèí?ÐåøåíèåÖèêëîâîé èíäåêñ äåéñòâèÿ ãðóïïû O íà âåðøèíû êóáà1 8P (O : V ) =x1 + 6x24 + 9x42 + 8x21 x23 .α241×èñëî ðàçíîïîìå÷åííûõ êóáîâ #Col(3) = P |x1 =...=x8 =2 =552= 23 .24Ïðèêëàäíàÿ àëãåáðàÒåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷2w(êðàñíûé) = y, w(ñèíèé) = 1, xk = y k + 1, k = 1, 8:1(y + 1)8 + 9 · (y 2 + 1)4 + 4 · (y 4 + 1)2 +#Col(4, 4) =24+ 8 · (y + 1)2 (y 3 + 1)2 =1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
