А.Б. Угольников - Лекции по дискретной математике (1083729)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Ëåêöèè ïî äèñêðåòíîé ìàòåìàòèêå.Ëåêòîð: Óãîëüíèêîâ Àëåêñàíäð Áîðèñîâè÷.Ìîñêâà, 2003. (îò 30 äåêàáðÿ)×àñòü IÊîìáèíàòîðèêà.Ëåêöèÿ 1.Ýëåìåíòàðíûå ïîíÿòèÿ.x1 , x2 , . . . , xn .Ïóñòü äàíû ýëåìåíòûÎïðåäåëåíèå.Íàáîð ýëåìåíòîâxi1 , xi2 , .

. . , xik , k 6 níàçûâàåòñÿk -âûáîðêîé.Âûáîðêè áûâàþò:1.2.óïîðÿäî÷åííûåíåóïîðÿäî÷åííûåÎïðåäåëåíèå.âûáîðêà Óïîðÿäî÷åííàÿk -ñî÷åòàíèåì.k -âûáîðêàíàçûâàåòñÿÊðîìå ýòîãî, âûáîðêè äåëÿòñÿ åùå íà äâà òèïà à)ìè.k -ïåðåñòàíîâêîé,áåç ïîâòîðåíèéíåóïîðÿäî÷åííàÿèëè á)k-ñ ïîâòîðåíèÿ-Îáû÷íî, êîãäà ãîâîðÿò ïåðåñòàíîâêà(ñî÷åòàíèå), ïîäðàçóìåâàþò ïåðåñòàíîâêó(ñî÷åòàíèå) áåçïîâòîðåíèé.Ïîñ÷èòàåì êîëè÷åñòâîk -âûáîðîêâî âñåõ ÷åòûðåõ ñëó÷àÿõ.Ñëó÷àé 1à)n(n − 1) . .

. (n − k + 1).Ñëó÷àé 1á)nk . ýòîì ñëó÷àåkÎáîçíà÷åíèå:ìîæåò áûòü áîëüøån!k!(n−k)! . ÊàæäîåÑëó÷àé 2a) Cnk =P (n, k) =n!(n−k)! . Ïî îïðåäåëåíèþ0! = 1.n.k -ñî÷åòàíèå áåç ïîâòîðåíèéCnk nkïðåäñòàâëÿåò ñîáîék! k -ïåðåñòàíîâîê áåç ïîâòîðåíèé. Äðóãîå îáîçíà÷åíèåÑëó÷àé 2á).αi îáîçíà÷àåò êîëè÷åñòâîk -ñî÷åòàíèÿìè è íàáîðàìè ÷èñåëα1 , α2 , . . . , αn ∈ Z, òàêèõ ÷òî α1 + α2 + .

. . + αn = k, α1 , α2 , . . . , αn > 0, ìîæíî óñòàíîâèòü âçàèìíî îäíîçíà÷íîå ñîîòâåòñòâèå. Ñëåäîâàòåëüíî, êîëè÷åñòâî k -ñî÷åòàíèé ñ ïîâòîðåíèÿìè ñîâïàäàåò ñêîëè÷åñòâîì ðåøåíèé óðàâíåíèÿ α1 + α2 + . . . + αn = k, α1 , α2 , . . . , αn > 0. Òåïåðü ðàññìîòðèìïîñëåäîâàòåëüíîñòè èç 0 è 1 ñëåäóþùåãî âèäàÐàññìîòðèìâõîæäåíèé ýëåìåíòàxik -ñî÷åòàíèå xi1 , xi2 , . . .

