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

. . , en } ìíîæåñòâîýëåìåíòîâ, ýëåìåíòû êàæäîãî òèïàèìåþòñÿ â íåîãðàíè÷åííîì êîëè÷åñòâå. Ðàññìîòðèì ñîâîêóïíîñòü èç k ýëåìåíòîâ,êàæäûé ýëåìåíò èìååò òèï èç ìíîæåñòâà U . Óïîðÿäî÷åííàÿ òàêàÿ ñîâîêóïíîñòüíàçûâàåòñÿ, íåóïîðÿäî÷åííàÿ kn. Äëÿ ÷èñëà ðàçìåùåíèé è ñî÷åòàíèé ñ ïîkâòîðåíèÿìè ïðèíÿòû îáîçíà÷åíèÿ Ân è, ñîîòâåòñòâåííî, Ĉnk .Òåîðåìà 8.òèïîâðàçìåùåíèåì ñ ïîâòîðåíèÿìèâòîðåíèÿìè ïî ýëåìåíòîâ òèïîâñî÷åòàíèåì ñ ïî-×èñëî ðàçìåùåíèé ñ ïîâòîðåíèÿìè îïðåäåëÿåòñÿ ôîðìóëîéÂkn = nk .Äîêàçàòåëüñòâî.Êàæäîå èç ìåñò âûáîðêè ìîæíî çàïîëíèòü ðîâíî n ñïîñîáàìè (ýëåìåíòîì ëþáîãî òèïà e1 , .

. . , en ). Çàïîëíèòü íàäî âñå k ìåñò. Îñòàåòñÿïðèìåíèòü ïðàâèëî ïðîèçâåäåíèÿ. Çàìå÷àíèå. Pàçìåùåíèÿ ñ ïîâòîðåíèÿìè ïî k ýëåìåíòîâ n òèïîâ âçàèìíîîäíîçíà÷íî ñîîòâåòñòâóþò ñëîâàì äëèíû k â àëôàâèòå ìîùíîñòè n. (Îáðàòèòåâíèìàíèå, ÷òî ñèìâîëû n è k ïîìåíÿëèñü ðîëÿìè, è íå ïóòàéòå!)20×èñëî ñî÷åòàíèé ñ ïîâòîðåíèÿìè âûðàæàåòñÿ ÷åðåç ÷èñëî ñî÷åòàíèé áåç ïîâòîðåíèé ôîðìóëàìèÒåîðåìà 9.kn−1Ĉnk = Cn+k−1= Cn+k−1.Äîêàçàòåëüñòâî.Ïóñòü B ñî÷åòàíèå ïî k ýëåìåíòîâ n òèïîâ. Îíî îäíîçíà÷íî îïðåäåëÿåòñÿ âåêòîðîì (x1 , . . .

, xn ), ãäå xj ÷èñëî âõîæäåíèÿ â B ýëåìåíòàòèïà ej :B ↔ (x1 , . . . , xn ),nXxj = k,xj ≥ 0.j=1Ïîëîæèì yj = xj +1, òîãäà ñî÷åòàíèþ B âçàèìíî îäíîçíà÷íî ñîîòâåòñòâóåò âåêòîðY = (y1 , . . . , yn ),yj ∈ N,nXyj =j=1nXj=1(xj + 1) =nXxj + k = n + k.j=1Êîëè÷åñòâî ñî÷åòàíèé ðàâíî êîëè÷åñòâó òàêèõ âåêòîðîâ Y , à îíî ðàâíî êîëè÷åñòâó ðàçáèåíèé n + k = y1 + · · · + yn ÷èñëà n + k ∈ N â ñóììó n íàòóðàëüíûõ ñëàãàåìûõ. Íàéäåì åãî. Áóäåì (êàê äðåâíèå ëþäè èëè ìàëåíüêèå äåòè) ïðåäñòàâëÿòüíàòóðàëüíîå ÷èñëî m ðÿäîì èç m òî÷åê.

