dm3 (Лекция), страница 6

(2)Åùå äëèííåå îêàçûâàåòñÿ ôîðìóëà äëÿ |A ∪ B ∪ C ∪ D|, ïîëó÷àåìàÿ ñ èñïîëüçîâàíèåì (1) è (2):|A ∪ B ∪ C ∪ D| = |A| + |B| + |C| + |D|−−|A ∩ B| − |A ∩ C| − |A ∩ D| − |B ∩ C| − |B ∩ D| − |C ∩ D|++|A ∩ B ∩ C| + |A ∩ B ∩ D| + |A ∩ C ∩ D| + |B ∩ C ∩ D| − |A ∩ B ∩ C ∩ D|.

(3)À êàê íàéòè |A1 ∪ · · · ∪ Am | ?Ýòî ïðèìåðû ôîðìóë âêëþ÷åíèÿ (ñîîòâåòñòâóþùåãî ñëàãàåìûì ñî çíàêîì +)è èñêëþ÷åíèÿ (ñëàãàåìûå ñî çíàêîì −).Îáùàÿ ôîðìóëèðîâêà çàäà÷èÈìååòñÿ N îáúåêòîâ, êîòîðûå ìîãóò îáëàäàòü èëè íå îáëàäàòü ñâîéñòâàìèP1 , . . . , Pm . Äëÿ êàæäîãî íàáîðà (j1 , . . .

, jr ), 1 ≤ r ≤ m, 1 ≤ j1 < j2 < · · · <jr ≤ m, èçâåñòíî êîëè÷åñòâî N (j1 , . . . , jr ) îáúåêòîâ, îáëàäàþùèõ ñâîéñòâàìèPj1 , . . . , Pjr (è, âîçìîæíî, äðóãèìè). Òðåáóåòñÿ íàéòèNkk(0 ≤ k ≤ m) .Óêàæåì ñïîñîá âû÷èñëåíèÿ Nk . Ïîëîæèì:÷èñëîäàþùèõ ðîâíî ñâîéñòâàìèS0 = N,30îáúåêòîâ, îáëà-XSr =N (j1 , . . . , jr ),r = 1, . . . , m.(4)1 ≤ j1 < j2 < · · · < jr ≤ mÒîãäàNk =mX(−1)r−k Crk Sr .(5)r=kîáùåé ôîðìóëîé âêëþ÷åíèé-èñêëþ÷åíèé ( Crk áèíî-Âûðàæåíèå (5) íàçûâàåòñÿìèàëüíûå êîýôôèöèåíòû). Åñëè k = 0, òîN0 =mX(−1)r Sr = N − S1 + S2 − · · · + (−1)r Sr .(6)r=0÷àñòíàÿ ôîðìóëà âêëþ÷åíèé-èñêëþ÷åíèé äëÿ ÷èñëà N0 îáúåêòîâ, íå îáëàäàþùèõ íè îäíèì èç ñâîéñòâ P1, .

. . , Pm.Ýòî ôîðìóëàõ âêëþ÷åíèÿ-èñêëþ÷åíèÿ ÷èñëà N (j1 , . . . , jr ) ïðåäïîëàãàþòñÿ èçâåñòíûìè, õîòÿ îíè íå âñåãäà óêàçàíû â óñëîâèè çàäà÷è.  òàêèõ ñëó÷àÿõ èõ íàäîíàéòè ñ ïîìîùüþ ïðàâèë êîìáèíàòîðíûõ âû÷èñëåíèé. Ðàññìîòðèì ðÿä ïðèìåðîâ.Âåðíåìñÿ ê ïðèìåðó 1 è èíòåðïðåòèðóåì åãî êàê ÷àñòíûé ñëó÷àé ðàññìîòðåííîé îáùåé ïîñòàíîâêè çàäà÷è. Îáúåêòû çäåñü ýëåìåíòû ìíîæåñòâà U == A1 ∪ · · · ∪ Am , ïðè ýòîì N = |U |, ñâîéñòâî Pj ñîñòîèò â ïðèíàäëåæíîñòè ýëåìåíòà ìíîæåñòâó Aj , j = 1, .