, xik .Ïóñòü ÷èñëîâ äàííóþ âûáîðêó. Òîãäà ìåæäó âñåìè00. . . 0}100. . . 0}1 . . . 100. . . 0}| {z| {z| {zα1α2αnÊàæäîìó ðåøåíèþ óðàâíåíèÿ ñîîòâåòñòâóåò ðîâíî îäíà ïîñëåäîâàòåëüíîñòü, è íàîáîðîò. Çíà÷èò,êîëè÷åñòâî ðåøåíèé ñîâïàäàåò ñ êîëè÷åñòâîì òàêèõ ïîñëåäîâàòåëüíîñòåé, ò.å. ðàâíîÏðèìåð.Ïîñ÷èòàåì ÷èñëîk -ñî÷åòàíèékCk+n−1.ñ ïîâòîðåíèÿìè, â êîòîðûõ âñå ýëåìåíòû âñòðå÷àþòñÿáîëåå, ÷åì îäèí ðàç. Àíàëîãè÷íî ñëó÷àþ 2á), êîëè÷åñòâî òàêèõ ñî÷åòàíèé ðàâíî ÷èñëó ðåøåíèéóðàâíåíèÿ α1 + α2 + . . . + αn = k, α1 , α2 , .

. . , αn > 1. Èëè óðàâíåíèÿ (α1 − 1) + (α2 − 1) + . . . + (αn −1) = k − n, α1 , α2 , . . . , αn > 1. Ñäåëàâ çàìåíó αi0 = αi − 1, ïîëó÷èì çàäà÷ó α10 + α20 + . . . + αn0 =k−nk − n, α10 , α20 , . . . , αn0 > 0. Îòâåò ê êîòîðîé ìû óæå íàøëè Ck−1.Ïåðå÷èñëèì íåêîòîðûå1.Cnk2.Cnk = Cnn−k .3.k−1kCnk = Cn−1+ Cn−1.ñâîéñòâà.- öåëîå. Áóäåì ïîëàãàòü, ÷òî ïðèk > n Cnk = 0.2Äîêàçàòåëüñòâî.Êîëè÷åñòâî âñåõ ñî÷åòàíèé äåëèòñÿ íà äâå ãðóïïû. Ïåðâàÿ ýòî òå ñî÷åòà-íèÿ, êîòîðûå ñîäåðæàò4.Áèíîìèàëüíàÿk−1x1 Cn−1.

Âòîðàÿ ýòî òå, êîòîðûå íå ñîäåðæàòòåîðåìà.n(1 + x) =nXkx1 Cn−1.Cnk xkk=0Äîêàçàòåëüñòâî.Ïðåäñòàâèì ëåâóþ ÷àñòü â âèäå ïðîèçâåäåíèÿnñêîáîê.(1 + x) . . . (1 + x) = . . . + ak xk + . . .|{z}nÊîëè÷åñòâî ðàçëè÷íûõ ñïîñîáîâ íàáðàòükxx â ñòåïåíè kåñòüCnk . Ýòî ÷èñëî è åñòü êîýôôèöèåíò ïðè.5.2n =nPCnkk=06.nP0=(−1)k Cnkk=07.Ïîëèíîìèàëüíàÿòåîðåìà.n!xr1 . . .

xrmmr1 !r2 ! . . . rm ! 1Xn(x1 + . . . + xm ) =r1 ,...,rm >0Äîêàçàòåëüñòâî.(x1 + . . . + xm ) . . . (x1 + . . . + xm ) = . . . + ar1 ...rm xr11 . . . xrmm + . . .{z}|nÀíàëîãè÷íî ïóíêòó 4, êîýôôèöèåíò ïðèÏðèìåð.xr11 . . . xrmmðàâåír2rmCnr1 Cn−r. . . Cn−....1Ñêîëüêî ñëîâ ìîæíî ñîñòàâèòü èç áóêâ ñëîâà "ÌÀÊÀÊÀ"?6(Ì + À + Ê) = . . .6!1 2 3Ì Ê À1!2!3!Îòâåò: 60.Ôîðìóëû îáðàùåíèÿ.Ôîðìóëû âêëþ÷åíèÿ è èñêëþ÷åíèÿ.Ïóñòü çàäàíû ýëåìåíòûx1 , x2 , . . . , xNè íàáîð ñâîéñòâp1 , . .

. , p n .Êàæäûé ýëåìåíò ìîæåò îáëà-äàòü êàêèì-ëèáî íàáîðîì ñâîéñòâ èëè íå îáëàäàòü íè îäíèì.Ïóñòüw(pi1 , . . . , pik ) ÷èñëî ýëåìåíòîâ, êîòîðûå îáëàäàþò ñâîéñòâàìè pi1 , . . . , pik(ìîæåò è åùåêàêèìè-íèáóäü).ÏóñòüPW (k) =w(pi1 , . . . , pik ). ÷àñòíîñòè,W (1) = w(p1 ) + . . . + w(pk ).i1 ,...ik16i1 6...6ik 6nÈ, íàêîíåö,E(k)- ÷èñëî ýëåìåíòîâ îáëàäàþùèõÒîãäà èìååò ìåñòî ñëåäóþùàÿôîðìóëàk -ñâîéñòâàìè.E(0) = N − W (1) + W (2) + . . .

+ (−1)n W (n).3Äîêàçàòåëüñòâî.à)x1 Ðàññìîòðèì äâà ñëó÷àÿ.íå îáëàäàåò íèêàêèì ñâîéñòâîì. Òîãäà â ëåâóþ ÷àñòü ôîðìóëû îí äîáàâèò åäèíèöó. Àñïðàâà áóäåì ñ÷èòàòü, ÷òî åãî åäèíèöà âõîäèò â ÷èñëîN.x1 îáëàäàåò ñâîéñòâàìè pi1 , . . . , pik . Òîãäà âêëàäCk2 + . . . + (−1)k Ckk . Ïî ñâîéñòâó 6. ýòà ñóììà ðàâíà 0.â ëåâóþ ÷àñòü åñòüá)Óïðàæíåíèå.0.À â ïðàâóþ1 − Ck1 +Äîêàæèòå ôîðìóëókE(k) = W (k) − Ck+1W (k + 1) + .

