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

Ïóñòü yn êîëè÷åñòâî ïåðåñòàíîâîê π(j) ýëåìåíòîâ j = 1, 2, . . . , n,ïðè êîòîðûõ êàæäûé ýëåìåíò j ëèáî îñòàåòñÿ íà ìåñòå, ëèáî ïåðåìåùàåòñÿ òîëüêîíà ñîñåäíåå ìåñòî, ò. å.π(1) ∈ {1, 2},π(n) ∈ {n − 1, n},π(j) ∈ {j − 1, j, j + 1}, 2 ≤ j ≤ n − 1.Ïóñòü π îäíà èç yn èñêîìûõ ïåðåñòàíîâîê n ýëåìåíòîâ. Åñëè π(n) = n, íàäîïåðåñòàâèòü ïðè òåõ æå óñëîâèÿõ n−1 ïðåäûäóùèõ ýëåìåíòîâ. Åñëè π(n) = n−1,òî π(n − 1) = n è íàäî ïåðåñòàâèòü ïðè òåõ æå óñëîâèÿõ ïðåäûäóùèå n − 2ýëåìåíòîâ.

Ïî ïðàâèëó ñóììû ïîëó÷àåìyn = yn−1 + yn−2 ,n ≥ 3.Î÷åâèäíî, y1 = 1, y2 = 2! = 2. Çíà÷åíèå y0 íå èìååò ñîäåðæàòåëüíîãî ñìûñëà, íîäëÿ ïîëó÷åíèÿ òîé æå ïîñëåäîâàòåëüíîñòè 1, 1, 2, 3, 5, 8, 13, 21, . . . óäîáíî ïðèíÿòüñîãëàøåíèå y0 = 1.Ïðèìåð 5 . Ïóñòü zn êîëè÷åñòâî áèíàðíûõ âåêòîðîâ b1 . . .

bn äëèíû n, íåèìåþùèõ äâóõ è áîëåå íóëåé ïîäðÿä. Î÷åâèäíî, z1 = 2 , z2 = 3 (01, 10, 11). Ïóñòüb1 . . . bn òàêîé âåêòîð. Åñëè bn = 1, òî ýòîìó æå óñëîâèþ óäîâëåòâîðÿåò âåêòîðb1 . . . bn−1 . Åñëè æå bn = 0, òî bn−1 = 1 è óêàçàííîìó óñëîâèþ óäîâëåòâîðÿåòâåêòîð b1 . . . bn−2 . Ïî ïðàâèëó ñóììûzn = zn−1 + zn−2 ,n ≥ 3.×òîáû ïîëó÷èâøàÿñÿ ïîñëåäîâàòåëüíîñòü êàê ìîæíî ìåíüøå îòëè÷àëàñü îò ïðåäûäóùèõ, ñîãëàñèìñÿ, ÷òî z0 = 1 (ïîëó÷èì ïîñëåäîâàòåëüíîñòü 1, 2, 3, 5, 8, . . .).255Ëèíåéíûå ðåêóððåíòíûå óðàâíåíèÿ5.1Îäíîðîäíûå óðàâíåíèÿÓðàâíåíèåxn+p = ap−1 xn+p−1 + ap−2 xn+p−2 + · · · + a1 xn+1 + a0 xn(1)ëèíåéíûì îäíîðîäíûì ðåêóððåíòíûì óðàâíåíèåì ïîðÿäêà p äëÿ ïîñëåäîâàòåëüíîñòè x0, x1, .