Ðàçáèåíèå òàêîãî ÷èñëà íà q ñëàãàåìûõïðåäñòàâëÿåòñÿ q − 1 ïåðåãîðîäêàìè (ïàëî÷êàìè) ìåæäó òî÷êàìè. Ãðóïïû íåðàçäåëåííûõ òî÷åê ñîîòâåòñòâóþò ñëàãàåìûì, íàïðèìåð, ðàçáèåíèå 7 = 3 + 2 + 1 + 1ìîæíî ïðåäñòàâèòü êàê · · ·| · ·| · |· . Êîëè÷åñòâî òðåáóåìûõ ðàçáèåíèé ýòî êîëè÷åñòâî ñïîñîáîâ ïîñòàâèòü n − 1 ïàëî÷åê ìåæäó n + k òî÷êàìè. Ïàëî÷êè ñòàâÿòñÿâ ïðîìåæóòêè ìåæäó òî÷êàìè, ÷èñëî ïðîìåæóòêîâ åñòü n + k − 1, ÷èñëî ñïîñîáîân−1 Cn+k−1.Ïðèìåð Ëþäè, íå èãðàþùèå â äîìèíî, ìîãóò íå çíàòü îñîáåííîñòè ýòîé èãðû,â ÷àñòíîñòè, ñêîëüêî â äîìèíî êîñòåé.

Íàéäåì ýòî ÷èñëî. Êîñòü ìîæíî ïðåäñòàâèòü êàê íåóïîðÿäî÷åííóþ (êîñòü ìîæíî ïåðåâåðíóòü) ïàðó {x1 , x2 }, ãäå x1 , x2 êîëè÷åñòâî î÷êîâ íà ïîëîâèíêå êîñòè, x1 , x2 ∈ {0, 1, . . . 6}. ×èñëî 0 èçîáðàæàåòñÿ ïóñòûì êâàäðàòîì, îñòàëüíûå ÷èñëà ñîîòâåòñòâóþùèì êîëè÷åñòâîì òî÷åê.Òàêèì îáðàçîì, U = {0, 1, . . . 6}, è ÷èñëî êîñòåé äîìèíî åñòü2Ĉ72 = C7+2−1= C82 = 8 · 7/2 = 28.214Ðåêóððåíòíûå óðàâíåíèÿÂî ìíîãèõ êîìáèíàòîðíûõ çàäà÷àõ èñêîìûå ÷èñëà ÿâëÿþòñÿ ÷ëåíàìè íåêîòîðîéïîñëåäîâàòåëüíîñòè, ìåæäó êîòîðûìè çàäàíî èëè âûâîäèòñÿ ñîîòíîøåíèå, íàçûâàåìîå.  îáùåì ñëó÷àå ðåêóððåíòíîå óðàâíåíèå äëÿ ÷ëåíîâïîñëåäîâàòåëüíîñòè x0 , x1 , .

. . , xn , xn+1 , . . .èìååò âèäðåêóððåíòíûìF (xn , xn−1 , . . . , x0 ) = 0.Ðåêóððåíòíûå óðàâíåíèÿ íàçûâàþòñÿ òàêæå âîçâðàòíûìè (ýòîò òåðìèí îòðàæàåòãëàâíîå ñâîéñòâî ÷ëåíîâ ïîñëåäîâàòåëüíîñòè).  èíôîðìàòèêå ðåêóððåíòíîñòèâûðàæàþòñÿ ðåêóðñèâíûìè ïðîöåäóðàìè, ãëàâíûì ñâîéñòâîì êîòîðûõ ÿâëÿåòñÿñàìîïðèìåíèìîñòü.