. . + (−1)n−k Cnk W (n).Äîêàæåì íåêîòîðûåP+íåðàâåíñòâà.= N − W (1) + . . . − W (r), ãäå r íå÷åòíî.P−=N−W (1) + . . . + W (q), ãäå q ÷åòíî.qÏóñòürÓòâåðæäåíèå. ∀r, q (r -íå÷åòíî, q -÷åòíî) âåðíî ñëåäóþùåå íåðàâåíñòâîP+rÄîêàçàòåëüñòâî.6 E(0) 6P−qE(0) ñíèçó. Åñëè ýëåìåíò x1 íå îáëàäàåò íèêàêèìèE(0) åñòü åäèíèöà.

Ïóñòü ýëåìåíò x1 îáëàäàåò ñâîéñòâàìèpi1 , . . . , pik . Òîãäà 1 − Ck1 + Ck2 − . . . − Ckr âêëàä ýëåìåíòà x1 â ëåâóþ ñóììó. Åñëè k 6 r, òî îíðàâåí íóëþ. Ïîêàæåì, ÷òî ïðè k > r îí ìåíüøå ëèáî ðàâåí íóëÿ.Äîêàæåì îöåíêó äëÿñâîéñòâàìè, òî åãî âêëàä âP+rè1 − Ck1 + Ck2 − . . . − Ckr =r−10112= 1 − Ck−1+ Ck−1+ Ck−1+ Ck−1+ . . . − Ck−1+ Ckr−1 6 0.×òî è òðåáîâàëîñü äîêàçàòü.Ôîðìóëà îáðàùåíèÿ Ìåáèóñà.n = pl11 .

. . plkk .(−1)k , l1 = l2 = . . . = lk = 1,µ(1) = 1, µ(n) =0, â ïðîòèâíîì ñëó÷àå.Îïðåäåëèì ôóíêöèþ Ìåáèóñà. ÏóñòüËåììà.Xµ(d) =d|nÄîêàçàòåëüñòâî.Ïóñòü1, n = 10, â ïðîòèâíîì ñëó÷àå.n = pl11 . . . plkk , nb = pl11 . . . plkk . Ïðè n = 1 ëåììà î÷åâèäíà. Ïóñòü n > 1.XXXµ(d) =µ(d) +µ(d).d|nd|bnd|bn, d - n̂Íî âòîðîå ñëàãàåìîå ðàâíî íóëþ ïî îïðåäåëåíèþ ôóíêöèèXµ.Ïîýòîìóµ(d) = 1 − Ck1 + Ck2 + . . . + (−1)k Ckk = 0.d|bn×òî è òðåáîâàëîñü äîêàçàòü.Òåîðåìà. Ïóñòü ôóíêöèè f, g : N → R. Òîãäà, åñëè f (n) =Pd|nôîðìóëà g(n) =Pd|nf ( nd )µ(d).4g(d), òî ñïðàâåäëèâà ñëåäóþùàÿÄîêàçàòåëüñòâî.XÈç óñëîâèÿnd=Pˆ.g(d)Òîãäàˆnd|dXˆ  µ(d) =g(d)dˆ| ndd|nfXˆg(d)µ(d)=XXˆg(d)µ(d)=ndˆ|n d| d̂ˆ d·dˆ|nd,d:Xˆg(d)Xµ(d) = g(n)d| ndˆ|nd̂×òî è òðåáîâàëîñü äîêàçàòü.Ïðèìåð. Ñêîëüêî ðàçëè÷íûõ ïîñëåäîâàòåëüíîñòåé èç íóëåé è åäèíèö äëèíû n ìîæíî íàïèñàòüïî êðóãó? Åñëè ïîñëåäîâàòåëüíîñòè ìîæíî ñîâìåñòèòü ïîâîðîòîì, îíè ñ÷èòàþòñÿ îäèíàêîâûìè.M (d) ýòî ÷èñëî ïîñëåïåðèîä d, åñëè ïðè ïîâîðîòå ïî÷àñîâîé ñòðåëêå íà d ýëåìåíòîâ îíà ñîâïàäàåò ñ ñîáîé.