. ..  ýòîì óðàâíåíèè íåèçâåñòíûìè ÿâëÿþòñÿ ÷ëåíû xníàçûâàåòñÿïîñëåäîâàòåëüíîñòè (òðåáóåòñÿ íàéòè ôîðìóëó äëÿ xn ), ÷èñëà a0 , . . . , ap−1 çàäàíû,îíè íàçûâàþòñÿ(1). Êîýôôèöèåíòû è íåèçâåñòíûåìîãóò áûòü ëþáûìè êîìïëåêñíûìè ÷èñëàìè, íî ñîäåðæàòåëüíûé ñìûñë, âàæíûéäëÿ çàäà÷ êîìáèíàòîðèêè, èìåþò öåëûå íåîòðèöàòåëüíûå ðåøåíèÿ. (Èç ïðèìåðîâ ïðåäûäóùåãî ðàçäåëà ëèíåéíûì îäíîðîäíûì ÿâëÿåòñÿ òîëüêî óðàâíåíèå (4).)Îïèøåì ìåòîä ðåøåíèÿ òàêèõ óðàâíåíèé.äëÿ óðàâíåíèÿ (1) èìååò âèäêîýôôèöèåíòàìè óðàâíåíèÿÕàðàêòåðèñòè÷åñêîå óðàâíåíèåtp = ap−1 tp−1 + ap−2 tp−2 + · · · + a1 t + a0 .(2)Ýòî àëãåáðàè÷åñêîå óðàâíåíèå ñòåïåíè p îòíîñèòåëüíî íåèçâåñòíîé t.

Îíî èìååòðîâíî p êîìïëåêñíûõ êîðíåé ñ ó÷åòîì êðàòíîñòè.Ïóñòü t1 , . . . , tm âñå êîðíè õàðàêòåðèñòè÷åñêîãî óðàâíåíèÿ (2), è îíè èìåþòêðàòíîñòè k1 , . . . , ks , k1 + · · · + km = p, ò. e. èìååò ìåñòî ðàçëîæåíèå íà ìíîæèòåëètp − ap−1 tp−1 − ap−2 tp−2 − · · · − a1 t − a0 = (t − t1 )k1 (t − t2 )k2 · · · (t − tm )km .Òîãäàîáùåå ðåøåíèå óðàâíåíè (1) îïèñûâàåòñÿ ôîðìóëîéxn =mXPj (n)tnj ,(3)j=1ãäå Pj (n) ìíîãî÷ëåíû îò n ñòåïåíè kj − 1, ò. å.Pj (n) = bj,kj −1 nkj −1 + bj,kj −2 nkj −2 + · · · + bj,1 n + bj,0 . ÷àñòíîñòè, åñëè tj êîðåíü êðàòíîñòè 1, òî Pj (n) åñòü ïîñòîÿííàÿ Cj . Míîãî÷ëåí Pj (n) ïîëíîñòüþ îïðåäåëÿåòñÿ ñâîèìè êîýôôèöèåíòàìè bj,kj −1 , bj,kj −2 ,. .

. ,bj,1 , bj,0 . Òàêèì îáðàçîì, îáùåå ðåøåíèå ñîäåðæèò ðîâíî p ïðîèçâîëüíûõ ïîñòîÿííûõ bj,kj −1 , bj,kj −2 ,. . . , bj,1 , bj,0 , j = 1, . . . , m. Åñëè âìåñòî âñåõ áóêâ bj,i ïîäñòàâèòüêîíêðåòíûå êîìïëåêñíûå ÷èñëà, òî ïîëó÷èì. Òàêèì îáðàçîì, èçîáùåãî ðåøåíèÿ ìîæíî ïîëó÷èòü áåñêîíå÷íîå ìíîæåñòâî ÷àñòíûõ ðåøåíèé. Äëÿ÷àñòíîå ðåøåíèå26íà-îäíîçíà÷íîãî îïðåäåëåíèÿ ÷àñòíîãî ðåøåíèÿ óðàâíåíèÿ ïîðÿäêà p çàäàþò p ÷èñëà x0 , x1 , . . . , xp−1 . Òîãäà íåèçâåñòíûå êîýôôèöèåíòû bj,iíàõîäÿòñÿ èç ñèñòåìû p ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé.Ïðèìåð 1.