Âûçîâ òàêîé ïðîöåäóðû èç ñåáÿ íàçûâàåòñÿ ðåêóðñèåé.Ðàññìîòðèì ðÿä ïðèìåðîâ, â êîòîðûõ ìû âûâåäåì, à â ðÿäå ñëó÷àåâ è ðåøèì(ò. e. íàéäåì âñå ÷èñëà ïîñëåäîâàòåëüíîñòè) ðåêóððåíòíûå óðàâíåíèÿ.Ïðèìåð 1 (çàäà÷à î ðàçðåçàíèè ïèööû). Ïèööà ðàçðåçàåòñÿ n ïðÿìîëèíåéíûìè äâèæåíèÿìè íîæà, ïðè êîòîðûõ êàæäûå äâå ëèíèè ðàçðåçà ïåðåñåêàþòñÿ, íî íèêàêèå òðè íå ïåðåñåêàþòñÿ â îäíîé òî÷êå. Ñêîëüêî êóñêîâ ïèööûîáðàçóåòñÿ? Ìîæíî àáñòðàãèðîâàòüñÿ îò ôîðìû è ðàçìåðà ïèööû è ñôîðìóëèðîâàòü çàäà÷ó íà ìàòåìàòè÷åñêîì ÿçûêå: íà ñêîëüêî ÷àñòåé äåëÿò ïëîñêîñòü nïðÿìûõ, èç êîòîðûõ ëþáûå äâå ïåðåñåêàþòñÿ, íî íèêàêèå òðè íå ïåðåñåêàþòñÿ âîäíîé òî÷êå?Ïóñòü xn ÷èñëî òàêèõ ÷àñòåé.

ßñíî, ÷òî x0 = 1, x1 = 2, x2 = 4. Èñõîäÿ èçýòèõ óñëîâèé, ïðèìåíèì èíäóêöèþ.  ìåòîäå ìàòåìàòè÷åñêîé èíäóêöèè ãëàâíîå èíäóêòèâíûé ïåðåõîä.Ïóñòü ïðîâåäåíû n ïðÿìûõ a1 , . . . , an . Ïðîâåäåì ñëåäóþùóþ, (n + 1)-óþ ïðÿìóþ b. Ïî óñëîâèþ îíà ïåðåñåêàåòñÿ ñ ïðÿìûìè a1 , . . . , an . Ðàññìîòðèì òî÷êèïåðåñå÷åíèÿ A1 , . . . , An . Ýòè n òî÷åê äåëÿò ïðÿìóþ b íà n + 1 ÷àñòåé, êàæäàÿ èçêîòîðûõ ïðèíàäëåæèò ñâîåé íîâîé ÷àñòè ïëîñêîñòè.

Òàêèì îáðàçîì, êîëè÷åñòâî÷àñòåé óâåëè÷èëîñü íà n + 1. Ïîëó÷åíî óðàâíåíèåxn+1 = xn + n + 1(1)ñ óñëîâèåì (îíî íàçûâàåòñÿ íà÷àëüíûì)x0 = 1.Ðåøèì óðàâíåíèå. Ïîñëåäîâàòåëüíî ïðèìåíÿÿ ôîðìóëó (1), ïîëó÷èìxn = xn−1 + n = xn−2 + (n − 1) + n = xn−3 + (n − 2) + (n − 1) + n == · · · = x0 + (1 + 2 + · · · + n).22(2)Èñïîëüçóÿ (2) è ôîðìóëó äëÿ ñóììû ïåðâûõ n ÷ëåíîâ àðèôìåòè÷åñêîé ïðîãðåññèè, îêîí÷àòåëüíî íàõîäèìxn = 1 + n(n − 1)/2.Ïðèìåð 2 (çàäà÷à î õàíîéñêîé áàøíå). Èìååòñÿ n êîëåö ðàçìåðîâ 1, 2, . . . ,n, íàíèçàííûõ íà âåðòèêàëüíûé ñòåðæåíü A, â âèäå ïèðàìèäêè ñ óìåíüøàþùèìèñÿ ñíèçó ââåðõ ðàçìåðàìè êîëåö.