Çàìåòèì, ÷òî åñëè d|n, òî Mn (d) = M (d).Êîëè÷åñòâî ëèíåéíûõ ïîñëåäîâàòåëüíîñòåé, îáðàçîâàííûõ ïîñëåäîâàòåëüíîñòÿìè äëèíû n è ïåðèîäà d, åñòü dM (d). Ïóñòü f (n) êîëè÷åñòâî âñåâîçìîæíûõ ëèíåéíûõ ïîñëåäîâàòåëüíîñòåé äëèíûn.Xf (n) = 2n =dM (d) (= g(d))Ïîïðîáóåì ðåøèòü ýòó çàäà÷ó ñ ïîìîùüþ âûâåäåííîé ôîðìóëû. Ïóñòüäîâàòåëüíîñòåé äëèíûdè ïåðèîäàd.Ïîñëåäîâàòåëüíîñòü èìååòd|nn · M (n) =Xnµ(d)2 dd|nÎòñþäà,M (n) =n1Xµ(d)2 dnd|nÑëåäîâàòåëüíî, èñêîìûõ ïîñëåäîâàòåëüíîñòåéPT (n) =M (d).d|nÔîðìóëà îáðàùåíèÿ Ìåáèóñà äëÿ ÷àñòè÷íî óïîðÿäî÷åííûõ ìíîæåñòâ ñíóëåì.ÏóñòüPåñòü ìíîæåñòâî ñ îòíîøåíèÿìè ñðàâíåíèÿ "6" è ðàâåíñòâà "=".Îïðåäåëåíèå.Åñëè äëÿ ìíîæåñòâà P âûïîëíåíûx 6 x ∀x ∈ P .2.

x 6 y, y 6 z ⇒ x 6 z .3. x 6 y, y 6 x ⇒ x = y ,îíî íàçûâàåòñÿ ÷àñòè÷íî óïîðÿäî÷åííûì .ñëåäóþùèå àêñèîìû1.òîÇàìå÷àíèå.Íåêîòîðûå ýëåìåíòû ìîãóò áûòü íåñðàâíèìû.Îïðåäåëåíèå.ìíîæåñòâàÅñëè ýëåìåíòω ∈ Pòàêîé, ÷òîx y.ω 6 x ∀x ∈ P ,òîãäàωíàçûâàåòñÿ[x, y] = ω ∈ P x 6 ω 6 yèíòåðâàëîì.Îïðåäåëåíèå.ÌíîæåñòâîÎïðåäåëåíèå.Åñëè ìîùíîñòü ëþáîãî èíòåðâàëà êîíå÷íà, òî ìíîæåñòâî íàçûâàåòñÿêîíå÷íûìÏóñòüíàçûâàåòñÿ.PíóëåìP.ëîêàëüíî êîíå÷íîå ìíîæåñòâî ñ íóëåì.f (x, y) : P × P −→ Rèf (x, y) = 0 ∀x y.Ââåäåì íåêîòîðûå îïåðàöèè â êëàññå òàêèõ ôóíêöèé.Ñëîæåíèå.h=f +gîçíà÷àåò, ÷òîÓìíîæåíèå íà ÷èñëî.h = af, a ∈ Rh(x, y) = f (x, y) + g(x, y).îçíà÷àåò, ÷òî h(x, y) = a · f (x, y).5ëîêàëüíîÎïåðàöèÿ "◦".h=f ◦gîçíà÷àåò, ÷òîh(x, y) =Pf (x, y)g(x, y).z: x6z6yÇàìå÷àíèå. ñèëó ëîêàëüíîé êîíå÷íîñòè ìíîæåñòâàPîïåðàöèÿ "◦" îïðåäåëåíà êîððåêòíà.Ò.å. ñóììèðóåòñÿ ëèøü êîíå÷íîå ÷èñëî ñëàãàåìûõ.Îïðåäåëåíèå. Ìíîæåñòâî ôóíêöèé ñ ââåäåííûìè îïåðàöèÿìè íàçûâàåòñÿ àëãåáðîé èíöèäåíò-íîñòèìíîæåñòâàPè îáîçíà÷àåòñÿA(P ).Ïåðå÷èñëèì íåêîòîðûå ñâîéñòâà àëãåáðû èíöèäåíòíîñòè.1.Îïåðàöèÿ "◦" àññîöèàòèâíà.2.Îïåðàöèÿ "◦" äèñòðèáóòèâíà.3.ÂA(P )åñòü åäèíèöà.