Ðåøèì óðàâíåíèå÷àëüíûõ óñëîâèéxn+4 = −xn+3 + 3xn+2 + xn+1 − 2xnñ íà÷àëüíûìè óñëîâèÿìèx0 = 3,x1 = 2,x2 = 5,x3 = 4.Ýòî îäíîðîäíîå óðàâíåíèå ïîðÿäêà 4. Ñîñòàâèì õàðàêòåðèñòè÷åñêîå óðàâíåíèå:t4 = −t3 + 3t2 + t − 2.Èìååì ìíîãî÷ëåí ñòåïåíè 4 ñ öåëûìè êîýôôèöèåíòàìè f (t) = t4 + t3 − 3t2 −t + 2. Òðåáóåòñÿ íàéòè âñå åãî (âîçìîæíî, êîìïëåêñíûå) êîðíè.

Èçâåñòíî, ÷òîöåëûå êîðíè ìíîãî÷ëåíà ñ öåëûìè êîýôôèöèåíòàìè ÿâëÿþòñÿ äåëèòåëÿìè åãîñâîáîäíîãî êîýôôèöèåíòà.  íàøåì ñëó÷àå ñâîáîäíûé êîýôôèöèåíò −2 èìååòäåëèòåëè ±1, ±2. Ëåãêî âû÷èñëÿåì f (1) = 0. Ýòî çíà÷èò, t1 = 1 ÿâëÿåòñÿ êîðíåì.Ïî òåîðåìå Áåçó ìíîãî÷ëåí f (t) äåëèòñÿ íà t − 1. Ðàçäåëèâ, íàõîäèì ÷àñòíîåt3 + 2t2 − t − 2, ò. å.f (t) = (t − 1)(t3 + 2t2 − t − 2). Ìíîãî÷ëåí g(t) = t3 + 2t2 − t − 2 èìååò óæå ìåíüøóþ ñòåïåíü 3, åãî ñâîáîäíûéêîýôôèöèåíò −2 äåëèòñÿ, â ÷àñòíîñòè, íà 1. Ëåãêî âû÷èñëÿåì g(1) = 0, íàõîäèìêîðåíü t = 1 è, ðàçäåëèâ íà t − 1, ïðåäñòàâëÿåì g(t) = (t − 1)(t2 + 3t + 2), îòêóäàf (t) = (t − 1)g(t) = (t − 1)2 (t2 + 3t + 2).Äàëåå, t2 + 3t + 2 = (t + 1)(t + 2) èf (t) = (t − 1)2 (t + 1)(t + 2).Âñå êîðíè õàðàêòåðèñòè÷åñêîãî óðàâíåíèÿ åñòü t1 = 1, t2 = −1, t3 = −2, îíèèìåþò êðàòíîñòè k1 = 2, k2 = k3 = 1, ïîýòîìó îáùåå ðåøåíèå ðåêóððåíòíîãîóðàâíåíèÿ èìååò âèäxn = (An + B)1n + C(−1)n + D(−2)n(çäåñü äëÿ êðàòêîñòè ïåðåèìåíîâàíû êîýôôèöèåíòû, óêàçàííûå â ôîðìóëå (3):A = b11 , B = b10 , C = C2 , D = C3 ).