. . , m. Êàæäûé èç ýëåìåíòîâ ïðèíàäëåæèò õîòÿ áûîäíîìó ìíîæåñòâó Aj , ò. å. êàæäûé îáúåêò îáëàäàåò õîòÿ áû îäíèì èç ñâîéñòâ,ïîýòîìó N0 = 0. Óñëîâèå "îáúåêò îáëàäàåò ñâîéñòâàìè Pj1 , . . . , Pjr " ðàâíîñèëüíîïðèíàäëåæíîñòè ýëåìåíòà ïåðåñå÷åíèþ Aj1 ∩ · · · ∩ Ajr , ïîýòîìó N (j1 , .

. . , jr ) == |Aj1 ∩ · · · ∩ Ajr |.Ïîäñòàâëÿÿ ýòè çíà÷åíèÿ â (4), (6), ïîëó÷àåì,0 = |U | + mXX(−1)r|Aj1 ∩ · · · ∩ Ajr | ,1 ≤ j1 < j2 < · · · < jr ≤ mr=1îòêóäà|U | = |A1 ∪ · · · ∪ Am | = − mXX(−1)rr=1|Aj1 ∩ · · · ∩ Ajr | ,1 ≤ j1 < j2 < · · · < jr ≤ mò.å.|A1 ∪ · · · ∪ Am | = mXr=1X(−1)r+1|Aj1 ∩ · · · ∩ Ajr | .1 ≤ j1 < j2 < · · · < jr ≤ mÏðè m = 2, 3, 4 ýòà îáùàÿ ôîðìóëà èìååò âèä (1), (2) è (3) ñîîòâåòñòâåííî.31Ïðèìåð 2.Íàéäåì êîëè÷åñòâî π(100) ïðîñòûõ ÷èñåë p òàêèõ, ÷òî p ≤ 100.Íàòóðàëüíîå ÷èñëî p íàçûâàåòñÿ ïðîñòûì, åñëè p ≥ 2 è åãî äåëèòåëÿìè ÿâëÿþòñÿòîëüêî 1 è ñàìî p.

Äëÿ ýòîãî âîñïîëüçóåìñÿ äàâíî (åùå â àíòè÷íûå âðåìåíà) èçâåñòíîé òåîðåìîé: ÷èñëî m ïðîñòîå òîãäà è òîëüêî òîãäà, êîãäà îíî íå äåëèòñÿ íè√íà îäíî ïðîñòîå ÷èñëî q òàêîå, ÷òî q ≤ m. Äîêàçàòü òåîðåìó î÷åíü ëåãêî: íàäîðàçëîæèòü ÷èñëî íà ïðîñòûå ìíîæèòåëè, òàêîå ðàçëîæåíèå äëÿ ëþáîãî íàòóðàëüíîãî åäèíñòâåííî ñ òî÷íîñòüþ äî ïîðÿäêà çàïèñè ìíîæèòåëåé.

Íàéäåì êîëè÷åñòâîíàòóðàëüíûõ ÷èñåë ñðåäè ïåðâûõ 100, íå äåëÿùèõñÿ íè íà 2, íè íà 3, íè íà 5, íèíà 7. Áóäåì ñ÷èòàòü ÷èñëà 1, . . . , 100 îáúåêòàìè, äåëèìîñòü íà q ñâîéñòâîì Pq .ÒîãäàN = S0 = 100,N (2) = 100/2 = 50, N (3) = b100/3c = 33, N (5) = 100/5 = 20, N (7) = b100/7c = 14,N (2, 3) = b100/6c = 16, N (2, 5) = 100/10c = 10, N (2, 7) = b100/14c = 7,N (3, 5) = b100/15c = 6, N (3, 7) = b100/21c = 4, N (5, 7) = b100/35c = 2,N (2, 3, 5) = b100/30c = 3, N (2, 3, 7) = b100/42c = 2, N (2, 5, 7) = b100/70c = 1,N (3, 5, 7) = b100/105c = 0, N (2, 3, 5, 7) = b100/210c = 0,S1 = N (2) + N (3) + N (5) + N (7) = 117,S2 = N (2, 3) + N (2, 5) + N (2, 7) + N (3, 5) + N (3, 7) + N (5, 7) = 45,S(3) = N (2, 3, 5) + N (2, 3, 7) + N (2, 5, 7) + N (3, 5, 7) = 6, S4 = N (2, 3, 5, 7) = 0.Ïî ôîðìóëå (6) ïîëó÷àåìN0 = S0 − S1 + S2 − S3 + S4 = 100 − 117 + 45 − 6 + 0 = 22.Ñðåäè ýòèõ 22 ÷èñåë îêàçûâàåòñÿ è ÷èñëî 1, íå ÿâëÿþùååñÿ ïðîñòûì ïî îïðåäåëåíèþ, à ïðîñòûå ÷èñëà 2, 3, 5, 7 îòñóòñòâóþò, ïîýòîìóπ(100) = 22 − 1 + 4 = 25.Âîò âñå ïðîñòûå ÷èñëà íå áîëüøèå, ÷åì 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,43,47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Çàìåòèì, ÷òî ñëåäóþùåå ÷èñëî 101 òàêæåïðîñòîå. 4Ïðèìåð 3. Òàêèì æå îáðàçîì ìîæíî àíàëèçèðîâàòü ïåðåñòàíîâêè ñ íåïîäâèæ-íûìè ýëåìåíòàìè. Îáúåêòû âñå m! ïåðåñòàíîâîê α(x) ýëåìåíòîâ x = 1, 2, . . . , m.4Âîáùåì ñëó÷àå ñîîòíîøåíèåxln xïðè x → ∞ äëÿ ëþáîãî âåùåñòâåííîãî ïîëîæèòåëüíîãî ÷èñëà x óñòàíîâëåíî âî âòîðîé ïîëîâèíå XIX â. ðóññêèì ìàòåìàòèêîì è ìåõàíèêîì ×åáûø¼âûì Ïàôíóòèåì Ëüâîâè÷åì è ôðàíöóçñêèìè ìàòåìàòèêàìè ÆàêîìÀäàìàðîì è Øàðëåì äå ëà Âàëëå Ïóññåíîì.π(x) ∼32Ñâîéñòâî Pj ñîñòîèò â íåïîäâèæíîñòè ýëåìåíòà j (α(j) = j ), j = 1, . . .

