А.Б. Угольников - Лекции по дискретной математике (1083729), страница 2
Текст из файла (страница 2)
+ Ckk ) = (−1)k1 − Ck1 + Ck2 − ... + (−1)k Ckk = 0 ñì. Ëåêöèþ 1 ) .Òåïåðü íà P îïðåäåëèì ôóíêöèè E(x) = êîëè÷åñòâî îáúåêòîâ îáëàäàþùèõ â òî÷íîñòè íàáîðîìñâîéñòâ x, à òàêæå ω(x) = êîëè÷åñòâî îáúåêòîâ îáëàäàþùèõ íàáîðîì ñâîéñòâ x (ïðè ýòîì, áûòü(âîñïîëüçîâàëèñü èçâåñòíûì òîæäåñòâîììîæåò, èìåþùèõ áîëåå øèðîêèé íàáîð ñâîéñòâ).
ßñíî, ÷òî â íàøèõ îáîçíà÷åíèÿõω(x) =XE(x)y:y6xÏîýòîìó ìîæíî ïðèìåíèòü ôîðìóëó îáðàùåíèÿ ̼áèóñà:E(x) =Xω(y)µ(y, x)y:y6xâ ÷àñòíîñòèE(∅) =nX(−1)kXω(x)x:|x|=kk=0(ñðàâíèòå ñ ðåçóëüòàòîì ïîëó÷åííûì íà Ëåêöèè 1).Óïðàæíåíèå.Äîêàçàòü ôîðìóëó îáðàùåíèÿ ̼áèóñà èç Ëåêöèè 1 èñõîäÿ èç îáùåé ôîðìóëûîáðàùåíèÿ ̼áèóñà.Ìåòîä ïðîèçâîäÿùèõ ôóíêöèéÐàññìîòðèìK[[x]]K , ò.å.
ìíîæåñòâîa = (a0 , a1 , a2 , ..., ak , ...) ôîðìàëüíî ñîîòíåñ¼ííûõ ñ2kìîíîìîâ {1, x, x , ..., x , ...} ïî ñëåäóþùåìó ïðàâèëó: êîëüöî ôîðìàëüíûõ ñòåïåííûõ ðÿäîâ íàä ïîëåìíå÷íûõ ÷èñëîâûõ ïîñëåäîâàòåëüíîñòåéíå÷íîé ëèíåéíîé êîìáèíàöèåéáåñêîáåñêî-a(x) = a0 + a1 x + a2 x2 + ... + ak xk + ...Íà ìíîæåñòâå ââîäÿòñÿ åñòåñòâåííûå îïåðàöèè ñëîæåíèÿ + è óìíîæåíèÿ” · ”:a(x) + b(x) = a0 + b0 + (a1 + b1 )x + (a2 + b2 )x2 + ... + (ak + bk )xka(x)·b(x) = a0 b0 +(a0 b1 +a1 b0 )x+(a0 b2 +a1 b1 +a2 b0 )x2 +...+(a0 bk +a1 bk−1 +...+ak−1 b1 +ak b0 )xk +...Ïîñòðîåííîå ìíîæåñòâî ñ ýòèìè îïåðàöèÿìè îáðàçóåò àññîöèàòèâíîå êîììóòàòèâíîå êîëüöî ñ åäè-a = (0, 0, 0, ..., 0, ...), ðîëü åäèíèöû ïîñëåäîa = (1, 0, 0, ..., 0, ...).Óòâåðæäåíèå. Ýëåìåíò a = (a0 , a1 , a2 , ..., ak , ...) ∈ K[[x]] îáðàòèì òîãäà è òîëüêî òîãäà,êîãäà a0 6= 0.Äîêàçàòåëüñòâî.
Äåéñòâèòåëüíî, åñëè a0 = 0, òî, î÷åâèäíî, íè ïðè êàêîì b a0 b0 6= 0. Îá−1ðàòíî, ïóñòü a0 6= 0, òîãäà ïîëîæèì b0 = a0 . Äàëåå ïî ðåêóðåíòíûì ñîîòíîøåíèÿì âû÷èñëÿåìb1 , b2 , b3 , ... :b1 = −a−10 a1 b0íèöåé, ðîëü íóëÿ â êîëüöå èãðàåò ïîñëåäîâàòåëüíîñòüâàòåëüíîñòüb2 = −a−10 (a1 b1 + a2 b0 )·m −1Ïðèìåð. (1 − x )m2m=1+x +x3m+x·+ ...9· ïðîâåðÿåòñÿ ïåðåìíîæåíèåì.Ââåä¼ì îïåðàòîðD : K[[x]] → K[[x]]a(x) =∞Xai xi ,D(a(x)) =i=0∞X(i + 1)ai+1 xii=0Ñâîéñòâà.1.D(a(x) + b(x)) = D(a(x)) + D(b(x))2. (ôîðìóëà Ëåéáíèöà)Ñëåäñòâèå.D(a(x)b(x)) = D(a(x))b(x) + a(x)D(b(x))ai (x), i = 1, ..., N îáðàòèìû, òî!NNNNYXYXYD(ai (x))iDa (x) =D(ai (x))aj (x) =ai (x) ·⇒ai (x)i=1i=1i=1i=1Åñëèj6=iDNQa (x)ii=1NQ=ai (x)NXD(ai (x))i=1(7)ai (x)i=1Ïðèìåíèì àïïàðàò ïðîèçâîäÿùèõ ôóíêöèé (ôîðìàëüíûõ ðÿäîâ) äëÿ îòûñêàíèÿ êîëè÷åñòâàn.P = {π(x)| π(x) = c0 + c1 x + ... + ck xk , ci ∈ {0, 1}, ck = 1}íàä Z2 .íåïðèâîäèìûõ äâîè÷íûõ ìíîãî÷ëåíîâ ñòåïåíèÈòàê, ïóñòüìíîãî÷ëåíîâ ìíîæåñòâî íåíóëåâûõÈç êóðñà àëãåáðû õîðîøî èçâåñòíî, ÷òî êîëüöî ìíîãî÷ëåíîâ ôàêòîðèàëüíàÿ îáëàñòü öåëîñòíîñòè, ò.å.
âñÿêèé íåíóëåâîé ìíîãî÷ëåí îäíîçíà÷íûì îáðàçîì ñ òî÷íîñòüþ äî ïîðÿäêà ñîìíîæèòåëåè äîìíîæåíèÿ íà îáðàòèìûé ýëåìåíò çàïèñûâàåòñÿ â ïðîèçâåäåíèå íåïðèâîäèìûõ.  êîëüöå ìíîãî÷ëåíîâ íàäZ2 êðîìå åäèíèöû êîëüöà äðóãèõ îáðàòèìûõ ýëåìåíòîâ íåò. Ïîñòàâèì çàäà÷ó îòûñêàíèÿm (íàïðèìåð I1 , î÷åâèäíî, ðàâíî 2).Ïóñòü R ⊆ P , Rk = {π(x) ∈ R| deg π = k}.
Ïðîèçâîäÿùåé ôóíêöèåé èëè íóìåðàòîðîì ìíîæå2ñòâà R íàçûâàåòñÿ ôîðìàëüíûé ðÿä cR (x) = c0 + c1 x + c2 x + ..., ãäå ck = |Rk | äëÿ êàæäîãî k . ßñíî,∞P1÷òî cP (x) =2k xk =.1 − 2xk=012IÏóñòü fm (x), fm (x), ..., fmm (x) âñå íåïðèâîäèìûå ìíîãî÷ëåíû ñòåïåíè m. ÏóñòüIm ÷èñëà íåïðèâîäèìûõ äâîè÷íûõ ìíîãî÷ëåíîâ ñòåïåíèiiRm= {π(x) ∈ P| π(x) = (fm(x))k , k = 0, 1, 2, ...}, i = 1, 2, ..., Im .1.1 − xmÓòâåðæäåíèå.
Ñïðàâåäëèâà ñëåäóþùàÿ ôîðìóëà:ßñíî, ÷òîmi = 1 + xcRm+ x2m + x3m + ... =cP =Im∞ YYicRm(8)m=1 i=1Äîêàçàòåëüñòâî.ìíîãî÷ëåíîâ ñòåïåíèÊîýôôèöèåíò ïðèk.xkâ ëåâîé ÷àñòè ðàâåíñòâà (8) êîëè÷åñòâî äâîè÷íûõ ñèëó åäèíñòâåííîñòè ïðåäñòàâëåíèÿ ìíîãî÷ëåíà â âèäå ïðîèçâåäåíèÿíåïðèâîäèìûõ êàæäîìó äâîè÷íîìó ìíîãî÷ëåíóπ(x)âçàèìíîîäíîçíà÷íî ìîæíî ñîïîñòàâèòü áåñ-êîíå÷íóþ ïîñëåäîâàòåëüíîñòü ÷èñåët = (t11 , t21 , t12 , ..., tI22 , ..., t1m , ..., tImm , ..., 0, 0, 0, ...),10âñåãäà çàêàí÷èâàþùóþñÿ áåñêîíå÷íîé ïîñëåäîâàòåëüíîñòüþ íóëåé, ñî ñëåäóþùèì ñìûñëîì :∞ IQmQm=1 i=1timi(fm(x)).Ïðè÷¼ìImPPm i=1mtim = deg π(x).äîáíûå ñëàãàåìûå, òî êîýôôèöèåíò ïðèxkπ(x) =Åñëè â ïðàâîé ÷àñòè ðàâåíñòâà (8) ïðèâåñòè ïî-áóäåò ðàâåíP1, ãäå A = Im PPtmtim = k .
 ñèëóm i=1t∈Aóïîìÿíóòîé âçàèìíî îäíîçíà÷íîñòè ýòè êîýôôèöèåíòû ðàâíû. ×òî è òðåáîâàëîñü äîêàçàòü.Ñëåäñòâèå.∞Y11=.1 − 2x m=1 (1 − xm )Im(9)Äàëåå îáðàòèì îáå ÷àñòè ðàâåíñòâà (9):1 − 2x =∞Y(1 − xm )Imm=1Ïðîäèôôåðåíöèðóåì è ïîëó÷åííîå ðàâåíñòâî óìíîæèì íà ðàâåíñòâî (9) :−2=1 − 2xD∞Q(1 − xm )Imm=1∞Q.(1 − xm )Imm=1Âîñïîëüçîâàâøèñü ðàâåíñòâîì (7), èìååì:∞∞∞XXXD (1 − xm )Im−2D (1 − xm )−xm−1==I=mI⇒mm1 − 2x m=1 (1 − xm )Im1 − xm1 − xmm=1m=1∞X1 − 2x − 11 − xm − 1=⇒mIm1 − 2x1 − xmm=1∞X11=⇒1−mIm 1 −1 − 2x m=11 − xm−1 +∞X2k xk =k=0∞X∞XmIm −1 + 1 + xm + x2m + ... ⇒m=1∞X2k xk =mIm xm + x2m + ... ⇒m=1k=12k =XmIm .m: m|kÂîñïîëüçîâàâøèñü ôîðìóëîé îáðàùåíèÿ ̼áèóñà îêîí÷àòåëüíî ïîëó÷àåì:Òåîðåìà.Im =Xµ(m)2k/mm: m|kÅñëè ðàññìàòðèâàòü ìíîãî÷ëåíû íàääëÿpImZpäëÿ ïðîñòîãî ÷èñëà íåïðèâîäèìûõ ìíîãî÷ëåíîâ ñòåïåíèp,m>0ôîðìóëó:pIm=Xµ(m)pk/mm: m|kÓïðàæíåíèå.Äîêàçàòü.11òî ðàññóæäàÿ àíàëîãè÷íî, ïîëó÷àåìèçZp [x]ñî ñòàðøèì êîýôôèöèåíòîì 1Ëåêöèÿ 3.Ðàññìîòðèì íåêîòîðûå ñëåäñòâèÿ èç òåîðåìû î ÷èñëå íåïðèâîäèìûõ ìíîãî÷ëåíîâ, êîòîðóþ ìûäîêàçàëè íà ïðîøëîé ëåêöèè.Ñëåäñòâèå.
Im > 0, I1 = 2.2k = kIk + I1 +XmIm(1)m|km6=1,kà) åñëèk ïðîñòîå, òîPmIm = 0èIk =m|km6=1,ká) åñëèk2k −2k . íå ïðîñòîå, òîIk 62k − 22k.6kk(2)Äàëåå,2k = kIk +XmIm < kIk +2k − 2k/2+1k=⇒ Ik >2kk ,k2m < kIk + 2k/2+1 =⇒m=1m|km>1Ñëåäñòâèå. Ik > 0, Ik ∼k/2X→ ∞.Ðàññìîòðèì ïðèìåð ïðèìåíåíèÿ ìåòîäà ïðîèçâîäÿùèõ ôóíêöèé.Ïðèìåð. Ñêîëüêî ìîæíî ñîñòàâèòü ïîñëåäîâàòåëüíîñòåé èç íóëåé è åäèíèö äëèíû n, â êîòîðûõäâå åäèíèöû íå ñòîÿò ðÿäîì?Ïóñòü ÷èñëî òàêèõ ïîñëåäîâàòåëüíîñòåé åñòüun .
Ðàçîáüåì âñå ïîñëåäîâàòåëüíîñòè íà äâå êó÷è:à) íà ïåðâîì ìåñòå ñòîèò åäèíèöà,á) íà ïåðâîì ìåñòå ñòîèò íîëü. ñëó÷àå à) íà âòîðîì ìåñòå ïî óñëîâèþ äîëæåí ñòîÿòü íîëü, ïîýòîìó êîëè÷åñòâî ïîñëåäîâàòåëüíîñòåé â ýòîì ñëó÷àåun−2 .À â ñëó÷àå á) èõ êîëè÷åñòâî åñòüÎòñþäà, èìååì ðåêóðåíòíîå ñîîòíîøåíèåun = un−1 + un−2 .un−1Ïðè ýòîì,u1 = 2, u2 = 3.Ðåêóðåíòíûå ñîîòíîøåíèÿ ñ ïîñòîÿííûìè êîýôôèöèåíòàìè.Ðàññìîòðèì ðåêóðåíòíîå ñîîòíîøåíèåun+r = a1 un+r−1 + a2 un+r−2 + . . . + ar un ,(3)a1 , . . .
, ar ∈ R è ar 6= 0. Íàøà çàäà÷à ïî èçâåñòíûì çíà÷åíèÿì u0 , . . . , ur−1un äëÿ ëþáûõ n. Ñâÿæåì ñ ïîñëåäîâàòåëüíîñòüþ u0 , u1 , . . . ôîðìàëüíûé ðÿä u(x) =u0 + u1 x + u2 x2 + . . ..2rÐàññìîòðèì ðÿä k(x) = 1 − a1 x − a2 x − . . . − ar x . Ïóñòü ðÿä c(x) åñòü ïðîèçâåäåíèå ðÿäîâ u(x) èk(x). Òîãäàcn+r = un+r − a1 un+r−1 − a2 un+r−2 − . . . − ar un = 0, ∀n > 0.ãäå êîýôôèöèåíòûíàéòè çíà÷åíèÿÀ, çíà÷èò,deg c(x) 6 r − 1.f (x) = xr k( x1 ).Ðàññìîòðèì ôóíêöèþÎïðåäåëåíèå. f (x)Ïóñòüα1 , . . . , αsíàçûâàåòñÿÒîãäàf (x) = xr − a1 xr−1 − . . .
− ar .õàðàêòåðèñòè÷åêèì ìíîãî÷ëåíîì.åãî êîðíè, l1 , . . . , ls ñîîòâåòñòâåííî èõ êðàòíîñòü. Òîãäàf (x) = (x − α1 )l1 · . . . · (x − αs )ls ⇐⇒ k(x) = (1 − α1 x)l1 · . . . · (1 − αs x)ls12lsu(x) =sXXc(x)c(x)βi,k==,ll1sk(x)(1 − α1 x) · . . . · (1 − αs x)(1 − αi x)ki=1k=1ãäåβi,k ∈ C.Ïîñëåäíåå ðàâåíñòâî åñòü ñëåäñòâèå èç òåîðåìû î ïðåäñòàâëåíèè ïðàâèëüíîé äðîáè ââèäå ñóììû ïðîñòåéøèõ.Äàëåå,−k(1 − αi x)ò.å. êîýôôèöèåíò ïðèxnåñòü∞X−k(−k − 1) · . . . · (−k − n + 1) n n=1+αi x ,n!n=1k(k+1)·...·(k+n−1) nαi . Çàìåòèì, ÷òîn!(k − 1)!k(k + 1) · . .
. · (k + n − 1) nk(k + 1) · . . . · (k + n − 1) nk−1αi =αi = Ck+n−1= P (n),n!(k − 1)!n!ãäåP (n)ïðè ôèêñèðîâàííîìkn ñòåïåíè íå áîëüøå, ÷åì k − 1.u(x) çàïèøåòñÿ â ñëåäóþùåì âèäååñòü ìíîãî÷ëåí îòÎòñþäà, ôîðìóëà äëÿ êîýôôèöèåíòîâ ðÿäàun =sXPi (n)αin ,deg Pi (n) 6 li − 1.i=1Òåì ñàìûì ìû äîêàçàëè ñëåäóþùóþ òåîðåìó.Òåîðåìà. Ïóñòü çàäàíî ðåêóðåíòíîå ñîîòíîøåíèå (3). f (x) åãî õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ.α1 , . . . , αs êîðíè f (x), l1 , . . .
, ls èõ êðàòíîñòü. Òîãäà ðåøåíèå (3) çàïèñûâàåòñÿ ôîðìóëîéun =sXPi (n)αin ,deg Pi (n) 6 li − 1.i=1Óïðàæíåíèå.Äîêàçàòü, ÷òî êîýôôèöèåíòû ìíîãî÷ëåíîâPi (n) îäíîçíà÷íî âûðàæàþòñÿ ÷åðåçu0 , . . . , ur−1 .×èñëà Ôèáîíà÷÷è.×èñëà Ôèáîíà÷÷è çàäàþòñÿ ñëåäóþùèì ðåêóðåíòíûì ñîîòíîøåíèåìun+2 = un+1 + un , u0 = 1, u1 = 2.Ñîñòàâèì õàðàêòåðèñòè÷åñêèé ìíîãî÷ëåíunx2 − x − 1 = 0.Åãî êîðíè åñòüçàïèøåòñÿ â âèäåun = C1 α1n + C2 α2n .ÊîýôôèöèåíòûC1 , C2íàõîäÿòñÿ èç ñèñòåìû(C1 + C2 = 1 √ √C1 1+2 5 + C2 1−2 5 = 2.13α1,2 =√1± 52 . Ôîðìóëà äëÿ(24.09.03)Ëåêöèÿ 4Ðàññìîòðèì ïðèìåíåíèå ìåòîäà ïðîèçâîäÿùèõ ôóíêöèé äëÿ ðåøåíèÿ çàäà÷è î íàõîæäåíèè÷èñåë Êàòàëàíè êîëè÷åñòâà ñïîñîáîâ ïåðåìíîæèòüÎáîçíà÷èì èñêîìîå êîëè÷åñòâî ñïîñîáîâßñíî, ÷òînv2 = 1, v3 = 2.n ýëåìåíòîâ, åñëè óìíîæåíèå íå àññîöèàòèâíî.vn .v1 := 1.
Åñëè â íåêîòîðîì ìåñòå ðàçáèòük + 1-ãî äî n-ãî è ñ÷èòàòü, ÷òî ñíà÷àëà ïðîèçâî-Äëÿ óäîáñòâà îáîçíà÷èììíîæèòåëåé íà 2 ÷àñòè : îò 1-ãî äîk -ãî,è îòäÿòñÿ ïåðåìíîæåíèÿ âíóòðè íèõ, à ïîòîì ïåðåìíîæàþòñÿ ðåçóëüòàòû, òî ïðè òàêîì ðàçäåëåíèèñóùåñòâóåòvk vn−kñïîñîáîâ:(x1 ...xk ) (xk+1 ...xn )| {z } |{z}Ïîýòîìó, ïðîñóììèðîâàâ ïî âñåìk,vkvn−kñïîñîáîâñïîñîáîâäëÿvnïîëó÷àåì:vn = v1 vn−1 + v2 vn−2 + ... + vn−1 v1Çàïèøåì ôîðìàëüíûé ðÿä:v(x) = v1 x + v2 x2 + ... ,vi èíòåðåñóþùèå= v(x) − x:ãäåíàñ ÷èñëà Êàòàëàíè. Çàìåòèì, ÷òî â ýòîì ñëó÷àåv(x)v(x) =v(x)v(x) = v1 v1 x2 + (v1 v2 + v2 v1 )x3 + ... + (v1 vn−1 + v2 vn−2 + ...
+ vn−1 v1 )xn + ... == v2 x2 + v3 x3 + ... + vn xn + ...Çàìåòèì, ÷òî óðàâíåíèþ(u(x))2 − u(x) + x = 0u(x) =1−óäîâëåòâîðÿåò ôóíêöèÿ√1 − 4x2Ýòà ôóíêöèÿ â íåêîòîðîé îêðåñòíîñòè íóëÿ ðàçëàãàåòñÿ â ñõîäÿùèéñÿ ê íåé ðÿä Òåéëîðà, ïðè÷¼ìýòîò ðÿä Òåéëîðà ñõîäèòñÿ àáñîëþòíî. Ñëåäîâàòåëüíî äëÿ å¼ ðÿäà Òåéëîðà âûïîëíÿåòñÿ òî æå ñîîòíîøåíèå. Êàê ìû óâèäèì íèæå, ýòîò ðÿä áóäåò íà÷èíàòüñÿ ñ ÷ëåíàx, ñ åäèíè÷íûì êîýôôèöèåíòîì.Ñîøë¼ìñÿ íà äâà ôàêòà èç îáùåé òåîðèè ñõîäÿùèõñÿ ðÿäîâ : èç ïîòî÷å÷íîãî ðàâåíñòâà ñõîäÿùèõñÿâ íåêîòîðîé îêðåñòíîñòè òî÷êè ðÿäîâ ñëåäóåò ðàâåíñòâî èõ êîýôôèöèåíòîâ è àáñîëþòíî ñõîäÿùèåñÿ ðÿäû ìîæíî ïåðåìíîæàòü ïî÷ëåííî â ïðîèçâîëüíîì ïîðÿäêå. Ó÷èòûâàÿ âñ¼ âûøåñêàçàííîå,ñòàíîâèòñÿ ÿñíî, ÷òî êîýôôèöèåíòû ðÿäà Òåéëîðà ôóíêöèèu ñîîòâåòñòâóþùèå ÷èñëà Êàòàëàíè.Âû÷èñëèì èõ:u(x) =1−√∞1 − 4x1 X −1/2(1/2 − 1)...(1/2 − n + 1)=(−4)n xn22 n=1n!)1 1 (− 12 )(− 32 )...( −2n+32(−4)n =22n!1 (−1)n (2n − 3)!!=(−4)n =4 2n−1n!1 1(2n − 2)!=(4)n =n−142(2n − 2)!!n!un = −=ãäå ïîä÷òî èn!!4n (2n − 3)!1 n−1= C2n−2,22n (n − 1)!n!nïîíèìàåòñÿ ïðîèçâåäåíèå íàòóðàëüíûõ ÷èñåë íå ïðåâîñõîäÿùèõn.14nè òîé æå ÷¼òíîñòè,Îòêóäà çàêëþ÷àåì, ÷òîvn =1 n−1Cn 2n−2Ðàññìîòðèì ïîñëåäíèé ïðèìåð: ïîäñ÷èòàåì êîëè÷åñòâî âûáîðîê ñ ïîâòîðåíèÿìè ïðè ïîìîùèàïïàðàòà ïðîèçâîäÿùèõ ôóíêöèé.Ðàññìîòðèì ïðîèçâåäåíèå:(1 + x + x2 + ...)...(1 + x + x2 + ...) =|{z}nkak xk(1)k=0xm1 xm2 ...xmn ,ò.÷.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