Êîýôôèöèåíòû A, B, C, D íàéäåì èç íà÷àëüíûõ óñëîâèé:x0x1x2x3=B= A +B= 2A +B= 3A +B+C +D = 3−C −2D = 2+C +4D = 5−C −8D = 427Ýòà ñèñòåìà ëèíåéíûõ óðàâíåíèé èìååò åäèíñòâåííîå ðåøåíèå A = 1, B = 2,C = 1, D = 0, ïîýòîìó ÷àñòíûì ðåøåíèåì, óäîâëåòâîðÿþùèì çàäàííûì íà÷àëüíûì óñëîâèÿì, ÿâëÿåòñÿ xn = n + 2 + (−1)n .Îòâåò: xn = n + 2 + (−1)n .Ïðèìåð 2. Ðåøèì çàäà÷ó Ôèáîíà÷÷èxn+2 = xn+1 + xn ,x0 = x1 = 1.Óðàâíåíèå îäíîðîäíîå ïîðÿäêà 2. Õàðàêòåðèñòè÷åñêîå óðàâíåíèå t2 = t + 1 èìååòêîðíè√√1− 51+ 5, t2 =22êðàòíîñòè 1, îáùåå ðåøåíèå èìååò âèä xn = C1 tn1 + C2 tn2 . Íà÷àëüíûå óñëîâèÿçàäàþò ñèñòåìó óðàâíåíèét1 =√ C1√ +C2 = 1(1 − 5)C1 +(1 + 5)C2 = 2Ðåøàÿ åå è ïîäñòàâëÿÿ C1 , C2 â ôîðìóëó îáùåãî ðåøåíèÿ, íàõîäèì ïîñëå ýëåìåíòàðíûõ ïðåîáðàçîâàíèé ÷àñòíîå ðåøåíèå â êðàñèâîì âèäå√ !n+11  1+ 5xn = √−25√ !n+11− 5.2Ôîðìóëà ñîäåðæèò èððàöèîíàëüíîñòè, íî âñå ÷ëåíû ïîñëåäîâàòåëüíîñòè Ôèáîíà÷÷è, âû÷èñëÿåìûå ïî íåé (ñ ïðèìåíåíèåì ôîðìóëû áèíîìà), öåëûå.

Ìîæíîïðè íàëè÷èè òåðïåíèÿ â ýòîì óáåäèòüñÿ ïðè íåáîëüøèõ çíà÷åíèÿõ n. Ïðîäåëàâòàêèå îïûòû, íåòðóäíî ïîíÿòü, ÷òî äëÿ íàõîæäåíèÿ ÷ëåíîâ ïîñëåäîâàòåëüíîñòèïðîùå èñïîëüçîâàòü ðåêóððåíòíîå óðàâíåíèå, ÷åì âûâåäåííóþ òîëüêî ÷òî ôîðìóëó. Ýòî õàðàêòåðíî äëÿ ìíîãèõ äðóãèõ êîìáèíàòîðíûõ ÷èñåë è ïîêàçûâàåò ïîëüçóðåêóððåíòíûõ óðàâíåíèé.5.2Íåîäíîðîäíûå óðàâíåíèÿ, ñâîäÿùèåñÿ ê îäíîðîäíûìÍåîäíîðîäíîå ëèíåéíîå ðåêóððåíòíîå óðàâíåíèå âèäàxn+p = ap−1 xn+p−1 + ap−2 xn+p−2 + · · · + a1 xn+1 + a0 xn + b,(4)ãäå b 6= 0 ÷èñëîâîé êîýôôèöèåíò, â áîëüøîì ÷èñëå ñëó÷àåâ ìîæíî ñâåñòè ê îäíîðîäíîìó ëèíåéíîé çàìåíîé ïåðåìåííûõ (ìåòîä ïðèìåíÿåòñÿ äëÿ ðåøåíèÿ ìíîãèõóðàâíåíèé â ðàçëè÷íûõ îáëàñòÿõ ìàòåìàòèêè).