Èìååþòñÿ òàêæå åùå äâà ñòåðæíÿ B è C áåçêîëåö. Òðåáóåòñÿ ïåðåìåñòèòü âñå êîëüöà ñî ñòåðæíÿ A íà C , èñïîëüçóÿ ñòåðæåíü B òàê, ÷òîáû â ëþáîé ìîìåíò íèêàêîå áîëüøåå êîëüöî íå íàõîäèëîñü âûøåìåíüøåãî. Ñêîëüêî îïåðàöèé ïåðåêëàäûâàíèÿ äîñòàòî÷íî ñäåëàòü?Ïóñòü xn îïòèìàëüíîå ÷èñëî îïåðàöèé. ßñíî, ÷òî x0 = 0, x1 = 1. Íàðèñîâàâñòåðæíè, íåòðóäíî ïîäñ÷èòàòü x2 = 3 è äàæå, ïðîÿâèâ òåðïåíèå, x3 = 7.

Îñíîâíàÿèäåÿ ïðè ïðîâåäåíèè òàêèõ îïåðàöèé, ñîñòîèò â ñëåäóþùåì. ×òîáû âûïîëíÿëîñüóñëîâèå íà ðàñïîëîæåíèå êîëåö ïî ðàçìåðàì, ïðè ëþáîì ñïîñîáå ðåøåíèÿ ïðèäåòñÿ ñíà÷àëà ïåðåìåñòèòü âåðõíèå n − 1 êîëåö ñî ñòåðæíÿ A íà B , èñïîëüçóÿ êàêâñïîìîãàòåëüíûé ñòåðæåíü C , ïîñëå ÷åãî ñàìîå áîëüøîå êîëüöî ðàçìåðà n ïåðåêëàäûâàåòñÿ ñ A íà C , à çàòåì îñòàëüíûå n − 1 êîëåö ïåðåêëàäûâàþòñÿ ñ B íà Cñ èñïîëüçîâàíèåì â êà÷åñòâå âñïîìîãàòåëüíîãî ñòåðæíÿ A.

Èç ýòèõ ñîîáðàæåíèéïîëó÷àåì óðàâíåíèåxn = 2xn−1 + 1(3)ñ íà÷àëüíûì óñëîâèåì x0 = 0. Ïîêàæåì, êàê ìîæíî åãî ðåøèòü. Ñäåëàåì çàìåíó ïåðåìåííîé (ðàñïðîñòðàíåííûé ïðèåì ïðè ðåøåíèè ìíîãèõ âèäîâ óðàâíåíèé)xn = yn − 1. Òîãäà yn − 1 = xn = 2xn−1 = 2(yn−1 − 1) + 1,yn = 2yn−1 ,y0 = 1,îòêóäà yn = 2n , xn = 2n − 1.Ýòó çàäà÷ó ïðèäóìàë â 1883 ã. êàê ãîëîâîëîìêó ôðàíöóçñêèé èíæåíåð ÝäóàðäËþêà íà îñíîâå âîñòî÷íîé ëåãåíäû î òîì, ÷òî Áóääà ïîâåëåë æðåöàì ïðîâåñòèòàêîå ïåðåêëàäûâàíèå 64 çîëîòûõ êîëåö, èç êîòîðûõ ïîñòðîåíà áàøíÿ â ãîðîäåÕàíîå.

Æðåöû òðóäÿòñÿ äåíü è íî÷ü âîò óæå íåñêîëüêî òûñÿ÷åëåòèé, íî êîíöàèõ ðàáîòå, êàê ìû òåïåðü çíàåì, â îáîçðèìîì áóäóùåì íå ïðåäâèäèòñÿ.Ïðèìåð 3. Îí óæå áûë ðàññìîòðåí â ðàçä. 1. Åñëè xn êîëè÷åñòâî äåñÿòè÷íûõ öåëûõ ÷èñåë îò 0 äî 10n , íå ñîäåðæàùèõ íàõîäÿùèõñÿ ïî ñîñåäñòâó îäèíàêîâûõ öèôð, òî äëÿ äëÿ ïîñëåäîâàòåëüíîñòè x0 , x1 , x2 , . . . ïîëó÷àåì ðåêóððåíòíîåóðàâíåíèå ñ íà÷àëüíûì óñëîâèåìxn+1 = xn + 9n+1 ,x0 = 1.Èñïîëüçóÿ ôîðìóëó ñóììû ãåîìåòðè÷åñêîé ïðîãðåññèè ñî çíàìåíàòåëåì 9, íàõîäèì xn = (9n+1 − 1)/8.23Ïðèìåð 4 (çàäà÷à î ïðîçâîíêå êàáåëÿ).Èìååòñÿ êàáåëü, ñîñòîÿùèé èçN ïðîâîäîâ.