, m, ò. å.ïåðåñòàâëÿþòñÿ òîëüêî ýëåìåíòû, îòëè÷íûå îò j . ÒîãäàN = m!,N (j1 , . . . , jr ) = (m − r)!,÷èñëî ïåðåñòàíîâîê, èìåþùèõ ðîâíî k íåïîäâèæíûõ ýëåìåíòîâ, íàõîäèòñÿ êàê Nkïî ôîðìóëå (5).Çàäàíèå äëÿ ñàìîñòîÿòåëüíîãî ðåøåíèÿ6. Íàéäèòå ÷èñëî ïåðåñòàíîâîê ýëåìåíòîâíîk1, . . . , m, îñòàâëÿþùèõ ðîâ-ýëåìåíòîâ íåïîäâèæíûìè.N12345678910111213141516Íîìåð âàðèàíòàNm4546455545657676k0111202334257364îñòàåòñÿ òàêèì æå, êàê â ïðåäûäóùèõ çàäàíèÿõ.Ðåøåíèÿ ïðèñûëàéòå ïî ïðåæíåìó àäðåñó MeshchaninovDG@mpei.ruÌåùàíèíîâó Äìèòðèþ Ãåðìàíîâè÷ó7Îñíîâíûå ïîíÿòèÿ òåîðèè ãðàôîâÂàæíûì èíñòðóìåíòîì äèñêðåòíîé ìàòåìàòèêè ÿâëÿþòñÿ ãðàôû.íàçûâàåòñÿ ïàðà ìíîæåñòâ G = (V, E), V = {v1 , .

. . , vn }, E = {e1 , . . . , em }.Ýëåìåíòû vi ìíîæåñòâà V íàçûâàþòñÿãðàôà G, ýëåìåíòû ej ìíîæåñòâà E , ýòî ïàðû ej = {vj1 , vj2 } ðàçëè÷íûõ âåðøèí. Åñëè âåðøèíûÃðàôîìðåáðàìèâåðøèíàìè33ñìåæíûìèvj1 , vj2 îáðàçóþò ðåáðî ej , îíè íàçûâàþòñÿ, ïðè ýòîì âåðøèíà vj1 èðåáðî ej íàçûâàþòñÿäðóã äðóãó, ýòî æå ñïðàâåäëèâî è äëÿ âåðøèíû vj2 è òîãî æå ðåáðà ej . ×èñëî ðåáåð, èíöèäåíòíûõ âåðøèíå vi , íàçûâàåòñÿñòåïåíüþ ýòîé âåðøèíû è îáîçíà÷àåòñÿ d(vi ).

V E ( n m).Ïðèìåð 1. Ðàññìîòðèì ãðàô G ñî ñëåäóþùèìè âåðøèíàìè è ðåáðàìè:èíöèäåíòíûìèV = {v1 , . . . , v7 },E = {e1 , e2 , e3 , e4 , e5 },e1 = {v1 , v2 }, e2 = {v1 , v3 }, e3 = {v2 , v3 }, e4 = {v2 , v4 }, e5 = {v5 , v6 }.Òîãäà n = 7, m = 5, G íåîðèåíòèðîâàííûé è èìååò ñëåäóþùèå ñòåïåíè âåðøèí:i 1 2 3 4 5 6 7d(vi ) 2 3 2 1 1 1 0Åñëè ñëîæèòü ñòåïåíè, òî ïîëó÷èì 2 + 3 + 2 + 1 + 1 + 1 + 0 = 2 · 5.Òåîðåìà 1.Ñóììà ñòåïåíåé âñåõ âåðøèí ãðàôà ðàâíà óäâîåííîìó ÷èñëó ðåáåð:nXd(vi ) = 2m.(1)i=1Äîêàçàòåëüñòâî.Ïóñòü d(vi , vj ) ýòî ÷èñëî ðåáåð, ñîåäèíÿþùèõ âåðøèíûvi è vj . Òîãäà d(vi , vj ) = d(vj , vi ) ∈ {0, 1},nXi=1d(vi ) =nn XXd(vi , vj ) =nn XXd(vi , vj ),j=1 i=1i=1 j=1è â ëåâîé ÷àñòè ðàâåíñòâà (1) êàæäîå ðåáðî ó÷òåíî ðîâíî äâàæäû: â ñëàãàåìûõd(vi ) è d(vj ).