Ïðîäåìîíñòðèðóåì ìåòîä çàìåíûïåðåìåííûõ íà ïðèìåðå.28Ïðèìåð 3.Ðàññìîòðèì óðàâíåíèå ñ íà÷àëüíûìè óñëîâèÿìèxn+2 = 4xn + b,x0 = 1,x1 = 6.Äëÿ âñåõ n = 0, 1, 2, . . . ïîëîæèì xn = yn + γ , ãäå ïîñòîÿííàÿ γ ïîêà íåèçâåñòíà.Ïîäñòàâèì ýòè âûðàæåíèÿ â èñõîäíîå óðàâíåíèå:yn+2 + γ = 4(yn + γ) + b,îòêóäàyn+2 = 4yn + (3γ + b).Óðàâíåíèå äëÿ ÷èñåë yn ñòàíåò îäíîðîäíûì, åñëè 3γ + b = 0, ò. å. γ = −b/3. Ïðèòàêîì âûáîðå γ íàõîäèì îáùåå ðåøåíèå îäíîðîäíîãî óðàâíåíèÿ yn+2 = 4yn :yn = C1 (−2)n + C2 2n ,îòêóäàxn = C1 (−2)n + C2 2n − b/3.Íàéäåì C1 , C2 èç íà÷àëüíûõ óñëîâèé. Ðåøàÿ ñèñòåìó óðàâíåíèéC1 +C2 −b/3 = 1−2C1 +2C2 −b/3 = 6,ïîëó÷èì C1 = −1 + b/12, C2 = 2 + b/4 è òîãäàxn = (−1 + b/12)(−2)n + (2 + b/4)2n − b/3.Çàäàíèÿ äëÿ ñàìîñòîÿòåëüíîãî ðåøåíèÿ4.

Ðåøèòå îäíîðîäíîå ðåêóððåíòíîå óðàâíåíèå ñ íà÷àëüíûìè óñëîâèÿìèxk+3 = (N − 2)xk+2 + (2N − 1)xk+1 + N xk , x0 = 2, x1 = 2N + 1, x2 = 2N 2 − 2.5. Ðåøèòå íåîäíîðîäíîå ðåêóððåíòíîå óðàâíåíèå ñ íà÷àëüíûì óñëîâèåìxk+1 = (N + 2)xk + N,Íîìåð âàðèàíòàNx0 = N − 1.îñòàåòñÿ òàêèì æå, êàê â ïðåäûäóùèõ çàäàíèÿõ.Ðåøåíèÿ ïðèñûëàéòå ïî ïðåæíåìó àäðåñó MeshchaninovDG@mpei.ruÌåùàíèíîâó Äìèòðèþ Ãåðìàíîâè÷ó296Ìåòîä âêëþ÷åíèé-èñêëþ÷åíèéÎí ÷àñòî ïðèìåíÿåòñÿ äëÿ ðåøåíèÿ çàäà÷ íå òîëüêî â êîìáèíàòîðèêå è äèñêðåòíîé ìàòåìàòèêå, íî è â äðóãèõ îáëàñòÿõ.Ïðèìåð 1. Áóäåì îáîçíà÷àòü ñèìâîëàìè |M | ÷èñëî ýëåìåíòîâ êîíå÷íîãî ìíîæåñòâà M .

Êàê íàéòè |A ∪ B|? Ôîðìóëà |A ∪ B| = |A| + |B| â îáùåì ñëó÷àåíåâåðíà, íåêîòîðûå ýëåìåíòû ìîãóò ïðèíàäëåæàòü îáîèì ìíîæåñòâàì A è B , âòàêîé ôîðìóëå îíè ó÷òåíû äâàæäû. Ïðàâèëüíîé ÿâëÿåòñÿ ôîðìóëà|A ∪ B| = |A| + |B| − |A ∩ B|.(1)Àíàëîãè÷íî ïîñòàâèì âîïðîñ î âû÷èñëåíèè |A ∪ B ∪ C|. Ïîëîæèì D = A ∪ B .Òîãäà x = |A ∪ B ∪ C| = |D ∪ C| è, ñîãëàñíî (1), íàõîäèì x = |D| + |C| − |D ∩ C|.Ïîäñòàâèì ñþäà D = A ∪ B è ñíîâà ïðèìåíèì (1):x = |A| + |B| − |A ∩ B| + |C| − |(A ∪ B) ∩ C| == |A| + |B| − |A ∩ B| + |C| − |(A ∩ C) ∪ (B ∩ C)| == |A| + |B| − |A ∩ B| + |C| − (|A ∩ C| + |B ∩ C| − |A ∩ B ∩ C|.Îêîí÷àòåëüíî ïîëó÷àåì|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.