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

Ëåêöèè ïî äèñêðåòíîé ìàòåìàòèêå.Ëåêòîð: Óãîëüíèêîâ Àëåêñàíäð Áîðèñîâè÷.Ìîñêâà, 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 + ...