Òðåáóåòñÿ íàéòè ñîîòâåòñòâèå ìåæäó ïðîâîäàìè íà ëåâîì è ïðàâîìêîíöàõ êàáåëÿ ("ïðîçâîíèòü" åãî) çà ìèíèìàëüíîå ÷èñëî îïûòîâ xN .Ðàññìîòðèì òàêîé àëãîðèòì (îí ïðèìåíÿåòñÿ è äëÿ äðóãèõ çàäà÷, â ÷àñòíîñòè,äëÿ ñîðòèðîâêè). Ïðåäïîëîæèì, ÷òî N åñòü ñòåïåíü äâîéêè. Ðàçäåëèì ìíîæåñòâîèç N ïðîâîäîâ íà ëåâîì êîíöå êàáåëÿ íà äâå ðàâíûå ÷àñòè (ñâÿæåì N/2 ïðîâîäîâ).Òåïåðü íà ëåâîì êîíöå êàáåëÿ äâå ñâÿçêè, íà ïðàâîì N ïðîâîäîâ. Ïðîçâîíèìîäíó ñâÿçêó íà ëåâîì êîíöå ñ êàæäûì èç N ïðîâîäîâ íà ïðàâîì êîíöå è íàéäåìñîîòâåòñòâèå. Äàëåå ðàçäåëèì êàæäóþ èç ñâÿçîê ëåâîãî êîíöà ïîïîëàì åùå ðàç,ïðèäåì ê äâóì àíàëîãè÷íûì çàäà÷àì ñ ïàðàìåòðîì N/2. Òàêèì îáðàçîì,xN = 2xN/2 + N.Ýòîìó ðåêóððåíòíîìó óðàâíåíèþ óäîâëåòâîðÿåò, êàê íåòðóäíî ïðîâåðèòü, ïîñëåäîâàòåëüíîñòü xN = N log2 N .

(Êàê íàéòè òàêîå ðåøåíèå ýòî îòäåëüíàÿ çàäà÷à,íå áóäåì åå ðàññìàòðèâàòü.) Íåòðóäíî ïîíÿòü, ÷òî îãðàíè÷åíèå N = 2m íå ÿâëÿåòñÿ ïðèíöèïèàëüíûì, íà êàæäîì øàãå ìîæíî äåëèòü ìíîæåñòâî íå òî÷íî, àïðèìåðíî ïîïîëàì, ñóòü ïðîöåññà íå èçìåíèòñÿ. Ìîæíî ïîêàçàòü, ÷òî ïîðÿäîê ðîñòà N log N ôóíêöèè xN ïðè N → ∞ ÿâëÿåòñÿ îïòèìàëüíûì. Äëÿ ýòîãî çàìåòèì,÷òî âñåãî âîçìîæíî N ! âàðèàíòîâ ñîîòâåòñòâèÿ ìåæäó N ïðîâîäàìè íà ëåâîì èN ïðîâîäàìè íà ïðàâîì êîíöàõ êàáåëÿ.

Îäèí îïûò ïðîçâîíêè èìååò äâà èñõîäà: óñïåõ (ñîîòâåòñòâèå ìåæäó îäíèì ïðîâîäîì ñëåâà è îäíèì ïðîâîäîì ñïðàâàîáíàðóæåíî) è íåóäà÷ó. Ïóñòü K ÷èñëî îïåðàöèé ïðîçâîíêè. Òîãäà 2K ≥ N !.Èñïîëüçóÿ ôîðìóëó Ñòèðëèíãà N ! ∼ CN N ïðè N → ∞, ãäå C íåêîòîðàÿïîñòîÿííàÿ, óáåæäàåìñÿ, ÷òî K ≥ N log2 N + log2 C .Ïðèìåð 5 (çàäà÷à î êðîëèêàõ Ôèáîíà÷÷è). Èìååòñÿ ïàðà íîâîðîæäåííûõ êðîëèêîâ, ñàìåö è ñàìêà. Êðîëèêè âçðîñëåþò 2 ìåñÿöà, à çàòåì íà÷èíàþòïëîäèòüñÿ: êàæäûé ìåñÿö îíè ðîæäàþò åùå ïàðó, òàêæå ñàìöà è ñàìêó. C íèìèïðîèñõîäèò òî æå ñàìîå: îíè äâà ìåñÿöà âçðîñëåþò, à çàòåì êàæäûé ìåñÿö ðîæäàþò ïàðó èç ñàìöà è ñàìêè, êîòîðûå ÷åðåç äâà ìåñÿöà íà÷èíàþò ïëîäèòüñÿ òåì æåîáðàçîì.

Òàê è ïðîèñõîäèò íåîãðàíè÷åííîå ðàçìíîæåíèå êðîëèêîâ, ñìåðòíîñòèñðåäè íèõ àáñîëþòíî íèêàêîé íåò.  ðåàëüíîé æèçíè ýòî íåâîçìîæíî, íî êàê ìîäåëü âïîëíå êðàñèâî. Çàäà÷ó îïèñàë è ïðîàíàëèçèðîâàë â XIII â. ìîíàõ ËåîíàðäîÔèáîíà÷÷è èç ã. Ïèçà. Çàäà÷à ñîñòîèò â íàõîæäåíèè êîëè÷åñòâà xn ïàð êðîëèêîâ÷åðåç n ìåñÿöåâ îò äàòû ðîæäåíèÿ íà÷àëüíîé ïàðû. (Ïîçäíåå ïîÿâèëîñü íàçâàíèå"÷èñëà Ôèáîíà÷÷è". Óäèâèòåëüíî, ÷òî îíè ïðîÿâëÿþòñÿ â îãðîìíîì ìíîæåñòâåñàìûõ ðàçíîîáðàçíûõ ÿâëåíèé è ñèòóàöèé è òåñíî ñâÿçàíû ñ íå ìåíåå èçâåñòíûìêîëè÷åñòâåííûì ñîîòíîøåíèåì, íàçûâàåìûì "çîëîòûì ñå÷åíèåì".) ×èñëà Ôèáîíà÷÷è îáëàäàþò ìíîãî÷èñëåííûìè çàìå÷àòåëüíûìè è êðàñèâûìè ñâîéñòâàìè (ñì.Âîðîáüåâ Í.Í. ×èñëà Ôèáîíà÷÷è Ì.: Íàóêà, 1984), ìû ïîêàæåì, êàê èõ íàéòè.24Èòàê, x0 = x1 = 1 (äâà ïåðâûõ ìåñÿöà êðîëèêè âçðîñëåþò). Íî äàëåå ïîëó÷àåìx2 = 2 (íà÷àëüíàÿ ïàðà ðàçìíîæèëàñü âïåðâûå), x3 = 3 (íà÷àëüíàÿ ïàðà ðàçìíîæèëàñü óæå äâàæäû, à êðîëèêè, ðîæäåííûå â ïðîøëîì ìåñÿöå, åùå íå âûðîñëè),x4 = 5 (ñòàëà ðàçìíîæàòüñÿ è âòîðàÿ ïàðà), àíàëîãè÷íî x5 = 8, x6 = 13, x7 = 21è âîîáùå óñëîâèÿ çàäà÷è îïèñûâàþòñÿ ðåêóððåíòíûì óðàâíåíèåìxn = xn−1 + xn−2 ,n ≥ 2,(4)ñ íà÷àëüíûìè óñëîâèÿìèx0 = x1 = 1.(5)Ïðèâåäåì åùå äâå ñîäåðæàòåëüíûå êîìáèíàòîðíûå çàäà÷è, îïèñûâàåìûå òåì æåñàìûì óðàâíåíèåì (4).Ïðèìåð 5'.