Ñëåäñòâèå 1.. ïðèìåðå 1 ÷åòûðå âåðøèíû íå÷åòíîé ñòåïåíè v2 , v4 , v5 , v6 . Âåðøèíà v7 èìååò÷åòíóþ ñòåïåíü 0, òàêàÿ âåðøèíà íàçûâàåòñÿ.Ïðèâåäåì ïðèìåð, â êîòîðîì ãðàôû è ñòåïåíè âåðøèí ïðèìåíÿþòñÿ äëÿ ðåøåíèÿ ëîãè÷åñêîé çàäà÷è.Ïðèìåð 2. Ó÷åíèêè îäíîãî êëàññà ïðîâîäèëè íà óðîêå ìàòåìàòèêè êðóãîâîéòóðíèð ïî èãðå â "êðåñòèêè-íîëèêè". Ó÷àñòíèêîâ áûëî ïÿòåðî. Êîãäà ïðîçâåíåëçâîíîê ñ óðîêà, òóðíèð ïðåðâàëè, â ýòîò ìîìåíò îêàçàëîñü ñûãðàíî 6 ïàðòèé.Áîëüøå âñåãî èãð, ïî òðè, ïðîâåëè òîëüêî Àëåíà è Âàñÿ. Ñêîëüêî èãð ïðîâåëèîñòàëüíûå ó÷àñòíèêè? Êòî ñ êåì èãðàë?Îïèøåì òóðíèð ãðàôîì ñ 5 âåðøèíàìè, ñîîòâåòñòâóþùèìè ó÷àñòíèêàì.

Ñîåäèíèì ïàðó âåðøèí ðåáðîì, åñëè ñîîòâåòñòâóþùèå ó÷àñòíèêè ñûãðàëè äðóã ñäðóãîì. Íàçîâåì ó÷àñòíèêîâ À (Àëåíà),  (Âàñÿ), Ñ(Ñàøà), D (Äàøà) è Å (Åãîð),×èñëî âåðøèí íå÷åòíîé ñòåïåíè â ãðàôå ÷åòíîèçîëèðîâàííîé34òàê æå îáîçíà÷èì è âåðøèíû. Òîãäà ÷èñëî ïàðòèé, ñûãðàííûì êàæäûì ó÷àñòíèêîì X , åñòü ñòåïåíü d(X) âåðøèíû X .

B ñèëó òåîðåìû 1 èìååìd(A) + d(B) + d(C) + d(D) + d(E) = 2 · 6,d(A) = d(B) = 3.Íå îãðàíè÷èâàÿ îáùíîñòè, ïîëàãàåì d(C) ≥ d(D) ≥ d(E). Òîãäà d(C) < 3 èd(C), d(D), d(E) ∈ {0, 1, 2},(2)d(C) + d(D) + d(E) = 6.(3)Åñëè d(E) = 0, òî d(C) + d(D) = 6 è óñëîâèÿ (2) è (3) íå ìîãóò âûïîëíÿòüñÿîäíîâðåìåííî.

Åñëè d(E) = 1, òî d(C) + d(D) = 5 è óñëîâèÿ (2) è (3) òàêæåíå âûïîëíÿþòñÿ îäíîâðåìåííî. Îñòàåòñÿ åäèíñòâåííàÿ âîçìîæíîñòü d(E) = 2.Ïðè ýòîì è d(C) = d(D) = 2. Íåîáõîäèìî ïðîâåðèòü, ÷òî òàêàÿ âîçìîæíîñòüäåéñòâèòåëüíî ðåàëèçóåòñÿ, ò. å. ïîñòðîèòü ãðàô òóðíèðà. Ýòî ìîæíî ñäåëàòüåäèíñòâåííûì ñïîñîáîì, ñîîòâåòñòâóþùèì ñëåäóþùåìó ìíîæåñòâó èç 6 èãðàâøèõïàð (ðåáåð ãðàôà): A è C , A è D, A è E , B è C , B è D, B è E .Ðàññìîòðèìñïîñîáû çàäàíèÿ ãðàôîâ.1. Óêàçàíèåì ñïèñêîâ âåðøèí è ðåáåð.Ýòèì ñïîñîáîì áûëè çàäàíû ãðàôû â ïðèâåäåííûõ ïðèìåðàõ.2.