Ýòî ôóíêöèÿδ(x, y) =Ò.å.1, x = y0, â ïðîòèâíîì∀f f ◦ δ = δ ◦ f = f.6ñëó÷àå.Ëåêöèÿ 2(10.09.03)Ëåììà. Ïóñòü f ∈ A(P ) Òîãäà ñóùåñòâîâàíèå ó f ëåâîé è ïðàâîé îáðàòíîé ôóíêöèè ðàâíîñèëüíî ñëåäóþùåìó:∀x ∈ Pf (x, x) 6= 0(1)Äîêàçàòåëüñòâî.Î÷åâèäíî, ÷òî åñëè ñóùåñòâóåò x, òàêîé ÷òî f (x, x) = 0, òî íè äëÿ êàêîég ∈ A(P ) f (x, x)g(x, x) 6= 1 = δ(x, x).Îáðàòíî. Ïóñòü äëÿ f âûïîëíåíî (1). Áóäåì èñêàòü òàêóþ ôóíêöèþ g1 ∈ A(P ), ÷òî äëÿ ëþáûõx, y ∈ PXδ(x, y) =f (x, z)g1 (z, y)ôóíêöèèz:x6z6yÄëÿ êàæäîãîx∈Pïîëîæèì:g1 (x, x) := f −1 (x, x)(2)(x, y) : x < y ðåêóðåíòíî îïðåäåëèì g1 (x, y),z : x < z 6 y:X0 = δ(x, y) = f (x, x)g1 (x, y) +f (x, z)g1 (z, y)(óñëîâèå (1) îáåñïå÷èâàåò ýòî).

Äàëåå äëÿ êàæäîé ïàðûñ÷èòàÿ, ÷òî çíà÷åíèÿg1 (z, y)èçâåñòíû äëÿ âñåõz:x<z6yîòêóäà:g1 (x, y) := −f −1 (x, x)Xf (x, z)g1 (z, y)(3)z:x<z6yÂâèäó ëîêàëüíîé êîíå÷íîñòè ìíîæåñòâàôóíêöèþ ê ôóíêöèèPôîðìóëà (2) êîððåêòíî îïðåäåëÿåò ïðàâóþ îáðàòíóþf.Àíàëîãè÷íî ðàññóæäàÿ, ïîëó÷àåì ôîðìóëó äëÿ ëåâîé îáðàòíîé ôóíêöèèg2 (x, y) := −f −1 (y, y)Xg2 (x, z)f (z, y)g2 :(4)z:x6z<y ñèëó àññîöèàòèâîñòè îïåðàöèèöèè êf◦äëÿg1èg2 ñîîòâåòñòâåííî ïðàâîé è ëåâîé îáðàòíîé ôóíê-ñïðàâåäëèâ îáùåàëãåáðàè÷åñêèé ôàêò èõ ðàâåíñòâà:g1 = δ ◦ g1 = (g2 ◦ f ) ◦ g1 = g2 ◦ (f ◦ g1 ) = g2 ◦ δ = g2Îïðåäåëåíèå.Äçåòà-ôóíêöèåé ìíîæåñòâàPζ(x, y) :=Ïî ïðåäûäóùåé ëåììå ó ôóíêöèèζíàçûâàåòñÿ ôóíêöèÿ1,0,x6yèíà÷åñóùåñòâóåò îáðàòíàÿ ôóíêöèÿµ,̼áèóñà.

Ïî ôîðìóëàì (2) (4) èìååì:µ(x, x) = 1x<y:µ(x, y) = −Xz:x<z6y7µ(z, y) = −Xz:x6z<yµ(x, z)íàçûâàåìàÿ ôóíêöèåéÒåîðåìàìíîæåñòâà(ôîðìóëà îáðàùåíèÿ ̼áèóñà äëÿ ëîêàëüíî-êîíå÷íîãî ÷àñòè÷íî óïîðÿäî÷åííîãîñ íóë¼ì).PÏóñòü f, g : P → R, ïðè÷¼ì äëÿ ëþáîãî x ∈ P ñïðàâåäëèâî:Xg(x) =f (y)(5)y:y6xÒîãäà èìååò ìåñòî ñëåäóþùàÿ ôîðìóëà îáðàùåíèÿ:Xg(y)µ(y, x)f (x) =(6)y:y6xÄîêàçàòåëüñòâî.Ïîäñòàâèì â (6) âûðàæåíèå äëÿXXy:y6xg(y)èç (5) :f (z) µ(y, x) =z:z6yXXf (z)µ(y, x) =y,z:z6y6xÏîñëåäíåå ðàâåíñòâî â ñèëó òîãî, ÷òîζ(z, y) = 1f (z)ζ(z, y)µ(y, x)y,z:z6y6xïðèz 6 y.Ïðîäîëæàåì öåïî÷êó ðàâåíñòâ:Xf (z)ζ(z, y)µ(y, x) =y,z:z6y6xX Xf (z)ζ(z, y)µ(y, x) =Xz:y:z6x z6y6x=z:z6xXXf (z) ζ(z, y)µ(y, x) =y:z6y6xf (z)δ(z, x) = f (x)z:z6x×òî è òðåáîâàëîñü äîêàçàòü.Ïðèìåð 1.

 êà÷åñòâå PíàPâîçüì¼ì ìíîæåñòâî íàòóðàëüíûõ ÷èñåë, â êà÷åñòâå îòíîøåíèÿ ïîðÿäêà îáû÷íîå îòíîøåíèå "áîëüøå - ìåíüøå"äëÿ íàòóðàëüíûõ ÷èñåë. ßñíî, ÷òî ðîëü íóëÿ âPèãðàåò 1. Âû÷èñëèì ôóíêöèþ ̼áèóñà:µ(x, x) = 1y = x + 1 : µ(x, y) = −1y 6= x + 1 : µ(x, y) = 0ÏóñòüSn =nPan ,òîãäà ôîðìóëà îáðàùåíèÿ ̼áèóñà óòâåðæäàåò, ÷òî1an = Sn − Sn−1Ïðèìåð 2.Èç îáùåé ôîðìóëû îáðàùåíèÿ ̼áèóñà ïîëó÷èì ôîðìóëó âêëþ÷åíèÿ-èñêëþ÷åíèÿ(ñì. Ëåêöèþ 1). ÏóñòüÏóñòüX = {p1 , p2 , ..., pn } ìíîæåñòâî âîçìîæíûõ ñâîéñòâ èçó÷àåìûõ NP = {x | x ⊆ P },ââåä¼ì îòíîøåíèå ïîðÿäêà íàîòíîøåíèè ïîðÿäêà ñîîòâåòñòâóåò ñàìî ìíîæåñòâîP.P :defx 6 y ⇔ y ⊆ x,îáúåêòîâ.íóëþ ïðè òàêîìÂû÷èñëèì ôóíêöèþ ̼áèóñà äëÿP:µ(x, x) = 1|y| = |x| − 1 : µ(x, y) = −1|y| = |x| − 2 : µ(x, y) = −((−1) + (−1) + 1) = 1z , òàêèõ ÷òî y ⊂ z ⊂ x è |z| = |x| − 1.

Äàëåå ïóñòüµ(x, y) = (−1)m äëÿ y ⊂ x òàêèõ, ÷òî |y| = |x|−m, ïðè m = 0, ..., k−1. Ïîêàæåì ñïðàâåäëèâîñòü ýòîé äåéñòâèòåëüíî, ñóùåñòâóåò 2 ìíîæåñòâà8m = k . Äåéñòâèòåëüíî, äëÿ äàííûõ y ⊂ x ñóùåñòâóåò ðîâíî Ckl òàêèõ z , ÷òî y ⊂ z ⊆ xk−lè |z| = |x| − (k − l), ïðè÷¼ì ïî ïðåäïîëîæåíèþ èíäóêöèè äëÿ òàêèõ z çíà÷åíèÿ µ(x, z) = (−1).Òàêèì îáðàçîì ïî ôîðìóëå äëÿ âû÷èñëåíèÿ ôóíêöèè µ èìååì:ôîðìóëû ïðèµ(x, y) = −((−1)k−1 Ck1 + (−1)k−2 Ck2 + ...

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций