Дискретная математика

1 1.1 Ââåäåíèå Î ïðåäìåòå è ñîäåðæàíèè êóðñà Ñëîâî "äèñêðåòíûé" ÿâëÿåòñÿ ïðîòèâîïîëîæíûì ïî çíà÷åíèþ ñëîâó "íåïðeðûâíûé", à íåïðåðûâíûìè ìîãóò áûòü òîëüêî áåñêîíå÷íûå îáðàçîâàíèÿ. Äèñêðåòíàÿ ìàòåìàòèêà èìååò äåëî ñ êîíå÷íûìè îáúåêòàìè: êîíå÷íûìè ìíîæåñòâàìè è èõ ïðåîáðàçîâàíèÿìè (ôóíêöèÿìè, îïðåäåëåííûìè íà êîíå÷íûõ ìíîæåñòâàõ è ïðèíèìàþùèìè êîíå÷íûå ìíîæåñòâà çíà÷åíèé). Ýëåìåíòû êîíå÷íûõ ìíîæåñòâ ìîæíî îáîçíà÷àòü öåëûìè ÷èñëàìè, ïîýòîìó ìîæíî ñêàçàòü, ÷òî äèñêðåòíàÿ ìàòåìàòèêà îïåðèðóåò öåëûìè ÷èñëàìè, ðåçóëüòàòû âñåõ âû÷èñëåíèé  öåëûå ÷èñëà. Èñòîðè÷åñêè íåîòðèöàòåëüíûå öåëûå ÷èñëà ïîÿâèëèñü ðàíüøå âñåõ îñòàëüíûõ, îíè âûðàæàþò êîëè÷åñòâî ýëåìåíòîâ ìíîæåñòâà. Òàê ïðèøëè ê ïîíÿòèþ íàòóðàëüíîãî ÷èñëà äðåâíèå ëþäè, òàê ó÷àò ìàëåíüêèõ äåòåé, ïîêàçûâàÿ è ñðàâíèâàÿ ìíîæåñòâà ñíà÷àëà îäèíàêîâûõ ïðåäìåòîâ (ïàëî÷åê, êóáèêîâ, øàðèêîâ), à çàòåì è ðàçíîðîäíûõ. Ïîçæå ïîíÿòèå ÷èñëà ðàñøèðÿåòñÿ â ñâÿçè ñ ïðàêòè÷åñêèìè äåéñòâèÿìè  ñ÷åòîì, àðèôìåòè÷åñêèìè îïåðàöèÿìè è îáðàòíûìè ê íèì. ×èñëî 0 íå èçìåíÿåò èñõîäíîå ïðè ñëîæåíèè, îòðèöàòåëüíûå ÷èñëà ïîÿâëÿþòñÿ ïðè âûïîëíåíèè âû÷èòàíèÿ, äåéñòâèÿ, îáðàòíîãî ñëîæåíèþ. Ðàöèîíàëüíûå ÷èñëà  ðåçóëüòàò äåëåíèÿ, äåéñòâèÿ, îáðàòíîãî óìíîæåíèþ. Èððàöèîíàëüíûå è êîìïëåêñíûå ÷èñëà  ðåçóëüòàò èçâëå÷åíèÿ êîðíåé, äåéñòâèé, îáðàòíûõ âîçâåäåíèþ â ñòåïåíü. Äàæå øêîëüíèêè ìîãóò óáåäèòüñÿ, ÷òî çàäà÷è ñ öåëî÷èñëåííûì ïî ñìûñëó ðåçóëüòàòîì äîâîëüíî ñèëüíî îòëè÷àþòñÿ îò àíàëîãè÷íûõ çàäà÷ áåç òàêîãî îãðàíè÷åíèÿ: óðàâíåíèÿ, íåðàâåíñòâà è èõ ñèñòåìû ìîãóò íå èìåòü ðåøåíèÿ è, íàïðîòèâ, ðåøåíèå âñåãî ëèøü îäíîãî óðàâíåíèÿ ñ íåñêîëüêèìè íåèçâåñòíûìè ìîæåò áûòü åäèíñòâåííûì.  äèñêðåòíîé ìàòåìàòèêå, â ñèëó êîíå÷íîñòè ðàññìàòðèâàåìûõ ìíîæåñòâ, íåâîçìîæåí ïðåäåëüíûé ïåðåõîä è, ñëåäîâàòåëüíî, íåïðèìåíèìû îñíîâàííûå íà ïîíÿòèè ïðåäåëà ìåòîäû äèôôåðåíöèàëüíîãî è èíòåãðàëüíîãî èñ÷èñëåíèÿ. Íåîáõîäèìû èíûå ïîäõîäû, îáóñëîâëåííûå ñïåöèôèêîé äèñêðåòíûõ çàäà÷, è ñèñòåìàòèçàöèÿ èõ â îñîáîì ðàçäåëå ìàòåìàòèêè.  ÕÕ âåêå äèñêðåòíàÿ ìàòåìàòèêà ïîëó÷èëà äîïîëíèòåëüíûé ñòèìóë ê ðàçâèòèþ â ñâÿçè ñ ïîÿâëåíèåì è øèðîêèì ïðèìåíåíèåì öèôðîâîé òåõíèêè. Ëþáîå òàêîå óñòðîéñòâî êîíå÷íî, è â íåì öèôðàìè ìîæíî ïðåäñòàâèòü ëèøü êîíå÷íîå ìíîæåñòâî ÷èñåë, êàê áû âåëèêî îíî íè áûëî. Ýòèì ñõîæè è ïðîñòåéøèé äðåâíèé âû÷èñëèòåëüíûé èíñòðóìåíò àáàê (ñ÷åòû), è ñîâðåìåííûé ñóïåðêîìïüþòåð. Îäíàêî íå ñëåäóåò ïðîòèâîïîñòàâëÿòü äèñêðåòíóþ è íåïðåðûâíóþ ìàòåìàòèêó. Îíè, êàê áóäåò âèäíî, íàõîäÿòñÿ â òåñíîé âçàèìîñâÿçè, ìåòîäû îäíîé ïðèìåíÿþòñÿ êàê èíñòðóìåíò â äðóãîé, èõ òðóäíî ðàçäåëèòü. Îâëàäåíèå è äèñêðåòíûìè, è íåïðåðûâíûì ìåòîäàìè íåîáõîäèìî äëÿ âûðàáîòêè ìàòåìàòè÷åñêîé êóëüòóðû 1 è óñïåøíîãî ïðèìåíåíèÿ ìàòåìàòèêè â ëþáîé ñôåðå äåÿòåëüíîñòè. Èçëàãàåìûé çäåñü êóðñ ñîñòîèò èç òðåõ ÷àñòåé. Ïåðâàÿ ÷àñòü  ýòî ìåòîäû êîìáèíàòîðíûõ âû÷èñëåíèé, ïîäñ÷åòà ðàçëè÷íûõ êîíå÷íûõ îáúåêòîâ. Âòîðàÿ ÷àñòü  ìîäåëè è ìåòîäû òåîðèè ãðàôîâ, ñîâðåìåííîãî ðàçäåëà ìàòåìàòèêè, ïîçâîëÿþùåãî àíàëèçèðîâàòü âñåâîçìîæíûå îòíîøåíèÿ ìåæäó ïàðîé ýëåìåíòîâ êîíå÷íîãî ìíîæåñòâà. Òåîðèÿ ãðàôîâ îáëàäàåò áîëüøîé ñòåïåíüþ óíèâåðñàëüíîñòè, êðàñîòîé è íàãëÿäíîñòüþ, ïîçâîëÿþùåé ñ÷èòàòü åå àíàëîãîì ãåîìåòðèè ïðè êîíå÷íîì ìíîæåñòâå òî÷åê. Òðåòüÿ, çàêëþ÷èòåëüíàÿ ÷àñòü  öåëî÷èñëåííàÿ àðèôìåòèêà, îíà îáëàäàåò, êàê óæå ãîâîðèëîñü, óäèâèòåëüíûìè (íà ïåðâûé âçãëÿä) îñîáåííîñòÿìè, ïîçâîëÿþùèìè â ðÿäå ñëó÷àåâ çíà÷èòåëüíî ñîêðàòèòü îáúåì âû÷èñëåíèé è èçáåæàòü îøèáîê. Ðåçóëüòàòû ïåðâîé ÷àñòè ñóùåñòâåííî èñïîëüçóþòñÿ â ïîñëåäóþùèõ. 1.2 Ðåêîìåíäóåìàÿ ëèòåðàòóðà 1. Íàáåáèí À. À. Äèñêðåòíàÿ ìàòåìàòèêà  Ì.: Íàó÷íûé ìèð, 2010. 2. Èâàíîâ Á. Í. Äèñêðåòíàÿ ìàòåìàòèêà. Àëãîðèòìû è ïðîãðàììû  Ì.: Ëàá. áàç. çíàíèé, 2002. 3. Íàáåáèí À. À. Ñáîðíèê çàäàíèé ïî äèñêðåòíîé ìàòåìàòèêå  Ì.: Íàó÷íûé ìèð, 2009. Íè îäíà èç êíèã íå ÿâëÿåòñÿ îáÿçàòåëüíîé. Äëÿ îâëàäåíèÿ êóðñîì è óñïåøíîãî âûïîëíåíèÿ çàäàíèé äîñòàòî÷íî ïóáëèêóåìîãî çäåñü ìàòåðèàëà. Íî ïîëåçíî çíàòü, ÷òî òàêèå êíèãè åñòü, êàê è ìíîæåñòâî äðóãèõ, â çàãëàâèè êîòîðûõ ïðèñóòñòâóþò ñëîâà "äèñêðåòíàÿ ìàòåìàòèêà". 1.3 Ïðèìåíÿåìûå îáîçíà÷åíèÿ N = {1, 2, . . .}  ìíîæåñòâî íàòóðàëüíûõ ÷èñåë. Z = {0, ±1, ±2, . . .}  ìíîæåñòâî öåëûõ ÷èñåë. Z+ = {0, 1, 2, . . .}  ìíîæåñòâî íåîòðèöàòåëüíûõ öåëûõ ÷èñåë. R = (−∞; +∞)  ìíîæåñòâî âåùåñòâåííûõ ÷èñåë. C = {z = x + iy, x, y ∈ R}  ìíîæåñòâî êîìïëåêñíûõ ÷èñåë, ãäå i  ìíèìàÿ åäèíèöà, i2 = −1. bxc  öåëàÿ ÷àñòü âåùåñòâåííîão x, íàèáîëüøåå öåëîå, íå ïðåâîñõîäÿùåå x. dxe äëÿ âåùåñòâåííîãî ÷èñëà x  íàèìåíüøåå öåëîå M òàêîå, ÷òî M ≥ x.  îçíà÷àåò êîíåö äîêàçàòåëüñòâà, "òðåáóåìîå ïîëó÷åíî", "òåîðåìà äîêàçàíà". 2 2 Âû÷èñëåíèå êîíå÷íûõ ñóìì  çàäà÷àõ äèñêðåòíîé ìàòåìàòèêè ïðèõîäèòñÿ äîâîëüíî ÷àñòî âûïîëíÿòü íåêîòîðûå ñòàíäàðòíûå âû÷èñëåíèÿ. Ðàññìîòðèì ìåòîäû âû÷èñëåíèÿ ñóìì, çàâèñÿùèõ îò íåñêîëüêèõ ïàðàìåòðîâ, îäíèì èç ïàðàìåòðîâ âñåãäà ÿâëÿåòñÿ ÷èñëî ñëàãàåìûõ. Ýòèìè íåñëîæíûìè òåõíè÷åñêèìè ïðèåìàìè íåîáõîäèìî îâëàäåòü äëÿ óñïåøíîãî ðåøåíèÿ áîëåå ñëîæíûõ è ñîäåðæàòåëüíûõ çàäà÷. Îòìåòèì, ÷òî ïðèíöèïèàëüíûì îòëè÷èåì ýòèõ âû÷èñëåíèé îò ñóììèðîâàíèÿ ðÿäîâ ìåòîäàìè âûñøåé ìàòåìàòèêè (òî÷íåå, ìàòåìàòè÷åñêîãî àíàëèçà) ÿâëÿåòñÿ êîíå÷íîñòü ÷èñëà ñëàãàåìûõ è íåâîçìîæíîñòü ïðåäåëüíîãî ïåðåõîäà.  ìàòåìàòè÷åñêîì àíàëèçå òàêèå ñèòóàöèè ÷àñòî ïðèâîäÿò ê ïðèáëèæåííîìó ðåçóëüòàòó (ïîãðåøíîñòü êîòîðîãî ìîæíî, òåì íå ìåíåå, îöåíèòü). Ìû æå áóäåì èñêàòü òî÷íûå çíà÷åíèÿ ñóìì íàòóðàëüíûõ ÷èñåë. Íàïîìíèì, ÷òî ðåçóëüòàòîì âñåãäà äîëæíî áûòü öåëîå ÷èñëî. Ðàññìîòðèì äîâîëüíî îáùåå ñåìåéñòâî ñóìì Sn (k) = n X j k = 1k + 2k + · · · + nk , (1) j=1 çàâèñÿùèõ îò äâóõ öåëî÷èñëåííûõ ïàðàìåòðîâ n ≥ 1 è k ≥ 0. 1.1 Ïðè k = 0 áåç òðóäà íàõîäèì Sn (0) = n X j = j=1 n X 1 = n, j=1 Sn (0) = n. (1.1) 1.2. Ïðè k = 1 çàïèøåì ñóììó Sn (1) â ïðÿìîì è îáðàòíîì ïîðÿäêå: Sn (1) = 1 + 2 + 3 + · · · + (n − 2) + (n − 1) + n, Sn (1) = n + (n − 1) + (n − 2) + · · · + 3 + 2 + 1. Ñëîæèâ ýòè ðàâåíñòâà, ïîëó÷èì 2Sn (1) = (1 + n) + (2 + n − 1) + (3 + n − 2) + · · · + (n − 2 + 3) + (n − 1 + 2) + (n + 1).  ïðàâîé ÷àñòè òåïåðü ñóììà n îäèíàêîâûõ ñëàãàåìûõ (n + 1), îòêóäà Sn (1) = n(n + 1) . 2 (1.2) Âåëèêèé íåìåöêèé ìàòåìàòèê Êàðë Ôðèäðèõ Ãàóññ (17771855) ïðèäóìàë òàêîé ñïîñîá âû÷èñëåíèÿ ýòîé ñóììû â 7-ëåòíåì âîçðàñòå. 3 Ðàññìîòðèì èíîé ñïîñîá. Îí èñïîëüçóåò ñóììó Sn+1 (2). Ñ îäíîé ñòîðîíû, Sn+1 (2) = Sn (2) + (n + 1)2 = Sn (2) + n2 + 2n + 1. Ñ äðóãîé ñòîðîíû, Sn+1 (2) = n X 2 (j + 1) = j=0 n X (j 2 + 2j + 1) = Sn (2) + 2Sn (1) + (n + 1). j=0 Òàêèì îáðàçîì, Sn (2) + n2 + 2n + 1 = Sn (2) + 2Sn (1) + n + 1, îòêóäà ïîñëå ýëåìåíòàðíûõ ïðåîáðàçîâàíèé 2Sn (1) = n2 + n. Ïîëó÷àåì òîò æå ðåçóëüòàò (1.2). Ïðè ëþáîì íàòóðàëüíîì n ïðîèçâåäåíèå n(n + 1) ÷åòíî, ïîýòîìó Sn (1) öåëîå. Âòîðîé ñïîñîá ìîæíî ìîäèôèöèðîâàòü äëÿ âû÷èñëåíèÿ, êàê ìû ïîêàæåì, è áîëåå ñëîæíûõ ñóìì. 1.3 (ñóììà ïåðâûõ n ÷ëåíîâ àðèôìåòè÷åñêîé ïðîãðåññèè a1 , a2 = a1 +d, a3 = a1 + 2d, . . . ñ ðàçíîñòüþ An (d) = d) n X j=1 aj = n X (a1 + (j − 1)d). j=1 Ïðåîáðàçóÿ ñóììó è èñïîëüçóÿ (1.2), ïîëó÷àåì An (d) = na1 + d(1 + 2 + · · · + n − 1) = na1 + d(n − 1)n/2. Ýëåìåíòàðíûìè ïðåîáðàçîâàíèÿìè ïðèõîäèì ê èçâåñòíûì ñî øêîëû ôîðìóëàì An (d) = n(2a1 + (n − 1)d) n(a1 + an ) = . 2 2 (1.3) 1.4. Âû÷èñëèì Sn (2) ñïîñîáîì, àíàëîãè÷íûì âòîðîìó ìåòîäó âû÷èñëåíèÿ ñóììû Sn (1). Èìååì Sn+1 (3) = Sn (3) + (n + 1)3 = Sn (3) + n3 + 3n2 + 3n + 1. Ñ äðóãîé ñòîðîíû, Sn+1 (3) = n X 3 (j + 1) = j=0 n X (j 3 + 3j 2 + 3j + 1) = Sn (3) + 3Sn (2) + 3Sn (1) + (n + 1). j=0 Òàêèì îáðàçîì, Sn (3) + n3 + 3n2 + 3n + 1 = Sn (3) + 3Sn (2) + 3Sn (1) + n + 1. 4 Ñ ó÷åòîì (1.2) ïîëó÷àåì n3 + 3n2 + 3n = 3Sn (2) + 3n(n + 1)/2 + n, . n(n + 1)(2n + 1) . (1.4) 6 Óáåäèìñÿ, ÷òî âûðàæåíèå èç ïðàâîé ÷àñòè (1.4) öåëîå. Èç äâóõ ïîñëåäîâàòåëüíûõ ÷èñåë ðîâíî îäíî ÷åòíî, ïîýòîìó ÷èñëèòåëü äðîáè äåëèòñÿ íà 2. Ïðîâåðèòü, ÷òî îí äåëèòñÿ è íà 3 (ñëåäîâàòåëüíî, íà 6 = 2 · 3) ìîæíî, ðàññìîòðåâ âîçìîæíûå îñòàòêè îò äåëåíèÿ íà 3 ÷èñëà n (ñëó÷àè n = 3m, 3m + 1, 3m + 2, ãäå m ∈ Z ). Ñäåëàéòå ýòî ñàìîñòîÿòåëüíî. 1.5. Àíàëîãè÷íî âû÷èñëèì Sn (3). Èç âûðàæåíèé Sn (2) = Sn+1 (4) = Sn (4) + (n + 1)4 = Sn (4) + n4 + 4n3 + 6n2 + 4n + 1, Sn+1 (4) = n X 4 (j + 1) = j=0 n X (j 4 + 4j 3 + 6j 2 + 4j + 1) = j=0 = Sn (4) + 4Sn (3) + 6Sn (2) + 4Sn (1) + (n + 1) ñëåäóåò ðàâåíñòâî Sn (4) + n4 + 4n3 + 6n2 + 4n + 1 = Sn (4) + 4Sn (3) + 6Sn (2) + 4Sn (1) + n + 1. Ïîäñòàâëÿÿ â íåãî (1.1), (1.2), (1.4), ïîëó÷èì n4 + 4n3 + 6n2 + 4n = 4Sn (3) + n(n + 1)(2n + 1) + 2n(n + 1) + n, îòêóäà 4Sn (3) = n4 + 2n3 + n2 è, íàêîíåö, n2 (n + 1)2 Sn (3) = . 4 (1.5) 1.6. Òàêèì æå ïóòåì ïîñëåäîâàòåëüíî âû÷èñëÿþòñÿ ñóììû Sn (4), Sn (5), . . ..  ÷àñòíîñòè, Sn (4) = n X j=1 j4 = n(6n4 + 15n3 + 10n2 − 1) . 30 Âûâåäèòå ýòó ôîðìóëó ñàìîñòîÿòåëüíî. 1.7. Çíàÿ Sn (0), Sn (1), Sn (2), . . . , Sn (m) è èñïîëüçóÿ ñâîéñòâî ëèíåéíîñòè ñóìì, ìîæíî âû÷èñëèòü ñóììó ìíîãî÷ëåíîâ còåïåíè m, çàâèñÿùèõ îò j : n X (am j m + am−1 j m−1 + · · · + a1 j + a0 ) = j=1 5 = am Sn (m) + am−1 Sn (m − 1) + · · · a1 Sn (1) + a0 Sn (0). 2. ëåì Ñóììà ïåðâûõ ÷ëåíîâ ãåîìåòðè÷åñêîé ïðîãðåññèè ñî çíàìåíàòe- q Gn (q) = 1 + q + q 2 + · · · + q n âû÷èñëÿåòñÿ ïî ñëåäóþùèì ôîðìóëàì: Gn (1) = n + 1, Gn (−1) = 0 ïðè ÷åòíûõ n, Gn (−1) = 1 ïðè íå÷åòíûõ n, q n+1 − 1 Gn (q) = ïðè |q| = 6 1. q−1 Ïðèìåð. Âîò ñîäåðæàòåëüíàÿ çàäà÷à, â êîòîðîé èñïîëüçóåòñÿ ñóììà Gn (q). Êàêîâî êîëè÷åñòâî äåñÿòè÷íûõ öåëûõ ÷èñåë îò 0 äî 10n , íå ñîäåðæàùèõ íàõîäÿùèõñÿ ðÿäîì îäèíàêîâûõ öèôð? Îáîçíà÷èì èñêîìóþ âåëè÷èíó êàê xn . Ëåãêî íàéòè x1 = 10, x2 = 100 − 9 = 91. Ïóñòü íàéäåíî ÷èñëî xn . Òîãäà xn+1 = xn + ∆n+1 , ãäå ∆n+1  êîëè÷åñòâî ÷èñåë, ñîäåðæàùèõ ðîâíî n + 1 öèôð d1 , d2 , . . . , dn+1 , ïðè ýòîì d1 6= 0, ò. å. d1 ìîæåò ïðèíèìàòü ëþáîå èç 9 çíà÷åíèé 1, . . . , 9. Òîãäà è äëÿ êàæäîãî j = 2, . . . , n + 1 öèôðà dj ìîæåò ïðèíèìàòü ëþáîå èç 9 çíà÷åíèé, ïðèíàäëåæàùèõ ìíîæåñòâó {0, 1, . . . , 9} \ {dj−1 }. Âñå n + 1 öèôð ìîãóò ïðèíèìàòü, òàêèì îáðàçîì, 9n+1 çíà÷åíèé (ýòî ÷àñòíûé ñëó÷àé îáùåãî , ÷àñòî èñïîëüçóåìîãî â ðàçëè÷íûõ çàäà÷àõ äèñêðåòíîé ìàòåìàòèêè). Ñëåäîâàòåëüíî, ∆n+1 = 9n+1 , xn+1 = xn + 9n+1 , ïðàâèëà ïðîèçâåäåíèÿ 9n+1 − 1 xn = 10 + 9 + 9 + · · · + 9 = Gn (9) = . 8 2 3 n Çàäàíèå äëÿ ñàìîñòîÿòåëüíîãî ðåøåíèÿ Âàðèàíò çàäàíèÿ  Âàø íîìåð â ñïèñêå ãðóïïû. Ðåøåíèÿ ïðèñûëàéòå ìíå, Ìåùàíèíîâó Äìèòðèþ Ãåðìàíîâè÷ó, ïî àäðåñó MeshchaninovDG@mpei.ru Íåîáõîäèìî âûïîëíèòü ïî îäíîìó âàðèàíòó êàæäîãî èç òðåõ çàäàíèé  âû÷èñëèòü óêàçàííûå ñóììû öåëûõ ÷èñåë. Çàäàíèå 1 1.1. n P j 2 (j − 3). j=1 6 1.2. 1.3. 1.4. 1.5. 1.6. 1.7. 1.8. 1.9. 1.10. 1.11. 1.12. 1.13. 1.14. 1.15. n P j 2 (2j + 1). j=1 n P (j 3 − 3j). j=1 n P (2j 3 + j − 1). j=1 n P (3j 3 − 4). j=1 n P (j 3 + 4j). j=1 n P (j 3 + 3j 2 ). j=1 n P (j 3 − 3j − 1). j=1 n P j 2 (j + 2). j=1 n P j(j 2 + 2j + 1). j=1 n P (j 3 + 3j − 1). j=1 n P (j 3 + 2j + 1). j=1 n P ((j + 1)3 − j). j=1 n P (2j 3 − (j − 1)2 ). j=1 n P (3j 2 + j 2 (j − 1)). j=1 7 Çàäàíèå 2 2.1. 2.2. 2.3. 2.4. 2.5. 2.6. 2.7. 2.8. 2.9. 2.10. 2.11. 2.12. 2.13. 2.14. 2.15. n P (−1)j 2j. j=0 n P (−1)j (2 − j). j=0 n P (−1)j (2j − 1). j=0 n P (−1)j+1 2j. j=0 n P (−1)j−1 (2j + 1). j=0 n P (−1)j (4j + 2). j=0 n P (−1)j−1 (j + 1). j=0 n P 3 (−1)j (3 − j). j=0 n P (−1)j (2j − 3). j=0 n P (−1)j (1 − j). j=0 n P (−1)(11j) (j − 1). j=0 n P (−1)(21j) 2j. j=0 n P (−1)(3j) (j − 3). j=0 n P (−1)j+4 (j − 4). j=0 n P 2 (−1)j 2j. j=0 8 Çàäàíèå 3 Íàéäèòå ÷èñëî, ÿâëÿþùååñÿ çíà÷åíèåì ñóììû. 3.1. 3.2. 3.3. 3.4. 3.5. 3.6. 3.7. 3.8. 3.9. 3.10. 3.11. 3.12. 3.13. 3.14. 3.15. 11 P (1 + (−2)j ). j=0 9 P ((−1)j + (−2)j ). j=0 5 P (−15 + (−3)j ). j=0 6 P 3 ((−1)j + (−4)j ). j=0 5 P (3j + (−2)j ). j=0 6 P (4j + (−2)j ). j=0 6 P ((−2)2j − (−2)j ). j=0 6 P ((−1)j + (−2)j ). j=0 5 P (22j + (−1)j ). j=0 10 P (2j + (−2)j ). j=0 7 P (2(−1)j + (−2)2j ). j=0 4 P ((−3)2j + (−2)3j ). j=0 6 P ((−1)3j + (−3)j ). j=0 11 P ((−1)2j + (−2)j ). j=0 11 P 2 ((−1)j + (−2)j ). j=0 9 3 Îñíîâíûå êîìáèíàòîðíûå êîíôèãóðàöèè è ÷èñëà Êîìáèíàòîðèêà, êîìáèíàòîðíûé àíàëèç  ýòî ðàçäåë ìàòåìàòèêè, â êîòîðîì ðàññìàòðèâàþòñÿ ïîäìíîæåñòâà êîíå÷íûõ ìíîæåñòâ. Ïîäìíîæåñòâà îïðåäåëåííîãî âèäà íàçûâàþòñÿ . Ïîäñ÷åò êîëè÷åñòâà êîìáèíàòîðíûõ êîíôèãóðàöèé ( ) ñîñòàâëÿåò ñóòü ïåðå÷èñëèòåëüíûõ çàäà÷ êîìáèíàòîðíîãî àíàëèçà. Òàêèå çàäà÷è ïðèõîäèòñÿ ðåøàòü êàê ÷àñòè áîëåå ñëîæíûõ çàäà÷ äèñêðåòíîé ìàòåìàòèêè. êîìáèíàòîðíûìè êîíôèãóðàöèÿìè êîìáèíàòîðíûõ ÷èñåë 3.1 Ïðîñòåéøèå ïðàâèëà êîìáèíàòîðíûõ âû÷èñëåíèé Ïðè ïîäñ÷åòå êîìáèíàòîðíûõ êîíôèãóðàöèé ïðèìåíÿþòñÿ äâà î÷åíü ïðîñòûõ ïðàâèëà. Ïðàâèëî ïðîèçâåäåíèÿ. O1 N1 Åñëè îáúåêò ìîæíî âûáðàòü ðàçëè÷íûìè ñïîñîáàìè, à îáúåêò O2 âûáèðàåòñÿ ðîâíî N2 ñïîñîáàìè, òî ïàðó îáúåêòîâ {O1 , O2 } ìîæíî âûáðàòü ðîâíî N1 · N2 ðàçëè÷íûìè ñïîñîáàìè. 1 Ïðàâèëî ñóììû. Åñëè îáúåêò O1 ìîæíî âûáðàòü N1 ðàçëè÷íûìè ñïîñîáàìè, à îáúåêò O2 âûáèðàåòñÿ ðîâíî N2 ñïîñîáàìè, è ïðè ýòîì âûáîð O1 è O2 îäíîâðåìåííî íåâîçìîæåí 2, òî âûáîð "O1 èëè O2" ìîæíî îñóùåñòâèòü ðîâíî N1 + N2 ðàçëè÷íûìè ñïîñîáàìè. Ýòè ïðàâèëà ïîçâîëÿþò ëåãêî âû÷èñëèòü êîëè÷åñòâî íåêîòîðûõ ÷àñòî ïðèìåíÿåìûõ êîìáèíàòîðíûõ êîíôèãóðàöèé. Ïðèìåð. Èç ãîðîäà A ðîâíî m1 äîðîã âåäóò â ãîðîä B è n1 äîðîã  â ãîðîä C . Ðîâíî m2 äîðoã âåäóò èç B â ãîðîä D, ðîâíî n2 äîðîã  èç C â D. Èç A â D ìîæíî ïðîåõàòü òîëüêî ÷åðåç ãîðîä B èëè ãîðîä C . Ñêîëüêèìè ñïîñîáàìè ìîæíî ïîïàñòü èç A â D? Ïðèìåíÿÿ ïðàâèëî ïðîèçâåäåíèÿ, íàõîäèì ÷èñëî m1 m2 ïóòåé èç A â D ÷åðåç B è ÷èñëî n1 n2 ïóòåé èç A â D ÷åðåç C . Äàëåå ïî ïðàâèëó ñóììû ïîëó÷àåì îòâåò m1 m2 + n1 n2 . Òåîðåìà 1. U = {e1 , . . . , en } n n 2 ( U ). Äîêàçàòåëüñòâî. Ïóñòü B  ïîäìíîæåñòâî ìíîæåñòâà U . Êàæäîå òàêîå ïîäìíîæåñòâî îäíîçíà÷íî îïðåäåëÿåòñÿ ïðèíàäëåæíîñòüþ èëè íåïðèíàäëåæíîñòüþ åìó êàæäîãî èç ýëåìåíòîâ e1 , . . . , en . Èòàê, äëÿ êàæäîãî j = 1, . . . , n íàäî âûáðàòü îäíî èç äâóõ óñëîâèé: ej ∈ B èëè ej 6∈ B . Åñòü ðîâíî nj = 2 ñïîñîáà âûáîðà òàêîãî óñëîâèÿ äëÿ êàæäîãî j = 1, . . . , n. Ïðèìåíÿÿ ïðàâèëî ïðîèçâåäåíèÿ, ïîëó÷àåì Êîíå÷íîå ìíîæåñòâî èç ýëåìåíòîâ èìååò ïîäìíîæåñòâ âêëþ÷àÿ ïóñòîå è ñàìî ìíîæåñòâî ðîâíî 1 îòñþäà 2 ýòî è íàçâàíèå ïðàâèëà, èìååòñÿ òàêæå àíàëîãèÿ ñ ïðîèçâåäåíèåì ñîáûòèé óñëîâèå î÷åíü âàæíî, åãî èãíîðèðîâàíèå ïðèâîäèò ê ñìûñëîâûì îøèáêàì 10 ÷èñëî 2 × · · · × 2 = 2n ñïîñîáîâ âûáîðà óñëîâèé äëÿ âñåõ j = 1, . . . , n, ò. å. ÷èñëî ðàçëè÷íûõ ïîäìíîæåñòâ ìíîæåñòâà U .  Ïðèìåð 1. Ìíîæåñòâî èç 3 ýëåìåíòîâ {E1 , E2 , E3 } èìååò ðîâíî 23 = 8 ïîäìíîæåñòâ: ∅, {E1 }, {E2 }, {E3 }, {E1 , E2 }, {E1 , E3 }, {E2 , E3 }, {E1 , E2 , E3 }. Ïîäìíîæåñòâà âçàèìíî îäíîçíà÷íî ñîîòâåòñòâóþò áèíàðíûì âåêòîðàì (x1 , x2 , x3 ), ãäå xj = 1, åñëè Ej ïðèíàäëåæèò ïîäìíîæåñòâó, è xj = 0 â ïðîòèâíîì ñëó÷àå. Ñëåäñòâèå 1. (x1 , . . . , xn ) n 2n . Òàêèå âåêòîðû ÷àñòî ïðèìåíÿþò ïðè ïîäñ÷åòå êîìáèíàòîðíûõ êîíôèãóðàöèé. Áèíàðíûå âåêòîðû  óíèâåðñàëüíûé ñïîñîá êîäèðîâàíèÿ, ò. å. çàïèñè ëþáîé èíôîðìàöèè â ÿçûêå ñ àëôàâèòîì {0, 1}. Ðàññìîòðèì àíàëîãè÷íûé ñïîñîá çàïèñè â ÿçûêå ñ ëþáûì êîíå÷íûì àëôàâèòîì. Äàäèì òî÷íûå îïðåäåëåíèÿ è âûâåäåì äîâîëüíî ïðîñòûå, íî âàæíûå ðåçóëüòàòû, øèðîêî ïðèìåíÿåìûå â äèñêðåòíîé ìàòåìàòèêå. Êîëè÷åñòâî áèíàðíûõ âåêòîðîâ 3.2 äëèíû ðàâíî Ñëîâà â êîíå÷íîì àëôàâèòå àëôàÑëîâîì äëèíû â àëôàâèòå Êîíå÷íîå ìíîæåñòâî, ñêàæåì, èç k ýëåìåíòîâ, A = {a1 , . . . , ak } íàçûâàåòñÿ , åãî ýëåìåíòû aj  , èëè áóêâàìè. n A íàçûâàåòñÿ êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü ñèìâîëîâ àëôàâèòà A: âèòîì ñèìâîëàìè aj(1) aj(2) . . . aj(n) , aj(1) , aj(2) , . . . , aj(n) ∈ A. Ìíîæåñòâî âñåõ ñëîâ äëèíû n â àëôàâèòå A îáîçíà÷àåòñÿ êàê An . ×èñëî ýëåìåíòîâ ïðîèçâîëüíîãî êîíå÷íîãî ìíîæåñòâà M îáîçíà÷àåòñÿ êàê |M | è íàçûâàåòñÿ M . Î÷åâèäíî, |∅| = 0. Íàòóðàëüíûå ÷èñëà è 0  ýòî âñå ìîùíîñòè êîíå÷íûõ ìíîæåñòâ. Èìåííî òàêèì îáðàçîì ó äðåâíèõ ëþäåé ñôîðìèðîâàëîñü àáñòðàêòíîå ïîíÿòèå íàòóðàëüíîãî ÷èñëà, èìåííî òàê ó÷àò ÷èñëàì ìàëåíüêèõ äåòåé. Ïî ïðàâèëó ïðîèçâåäåíèÿ ëåãêî âûâîäèòñÿ îáîáùåíèå ñëåäñòâèÿ 1. Ñëåäñòâèå 2. n k kn. Ýòî æå ìîæíî çàïèñàòü òàê: åñëè |A| = k , òî |An | = k n (÷àñòíûé ñëó÷àé ïðàâèëà ïðîèçâåäåíèÿ). Ïðè çàïèñè ñëîâ ôèêñèðîâàííîãî àëôàâèòà óäîáíî ðàñïîëàãàòü ñëîâà â íåêîòîðîì ïîðÿäêå, ïîçâîëÿþùåì ëåãêî èõ ïðîñìàòðèâàòü è ïðîâåðÿòü, âñå ëè íóæíûå ñëîâà ïðèñóòñòñòâóþò, íåò ëè ïîâòîðåíèé. Îáùåïðèíÿòûì ÿâëÿåòñÿ . Ýòèì ñïîñîáîì ïåðå÷èñëÿþòñÿ ñëîâà â ñëîâàðÿõ, ñïðàâî÷íèêàõ, ýíöèêëîïåäèÿõ, ñïèñêàõ èìåí è íàçâàíèé è ò. ï. Ñëîâà cíà÷àëà óïîðÿäî÷èâàþòñÿ ïî ïåðâîé áóêâå, çàòåì ñëîâà ñ îäèíàêîâîé ïåðâîé áóêâîé óïîðÿäî÷èâàþòñÿ ïî ìîùíîñòüþ êîíå÷íîãî ìíîæåñòâà Êîëè÷åñòâî ñëîâ äëèíû â àëôàâèòå èç áóêâ ðàâíî ëåêñèêîãðà- ôè÷åñêèé ïîðÿäîê 11 âòîðîé è òàê äàëåå. Åñëè ecòü ñëîâà ðàçíîé äëèíû, òî ïîðÿäîê ñëîâ ñ îäèíàêîâûìè ïåðâûìè áóêâàìè òàêîâ, ÷òî ñíà÷àëà âûïèñûâàþòñÿ êîðîòêèå ñëîâà, ó êîòîðûõ íåò ñëåäóþùåé áóêâû, çàòåì óæå îñòàëüíûå ñëîâà (ñ òåìè æå ïåðâûìè áóêâàìè) óïîðÿäî÷èâàþòñÿ ïî ñëåäóþùåé áóêâå. Ïðèìåð 3. Âûïèøåì â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå âñå 32 = 9 ñëîâ äëèíû 2 â àëôàâèòå {a, b, c} ìîùíîñòè 3: aa, ab, ac, ba, bb, bc, ca, cb, cc. Ïðèìåð 4. Âûïèøåì â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå ñëîâà ðàçíîé äëèíû â àëôàâèòå {a, b, c} èç ìíîæåñòâà {bcaa, b, cca, cbac, acb, bcab, abcc, bcca, bbc, cc} : abcc, acb, b, bbc, bcaa, bcab, bcca, cbac, cc, cca. ñîðòèðîâêîé Ïðîöåññ óïîðÿäî÷èâàíèÿ ðàçëè÷íûõ ñïèñêîâ íàçûâàåòñÿ èõ . Ñîðòèðîâêà ÷àñòî ïðèìåíÿåòñÿ â ðàçëè÷íûõ çàäà÷àõ îáðàáîòêè èíôîðìàöèè. Ñëîæíîñòü ñîðòèðîâêè îöåíèâàåòñÿ ìåòîäàìè äèñêðåòíîé ìàòåìàòèêè. Ñèììåòðè÷íûå îòíîñèòåëüíî ñâîåé ñåðåäèíû ñëîâà íàçûâàþòñÿ . Ïðèìåðû ïàëèíäðîìîâ â ðóññêîì ÿçûêå  èìÿ Àëëà, ñëîâî "êàçàê". Íàéäåì ÷èñëî ïàëèíäðîìîâ äëèíû n â àëôàâèòå ìîùíîñòè k .  ïàëèíäðîìå ÷åòíîé äëèíû n ïðîèçâîëüíî ìîæíî çàäàòü òîëüêî ïåðâûå n/2 áóêâ, îñòàëüíûå  òå æå ïåðâûå n/2 áóêâ, çàïèñàííûå â îáðàòíîì ïîðÿäêå. ×èñëî ïàëèíäðîìîâ ÷åòíîé äëèíû n ðàâíî k n/2 .  ïàëèíäðîìå íå÷åòíîé äëèíû n = 2m + 1 ïðîèçâîëüíî ìîæíî çàäàòü ïåðâûå m áóêâ è åùå îäíó  öåíòðàëüíóþ. ×èñëî òàêèõ ïàëèíäðîìîâ ðàâíî k m+1 .  ìàòåìàòèêå ïðèíÿòî îáîçíà÷åíèå dxe äëÿ íàèìåíüøåãî öåëîãî ÷èñëà N òàêîãî, ÷òî N ≥ x, ãäå x  ïðîèçâîëüíîå âåùåñòâåííîå ÷èñëî. Òàê, d0.7e = 1, dπe = 4, d(−5)e = −5. Ðåçóëüòàòû íàøèõ íàáëþäåíèé íàä ïàëèíäðîìàìè ìîæíî çàïèñàòü êàê Ñëåäñòâèå 3. n k dn/2e k . Ïðèìåð 5. Âûïèøåì â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå âñå ïàëèíäðîìû äëèíû íå áîëåå 3 â àëôàâèòå {a, b, c}. Èìååì k = 3. ×èñëî ïàëèíäðîìîâ äëèíû 1 ðàâíî 3d1/2e = 31 = 3, äëèíû 2  3d2/2e = 31 = 3 , äëèíó 3 èìåþò 3d3/2e = 32 = 9 ïàëèíäðîìîâ. Îñòàëîñü âûïèñàòü âñå 3 + 3 + 9 = 15 ïàëèíäðîìîâ â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå: ïàëèíäðîìàìè ×èñëî ïàëèíäðîìîâ äëèíû â àëôàâèòå ìîùíîñòè ðàâíî a, aa, aaa, aba, aca, b, bab, bb, bbb, bcb, c, cac, cbc, cc, ccc. Íåêîòîðûå ìàñòåðà ñëîâà ïðîÿâëÿþò íåìàëî èñêóññòâà â ñîñòàâëåíèè îñìûñëåííûõ ïàëèíäðîìîâ, íàïðèìåð, "Àííà, Âàñ è òèíà ìàíèò, è ñàâàííà". Ýòà ôðàçà ñîäåpæèò 24 áóêâû ðóññêîãî àëôàâèòà. Îáùåå ÷èñëî ïàëèíäðîìîâ òàêîé äëèíû 12 åñòü 3312 , íî èç íèõ íàäî åùå âûáðàòü ñèíòàêñè÷åñêè ïðàâèëüíî çàïèñûâàåìûå, à èç ïîñëåäíèõ  îñìûñëåííûå. Òðåáóåòñÿ âèðòóîçíîå âëàäåíèå ÿçûêîì! Ïðèìåð 6. Àâòîìîáèëüíûå íîìåðà ñîäåðæàò 3 äåñÿòè÷íûå öèôðû è 4 áóêâû èç 12, îáùèõ äëÿ êèðèëëè÷åñêîãî è ëàòèíñêîãî àëôàâèòîâ. Íàéäåì ÷èñëî âñåõ âîçìîæíûõ íîìåðîâ. Òðè öèôðû ìîæíî âûáðàòü, ïî ïðàâèëó ïðîîèçâåäåíèÿ, 103 ñïîñîáàìè. Àíàëîãè÷íî 4 áóêâû ìîæíî âûáðàòü 124 = 20 736 ñïîñîáàìè. Âûáèðàÿ è öèôðû è áóêâû, ïîëó÷àåì, ïî ïðàâèëó ïðîèçâåäåíèÿ, 20 736 000 íîìåðîâ. Íåêîòîðûå ëþäè ñ÷èòàþò ïðåñòèæíûìè "çåðêàëüíûå" íîìåðà, â êîòîðûõ ñëîâî, ñîñòàâëåííîå èç öèôð, åñòü ïàëèíäðîì. ×èñëî òàêèõ íîìåðîâ îêàçûâàåòñÿ, â ñîîòâåòñòâèè ñ óæå èçëîæåííûìè ðåçóëüòàòàìè, 122 103 = 144 000. 3.3 Ðàçìåùåíèÿ, ïåðåñòàíîâêè, ñî÷åòàíèÿ Ïóñòü ôèêñèðîâàíî n-ýëåìåíòíîå ìíîæåñòâî U = {E1 , . . . , En }. Åãî íåóïîðÿäî÷åííûå k -ýëåìåíòíûå ïîäìíîæåñòâà {Ej(1) , . . . , Ej(k) }, 1 ≤ j(1) < · · · < j(k) ≤ n, 0 ≤ k ≤ n, ñî÷åòàíèÿìè èç ýëåìåíòîâ ïî íàçûâàþòñÿ n k (óïîòðåáëÿþòñÿ ôèãóðíûå ñêîáêè). ×èñëî ñî÷åòàíèé èç n ýëåìåíòîâ ïî k îáîçíà÷àåòñÿ êàê Cnk . Óïîðÿäî÷åííûå k -ýëåìåíòíûå ïîäìíîæåñòâà (Ej(1) , . . . , Ej(k) ), 1 ≤ j(1) < · · · < j(k) ≤ n, 0 ≤ k ≤ n, ðàçìåùåíèÿìè èç ýëåìåíòîâ ïî íàçûâàþòñÿ n k (óïîòðåáëÿþòñÿ êðóãëûå ñêîáêè, êàê ïðè óêàçàíèè ýëåìåíòîâ âåêòîðîâ è ìàòðèö). ×èñëî ðàçìåùåíèé èç n ýëåìåíòîâ ïî k îáîçíà÷àåòñÿ êàê Akn . Ðàçìåùåíèå èç k ýëåìåíòîâ k ïî íàçûâàåòñÿ ýòèõ k . Òåîðåìà 2. 0≤k≤n ïåðåñòàíîâêîé ýëåìåíòîâ Åñëè , òî Akn = n(n − 1)(n − 2) · · · (n − k + 1) =  ÷àñòíîñòè, n! . (n − k)! 3 Akk = k!. Äîêàçàòåëüñòâî. Ïóñòü A  ðàçìåùåíèå, ñîñòîÿùåå èç k ýëåìåíòîâ ìíîæåñòâà U = {E1 , . . . , En }. Îíî îäíîçíà÷íî îïðåäåëÿåòñÿ âûáîðîì ñâîèõ ýëåìåíòîâ Ej(1) , . . . , Ej(k) . Ýëåìåíò Ej(1) ìîæíî âûáðàòü n ñïîñîáàìè (ëþáîé èç n ýëåìåíòîâ ìíîæåñòâà Ω), Ej(2)  (n − 1) ñïîñîáîì (ëþáîé èç ýëåìåíòîâ ìíîæåñòâà U êðîìå 3 Åñëè k  ïîëîæèòåëüíîå öåëîå, òî k! = 1 × 2 × · · · × k è ïî îïðåäåëåíèþ 0!=1 13 Ej(1) ), Ej(3)  (n − 2) ñïîñîáàìè è òàê äàëåå. Ïîñëåäíèé ýëåìåíò Ej(k) ðàçìåùåíèÿ ìîæíî âûáðàòü (n − (k − 1)) ñïîñîáàìè (ëþáîé â U êðîìå Ej(1) , . . . , Ej(k−1) . Ïðèìåíÿÿ ïðàâèëî ïðîèçâåäåíèÿ, ïîëó÷àåì Akn = n(n − 1)(n − 2) · · · (n − k + 1).  Ïðèìåð 7. Âûïèøåì â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå âñå k! ïåðåñòàíîâîê k ýëåìåíòîâ äëÿ k = 2, 3, 4. Èìååì 2! = 2, 3! = 6, 4! = 24. Ýòî ÷èñëî ïåðåñòàíîâîê. Óêàæåì ñàìè ïåðåñòàíîâêè â íóæíîì ïîðÿäêå. k=2: 12, 21. k=3: 123, 132, 213, 231, 312, 321. k=4: 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321. Ïðèìåð 8. Íà ïðàçäíèê ïðèøëè ñóïðóæåñêàÿ ïàðà ñ äâóìÿ äåòüìè, ñåìüÿ ñ îäíèì ðåáåíêîì, äâå ïàðû áåç äåòåé è ñâîáîäíûé ìóæ÷èíà. Îíè õîòÿ âñòàòü øåðåíãîé äëÿ ñîâìåñòíîãî ôîòî. Ñêîëüêèìè ñïîñîáàìè ìîæíî ýòî ñäåëàòü, åñëè âñå ÷ëåíû êàæäîé ñåìüè õîòÿò áûòü ðÿäîì äðóã ñ äðóãîì? Áóäåì ñ÷èòàòü êàæäóþ ñåìüþ (è îäíîãî ìóæ÷èíó) êàê åäèíûé îáúåêò. Èìååì 5 îáúåêòîâ, êîòîðûå ìîæíî ïåðåñòàâèòü 5! ñïîñîáàìè. Íî íàäî åùå óïîðÿäî÷èòü âñåõ ïðåäñòàâèòåëåé êàæäîé ñåìüè-îáúåêòà. Ïðèìåíÿÿ ïðàâèëî ïðîèçâåäåíèÿ, íàõîäèì 5!4!3!(2!)2 1! = 69 120 ñïîñîáîâ. ñëîâà w íàçûâàåòñÿ ñëîâî, ïîëó÷åííîå ïåðåñòàíîâêîé âñåõ áóêâ ñëîâà w. Ñëîâî "ñëîí" èìååò 4! àíàãðàìì, à ñëîâî "æàáà"  íå 4!, à òîëüêî 12 (â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå: ààáæ, ààæá, àáàæ, àáæà, àæàá, àæáà, áààæ, áàæà, áæàà, æààá, æàáà, æáàà), ïîñêîëüêó áóêâà "à" ïîâòîðÿåòÿ äâàæäû, ïåðåñòàíîâêè ýòèõ áóêâ íå ìåíÿþò ñëîâî. Àíàëîãè÷íî ñëîâî "êàêàäó" èìååò íå 6!, à 6!/(2!)2 àíàãðàìì, â ýòîì ñëîâå ïî äâà ðàçà ïîâòîðÿþòñÿ áóêâû "à" è "ê". Íåòðóäíî âûâåñòè îáùóþ ôîðìóëó: n k, k ≤ n Àíàãðàììîé åñëè ñëîâî èìååò äëèíó è ñîäåðæèò , ðàçëè÷íûõ áóêâ, ïîâòîðÿþùèõñÿ k1, . . . , kn ðàç (ïðè ýòîì k1 + · · · + kn = n), òî ÷èñëî àíàãðàìì òàêîãî ñëîâà åñòü n! . k1 ! · · · kn ! Àíàãðàììû ÷àñòî èñïîëüçóþòñÿ êàê ïñåâäîíèìû (âûìûøëåííûå èìåíà). Íàïðèìåð, Ôðàíñóà Ðàáëå ïîäïèñûâàë ñâîé îñòðîñàòèðè÷åñêèé ðîìàí "Ãàðãàíòþà è Ïàíòàãðþýëü"(15331551) ïñåâäîíèìîì Àëüêîôðèáàñ Íàçüå (Alcofribas Nasier  ïîëíàÿ àíàãðàììà, âêëþ÷àÿ ïðîáåë, ïîäëèííîãî èìåíè Francois Rabelais). Äðóãîé 14 ïðèìåð: âåñüìà óñïåøíîãî õóäîæíèêà XX âåêà Ñàëüâàäîðà Äàëè (Salvador Dali) äðóçüÿ íàçûâàëè Avida Dollars ("Ãðåáóùèé Äåíüãè"). Òåîðåìà 3. 0≤k≤n Åñëè Cnk = , òî n(n − 1)(n − 2) · · · (n − k + 1) n! = . k! k!(n − k)! (1) Çàìåòèì, ÷òî Cnk = Akn /Akk è ïðèìåíèì òåîðåìó 2.  Ôóíêöèÿ k! î÷åíü áûñòðî ðàñòåò ((k + 1)! = k!(k + 1), 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, 6! = 720), âû÷èñëåíèå Cnk ïî ôîðìóëå (1) îãðàíè÷åíî òåõíè÷åñêèìè âîçìîæíîñòèìè àïïàðàòóðû. Äëÿ áîëåå ýôôåêòèâíîãî âû÷èñëåíèÿ ïðèìåíÿþòñÿ ñëåäóþùèå ñâîéñòâà. Çàìå÷àíèå. ×òîáû íå çàïèñûâàòü îãðàíè÷åíèÿ äëÿ çíà÷åíèÿ âåðõíèõ èíäåêñîâ k è ïðèäàâàòü èì ëþáîå íåîòðèöàòåëüíîå öåëîå çíà÷åíèå, ïðèíÿòî ñîãëàøåíèå Äîêàçàòåëüñòâî. Akn = Cnk = 0 ïðè k > n. Òåîðåìà 4 (ñâîéñòâà ÷èñåë 1. 2. 3. 4. 5. 6. Cnk ). Cn0 = Cnn = 1. Cn1 = Cnn−1 = n. Cn2 = Cnn−2 = n(n − 1)/2. Cnk = Cnn−k . k−1 k Cnk = Cn−1 + Cn−1 . k Cn ×èñëà îáðàçóþò áåñêîíå÷íóþ ìàòðèöó, íàçûâàåìóþ òðåóãîëüíèêîì Ïàñêàëÿ. Åå ñòðîêè ñîîòâåòñòâóþò çíà÷åíèÿì n = 0, 1, 2 . . ., ñòîëáöû  çíà÷åíèÿì k = 0, 1, . . . , n. Âîò ïåðâûå ñòðîêè òðåóãîëüíèêà Ïàñêàëÿ: 1 1 1 1 1 1 1 1 2 1 3 3 1 4 6 4 1 5 10 10 5 1 6 15 20 15 6 1 Åñëè n = 2m, òî Cn0 < Cn1 < . . . < Cnm−1 < Cnm > Cnm+1 > · · · > Cnn. Åñëè n = 2m + 1, òî Cn0 < Cn1 < . . . < Cnm−1 < Cnm = Cnm+1 > Cnm+2 > · · · > Cnn. 8. Ñâåðòêà-ðàçâåðòêà: 7. CNK1 +N2 = K X CNM1 CNK−M . 2 M =0 Ïåðåõîä îò ïðàâîé ÷àñòè ýòîé ôîðìóëû ê ëåâîé íàçûâàåòñÿ ñòàíîâèòñÿ êîðî÷å), â äðóãóþ ñòîðîíó  . ðàçâåðòêîé 15 ñâåðòêîé (ôîðìóëà Äîêàçàòåëüñòâî. Ñóùåñòâóåò íåìàëî ñïîñîáîâ âûâîäà ýòèõ ñâîéñòâ. Ìû èçëîæèì äîêàçàòåëüñòâî, èñïîëüçóþùåå ñîäåðæàòåëüíûé ñìûñë ÷èñåë Cnk . Ïóñòü U = {e1 , . . . , en }. 1. ×èñëî Cn0  ýòî êîëè÷åñòâî 0-ýëåìåíòíûõ ïîäìíîæåñòâ ìíîæåñòâà U . ßñíî, ÷òî òàêîå ïîäìíîæåñâî îäíî  ïóñòîå, Cn0 = 1. Ìíîæåñòâî U èìååò òàêæå ðîâíî îäíî ïîäìíîæåñòâî ìîùíîñòè n  ñàìî U . Îòñþäà Cnn = 1. 2. Àíàëîãè÷íî, Cn1  êîëè÷åñòâî îäíîýëåìåíòíûõ ïîäìíîæåñòâ ìíîæåñòâà U . Èìååòñÿ ðîâíî n òàêèõ ïîäìíîæåñòâ: {e1 }, . . . , {en }. Äàëåå, êàæäîå (n−1)-ýëåìåíòíîå ïîäìíîæåñòâî B â U îäíîçíà÷íî îïðåäåëÿåòñÿ ðîâíî îäíèì ýëåìåíòîì èç U , íå âõîäÿùèì â B . Òàêîé ýëåìåíò âûáèðàåòñÿ ðîâíî n ñïîñîáàìè, ïîýòîìó Cnn−1 = n. 3. Ýòè ôîðìóëû  ÷àñòíûé ñëó÷àé ôîðìóëû (1). 4. Êàæäîìó k -ýëåìåíòíîìó ïîäìíîæåñòâó B â U âçàèìíî îäíîçíà÷íî ñîîòâåòñòâóåò (n − k)-ýëåìåíòíîå ìíîæåñòâî B (îíî íàçûâàåòñÿ B â U , èëè U \B U è B ), ñîñòîÿùåå â òî÷íîñòè èç âñåõ ýëåìåíòîâ â k U , íå âõîäÿùèõ â B . ×èñëî Cn ìíîæåñòâ B ðàâíî ÷èñëó Cnn−k ìíîæåñòâ B . 5. Ïîëîæèì U1 = {e1 , . . . , en−1 }. Âñå Cnk ïîäìíîæåñòâ B ìîùíîñòè k â U ìîæíî ðàçáèòü íà äâå íåïåðåñåêàþùèåñÿ ãðóïïû: k−1 1) ñîäåðæàùèå ýëåìåíò en , èõ êîëè÷åñòâî åñòü Cn−1 , òàê êàê ýëåìåíòàìè ïîäìíîæåñòâà U1 çàïîëíÿþòñÿ ëèøü k − 1 ìåñò â ìíîæåñòâå B (îäíî ìåñòî â B çàíÿòî ýëåìåíòîì en ); k 2) íå ñîäåðæàùèå en , èõ êîëè÷åñòâî åñòü Cn−1 , òàê êàê ýëåìåíòàìè ïîäìíîæåñòâà U1 çàïîëíÿþòñÿ âñå k ìåñò â ìíîæåñòâå B . k−1 k . + Cn−1 Ïî ïðàâèëó ñóììû ïîëó÷àåì Cnk = Cn−1 6. Êàæäûé k -ûé ýëåìåíò (1 ≤ k ≤ n−1) ñòðîêè n òðåóãîëüíèêà âû÷èñëÿåòñÿ ïî ôîðìóëå 5 ñëîæåíèåì ñîîòâåòñòâóþùèõ ýëåìåíòîâ ïðåäûäóùåé ñòðîêè. Çíà÷åíèÿ ýëåìåíòîâ ïðè k = 0 è k = n îïðåäåëÿþòñÿ ñâîéñòâîì 1. 7. Ñëåäóåò èç ôîðìóëû (1) è ñâîéñòâà 4. Ëåãêî âèäåòü â òðåóãîëüíèêå Ïàñêàëÿ. 8. Ïðèäàäèì âõîäÿùèì â ôîðìóëó ÷èñëàì ñîäåðæàòåëüíûé ñìûñë. Ïóñòü èìååòñÿ N1 ìóæ÷èí è N2 æåíùèí. Èç íèõ íàäî âûáðàòü K ÷åëîâåê ëþáîãî ïîëà. Èñïîëüçóåì ðàñïðîñòðàíåííûé ïðèåì  ïîäñ÷åò äâóìÿ ñïîñîáàìè. Ñ îäíîé ñòîK ðîíû, ýòî ìîæíî ñäåëàòü CN ñïîñîáàìè. Ïðèìåíèì âòîðîé ñïîñîá. Ïóñòü â âû1 +N2 áðàííîé ãðóïïå ðîâíî M ìóæ÷èí è K − M æåíùèí. Ñîñòàâ òàêîé ãðóïïû ìîæíî M K−M âûáðàòü, ïî ïðàâèëó ïðîèçâåäåíèÿ, CN CN2 ñïîñîáàìè. Ïðè ýòîì M = 0, . . . , K . 1 Îñòàåòñÿ ïðèìåíèòü ïðàâèëî ñóììû.  ðàçíîñòüþ äîïîëíåíèåì ìíîæåñòâ 16 3.4 Ôîðìóëû áèíîìà è ïîëèíîìà. Áèíîìèàëüíûå è ïîëèíîìèàëüíûå êîýôôèöèåíòû Òåîðåìà 5. Ôîðìóëà áèíîìà Íüþòîíà: n (a + b) = n X Cnk an−k bk . k=0 (2) áèíîìîì Âûðàæåíèå, ñòîÿùåå â ëåâîé ÷àñòè ýòîé ôîðìóëû, íàçûâàåòñÿ (ñóììà k äâóõ ñëàãàåìûõ, âîçâåäåííàÿ â ñòåïåíü), à ÷èñëà Cn íàçûâàþòñÿ â ñâÿçè ñ ýòèì . Äîêàçàòåëüñòâî ïðîâåäåì ñ èñïîëüçîâàíèåì êîìáèíàòîðíîãî ñìûñëà, íî åñòü ìíîæåñòâî äðóãèõ ñïîñîáîâ. Çàïèøåì ëåâóþ ÷àñòü â âèäå ïðîèçâåäåíèÿ n îäèíàêîâûõ ìíîæèòåëåé: (a + b)n = (a + b)(a + b) · · · (a + b). Ïðîèçâåäåíèå ñóìì ïðåîáðàçóåì â ñóììó ïðîèçâåäåíèé. Êàæäîå ïðîèçâåäåíèå-ñëàãàåìîå ñóììû ñîäåðæèò ðîâíî n ìíîæèòåëåé, êàæäûé èç íèõ  a èëè b. Åñëè òàêîå ïðîèçâåäåíèå ñîäåðæèò ðîâíî k ìíîæèòåëåé b, òî êàæäûé èç îñòàëüíûõ n − k ìíîæèòåëåé  ýòî a. ×èñëî ñëàãàåìûõ, ñîäåðæàùèõ ðîâíî k ìíîæèòåëåé b, ðàâíî Cnk (èç ìíîæåñòâà {1, . . . , n} íîìåðîâ ïåðåìíîæàåìûõ ñóìì (a + b) âûáèðàþòñÿ k ñóìì, îò êîòîðûõ áåðåòñÿ ñëàãàåìîå b. Ñëàãàåìûå ïðåîáðàçîâàííîãî âûðàæåíèÿ îòëè÷àþòñÿ çíà÷åíèåì k , êîòîðîå ìîæåò áûòü 0, . . . , n. Îñòàåòñÿ ïðèìåíèòü ïðàâèëî ñóììû.  Ïðèìåðàìè áèíîìèàëüíîé ôîðìóëû ÿâëÿþòñÿ õîðîøî èçâåñòíûå èç øêîëüíîãî êóðñà ôîðìóëû áèíîìèàëüíûìè êîýôôèöèåíòàìè (a ± b)2 = a2 ± 2ab + b2 , (a ± b)3 = a3 ± 3a2 b + 3a2 b ± b3 è áîëåå ñëîæíûå (a±b)4 = a4 ±4a3 b+6a2 b2 ±4ab3 +b4 , Òåîðåìà 6. öèåíòîâ: (a+b)5 = a5 ±5a4 b+10a3 b2 ±10a2 b3 +5ab4 ±b5 . Ñïðàâåäëèâû ñëåäóþùèå ñâîéñòâà ñóìì áèíîìèàëüíûõ êîýôôèn X Cnk = 2n , (3) (−1)k Cnk = 0, (4) k=0 n X k=0 Cn0 + Cn2 + Cn4 + · · · = Cn1 + Cn3 + Cn5 + · · · = 2n−1 . Äîêàçàòåëüñòâî. (5) Ïåðâàÿ ñóììà  ýòî ñóììà âñåõ ýëåìåíòîâ ñòðîêè n òðåóãîëüíèêà Ïàñêàëÿ. Ðàâåíñòâî (3) ïîëó÷àåòñÿ èç (2) ïðè a = b = 1. Âòîðàÿ ñóììà 17  ýòî ñóììà âñåõ ýëåìåíòîâ ñòðîêè n òðåóãîëüíèêà Ïàñêàëÿ, èìåþùèõ ÷åðåäóþùèåñÿ çíàêè. Ðàâåíñòâî (4) ïîëó÷àåòñÿ èç (2) ïðè a = 1, b = −1. Ðàññìîòðèì òðåòüþ ñóììó. Ïîëîæèì S0 = Cn0 + Cn2 + Cn4 + · · · , S1 = Cn1 + Cn3 + Cn5 + · · · . Çàïèøåì ñóììû (3) è (4) â âèäå Cn0 + Cn1 + Cn2 + Cn3 + · · · + Cnn = 2n , Cn0 − Cn1 + Cn2 − Cn3 + · · · + (−1)n Cnn = 0. Cëîæèâ äâà ïîñëåäíèõ ðàâåíñòâà, ïîëó÷èì 2Cn0 + 2Cn2 + 2Cn4 + · · · = 2n , ò. å. 2S0 = 2n , îòêóäà S0 = 2n /2 = 2n−1 , S1 = 2n − S0 = 2n − 2n−1 = 2n−1 .  Îáîáùåíèåì áèíîìèàëüíîé ôîðìóëû ÿâëÿåòñÿ ïîëèíîìèàëüíàÿ ôîðìóëà äëÿ ñòåïåíè ñóììû m ñëàãàåìûõ, â êîòîðîé ïðèñóòñòâóþò ïîëèíîìèàëüíûe êîýôôèöèåíòû. Òåîðåìà 7 (ïîëèíîìèàëüíàÿ ôîðìóëà). X n (x1 + · · · + xm ) = k1 +···+km =n k! xk11 · · · xkmm . k1 ! · · · km ! Ñóììèðîâàíèå âåäåòñÿ ïî âñåì íåîòðèöàòåëüíûì öåëûì ÷èñëàì k1, . . . , km òàêèì, ÷òî k1 + · · · + km = n. ×èñëà íàçûâàþòñÿ k! k1 ! · · · km ! ïîëèíîìèàëüíûìè êîýôôèöèåíòàìè. Èõ ñóììà ðàâíà mn: X k1 +···+km =n k! = mn . k1 ! · · · km ! Ôîðìóëà áèíîìà  ÷àñòíûé ñëó÷àé ïîëèíîìèàëüíîé ôîðìóëû ïðè m = 2. Ïðèìåð 2. Çàïèøåì ïîëèíîìèàëüíóþ ôîðìóëó äëÿ (x1 +x2 +x3 )4 . Âû÷èñëèì 18 ïîëèíîìèàëüíâå êîýôôèöèåíòû: k1 k2 k3 4!/(k1 !k2 !k3 !) 0 0 4 1 0 1 3 4 6 0 2 2 0 3 1 4 0 4 0 1 1 0 3 4 12 1 1 2 1 2 1 12 1 3 0 4 6 2 0 2 2 1 1 12 6 2 2 0 3 0 1 4 4 3 1 0 4 0 0 1 Òåïåðü ìîæíî âûïèñàòü âñþ ôîðìóëó, èçìåíèâ äëÿ êðàñîòû ïîðÿäîê ñëàãàåìûõ: (x1 + x2 + x3 )4 = x41 + x42 + x43 + 4(x31 x2 + x1 x32 + x31 x3 + x1 x33 + x32 x3 + x2 x33 )+ +6(x21 x22 + x21 x23 + x22 x23 ) + 12(x21 x2 x3 + x1 x22 x3 + x1 x2 x23 ). 19 Âû÷èñëèì, ñ êàêîé âåðîÿòíîñòüþ P ñëàãàåìîå ðàçëîæåíèÿ (x1 + x2 + x3 + x4 ) ñîäåðæèò êâàäðàò ïåðåìåííîé. Ïî îïðåäåëåíèþ êëàññè÷åñêîé âåðîÿòíîñòè P = M/N . Íàéäåì  ÷èñëî N âñåõ ñëàãàåìûõ ðàçëîæåíèÿ. Îíè ñîîòâåòñòâóþò âåêòîðàì (k1 , k2 , k3 , k4 ) ñ íåîòðèöàòåëüíûìè öåëûìè êîîðäèíàòàìè òàêèìè, ÷òî k1 + k2 + k3 + k4 = 3. Âûïèøåì âñå òàêèå âåêòîðû (äëÿ êðàòêîñòè ñêîáêè îïóñêàåì): Ïðèìåð 3 0003, 0012, 0021, 0030, 0102, 0111, 0201, 0210, 0300, 1002, 1011, 1020, 1101, 1110, 1200, 2001, 2010, 2100, 3000. Èõ, êàê âèäèì, 19. Èç íèõ 11 ñîäåðæàò êîîðäèíàòó, ðàâíóþ 2. Òàêèì îáðàçîì, M = 11 è P = 11/19. 3.5 Ðàçìåùåíèÿ è ñî÷åòàíèÿ ñ ïîâòîðåíèÿìè Åñëè ìû âûáèðàåì ïîäìíîæåñòâî B ìîùíîñòè k ìíîæåñòâà U = {e1 , . . . , en }, óïîðÿäî÷åííîå (ðàçìåùåíèå) èëè íåóïîðÿäî÷åííîå (ñî÷åòàíèå), òî êàæäûé èç ýëåìåíòîâ e1 , . . . , en ìîæåò âõîäèòü â ïîäìíîæåñòâî B òîëüêî 0 èëè 1 ðàç (åñëè âõîäèò, òî íå ïîâòîðÿåòñÿ). Âûçûâàþò èíòåðåñ è èìåþò ñîäåðæàòåëüíûé ñìûñë è òàêèå âûáîðêè, ñîñòîÿùèå èç k ýëåìåíòîâ (èõ óæå íåëüçÿ íàçûâàòü ïîäìíîæåñòâàìè ìíîæåñòâà U ), â êîòîðûõ âûáðàííûå îáúåêòû ìîãóò ïîâòîðÿòüñÿ. Ïðîñòåéøèì ïðèìåðîì ÿâëÿþòñÿ ñëîâà ôèêñèðîâàííîé äëèíû â êîíå÷íîì àëôàâèòå. Áóêâû â îäíîì ñëîâå ìîãóò ïîâòîðÿòüñÿ. Äàäèì òî÷íûå ìàòåìàòè÷åñêèå îïðåäåëåíèÿ òàêèõ êîìáèíàòîðíûõ êîíôèãóðàöèé, íàó÷èìñÿ èõ ïîäñ÷èòûâàòü è ïðèâåäåì äðóãèå ñîäåðæàòåëüíûå ïðèìåðû. Ïóñòü U = {e1 , . . . , en }  ìíîæåñòâî ýëåìåíòîâ, ýëåìåíòû êàæäîãî òèïà èìåþòñÿ â íåîãðàíè÷åííîì êîëè÷åñòâå. Ðàññìîòðèì ñîâîêóïíîñòü èç k ýëåìåíòîâ, êàæäûé ýëåìåíò èìååò òèï èç ìíîæåñòâà U . Óïîðÿäî÷åííàÿ òàêàÿ ñîâîêóïíîñòü íàçûâàåòñÿ , íåóïîðÿäî÷åííàÿ  k n . Äëÿ ÷èñëà ðàçìåùåíèé è ñî÷åòàíèé ñ ïîk âòîðåíèÿìè ïðèíÿòû îáîçíà÷åíèÿ Ân è, ñîîòâåòñòâåííî, Ĉnk . Òåîðåìà 8. òèïîâ ðàçìåùåíèåì ñ ïîâòîðåíèÿìè âòîðåíèÿìè ïî ýëåìåíòîâ òèïîâ ñî÷åòàíèåì ñ ïî- ×èñëî ðàçìåùåíèé ñ ïîâòîðåíèÿìè îïðåäåëÿåòñÿ ôîðìóëîé Âkn = nk . Äîêàçàòåëüñòâî. Êàæäîå èç ìåñò âûáîðêè ìîæíî çàïîëíèòü ðîâíî n ñïîñîáàìè (ýëåìåíòîì ëþáîãî òèïà e1 , . . . , en ). Çàïîëíèòü íàäî âñå k ìåñò. Îñòàåòñÿ ïðèìåíèòü ïðàâèëî ïðîèçâåäåíèÿ.  Çàìå÷àíèå. Pàçìåùåíèÿ ñ ïîâòîðåíèÿìè ïî k ýëåìåíòîâ n òèïîâ âçàèìíî îäíîçíà÷íî ñîîòâåòñòâóþò ñëîâàì äëèíû k â àëôàâèòå ìîùíîñòè n. (Îáðàòèòå âíèìàíèå, ÷òî ñèìâîëû n è k ïîìåíÿëèñü ðîëÿìè, è íå ïóòàéòå!) 20 ×èñëî ñî÷åòàíèé ñ ïîâòîðåíèÿìè âûðàæàåòñÿ ÷åðåç ÷èñëî ñî÷åòàíèé áåç ïîâòîðåíèé ôîðìóëàìè Òåîðåìà 9. k n−1 Ĉnk = Cn+k−1 = Cn+k−1 . Äîêàçàòåëüñòâî. Ïóñòü B  ñî÷åòàíèå ïî k ýëåìåíòîâ n òèïîâ. Îíî îäíîçíà÷íî îïðåäåëÿåòñÿ âåêòîðîì (x1 , . . . , xn ), ãäå xj  ÷èñëî âõîæäåíèÿ â B ýëåìåíòà òèïà ej : B ↔ (x1 , . . . , xn ), n X xj = k, xj ≥ 0. j=1 Ïîëîæèì yj = xj +1, òîãäà ñî÷åòàíèþ B âçàèìíî îäíîçíà÷íî ñîîòâåòñòâóåò âåêòîð Y = (y1 , . . . , yn ), yj ∈ N, n X yj = j=1 n X j=1 (xj + 1) = n X xj + 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. 21 4 Ðåêóððåíòíûå óðàâíåíèÿ Âî ìíîãèõ êîìáèíàòîðíûõ çàäà÷àõ èñêîìûå ÷èñëà ÿâëÿþòñÿ ÷ëåíàìè íåêîòîðîé ïîñëåäîâàòåëüíîñòè, ìåæäó êîòîðûìè çàäàíî èëè âûâîäèòñÿ ñîîòíîøåíèå, íàçûâàåìîå .  îáùåì ñëó÷àå ðåêóððåíòíîå óðàâíåíèå äëÿ ÷ëåíîâ ïîñëåäîâàòåëüíîñòè 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'. Ïóñòü 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, . . .). 25 5 Ëèíåéíûå ðåêóððåíòíûå óðàâíåíèÿ 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 = m X Pj (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 íàéäåì èç íà÷àëüíûõ óñëîâèé: x0 x1 x2 x3 = B = A +B = 2A +B = 3A +B +C +D = 3 −C −2D = 2 +C +4D = 5 −C −8D = 4 27 Ýòà ñèñòåìà ëèíåéíûõ óðàâíåíèé èìååò åäèíñòâåííîå ðåøåíèå 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− 5 1+ 5 , t2 = 2 2 êðàòíîñòè 1, îáùåå ðåøåíèå èìååò âèä xn = C1 tn1 + C2 tn2 . Íà÷àëüíûå óñëîâèÿ çàäàþò ñèñòåìó óðàâíåíèé t1 = √ C1 √ +C2 = 1 (1 − 5)C1 +(1 + 5)C2 = 2 Ðåøàÿ åå è ïîäñòàâëÿÿ C1 , C2 â ôîðìóëó îáùåãî ðåøåíèÿ, íàõîäèì ïîñëå ýëåìåíòàðíûõ ïðåîáðàçîâàíèé ÷àñòíîå ðåøåíèå â êðàñèâîì âèäå √ !n+1 1  1+ 5 xn = √ − 2 5   √ !n+1 1− 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, Íîìåð âàðèàíòà N x0 = N − 1. îñòàåòñÿ òàêèì æå, êàê â ïðåäûäóùèõ çàäàíèÿõ. Ðåøåíèÿ ïðèñûëàéòå ïî ïðåæíåìó àäðåñó MeshchaninovDG@mpei.ru Ìåùàíèíîâó Äìèòðèþ Ãåðìàíîâè÷ó 29 6 Ìåòîä âêëþ÷åíèé-èñêëþ÷åíèé Îí ÷àñòî ïðèìåíÿåòñÿ äëÿ ðåøåíèÿ çàäà÷ íå òîëüêî â êîìáèíàòîðèêå è äèñêðåòíîé ìàòåìàòèêå, íî è â äðóãèõ îáëàñòÿõ. Ïðèìåð 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|. (2) Åùå äëèííåå îêàçûâàåòñÿ ôîðìóëà äëÿ |A ∪ B ∪ C ∪ D|, ïîëó÷àåìàÿ ñ èñïîëüçîâàíèåì (1) è (2): |A ∪ B ∪ C ∪ D| = |A| + |B| + |C| + |D|− −|A ∩ B| − |A ∩ C| − |A ∩ D| − |B ∩ C| − |B ∩ D| − |C ∩ D|+ +|A ∩ B ∩ C| + |A ∩ B ∩ D| + |A ∩ C ∩ D| + |B ∩ C ∩ D| − |A ∩ B ∩ C ∩ D|. (3) À êàê íàéòè |A1 ∪ · · · ∪ Am | ? Ýòî ïðèìåðû ôîðìóë âêëþ÷åíèÿ (ñîîòâåòñòâóþùåãî ñëàãàåìûì ñî çíàêîì +) è èñêëþ÷åíèÿ (ñëàãàåìûå ñî çíàêîì −). Îáùàÿ ôîðìóëèðîâêà çàäà÷è Èìååòñÿ N îáúåêòîâ, êîòîðûå ìîãóò îáëàäàòü èëè íå îáëàäàòü ñâîéñòâàìè P1 , . . . , Pm . Äëÿ êàæäîãî íàáîðà (j1 , . . . , jr ), 1 ≤ r ≤ m, 1 ≤ j1 < j2 < · · · < jr ≤ m, èçâåñòíî êîëè÷åñòâî N (j1 , . . . , jr ) îáúåêòîâ, îáëàäàþùèõ ñâîéñòâàìè Pj1 , . . . , Pjr (è, âîçìîæíî, äðóãèìè). Òðåáóåòñÿ íàéòè Nk k (0 ≤ k ≤ m) . Óêàæåì ñïîñîá âû÷èñëåíèÿ Nk . Ïîëîæèì: ÷èñëî äàþùèõ ðîâíî ñâîéñòâàìè S0 = N, 30 îáúåêòîâ, îáëà- X Sr = N (j1 , . . . , jr ), r = 1, . . . , m. (4) 1 ≤ j1 < j2 < · · · < jr ≤ m Òîãäà Nk = m X (−1)r−k Crk Sr . (5) r=k îáùåé ôîðìóëîé âêëþ÷åíèé-èñêëþ÷åíèé ( Crk  áèíî- Âûðàæåíèå (5) íàçûâàåòñÿ ìèàëüíûå êîýôôèöèåíòû). Åñëè k = 0, òî N0 = m X (−1)r Sr = N − S1 + S2 − · · · + (−1)r Sr . (6) r=0 ÷àñòíàÿ ôîðìóëà âêëþ÷åíèé-èñêëþ÷åíèé äëÿ ÷èñëà N0 îáúåêòîâ, íå îáëàäàþùèõ íè îäíèì èç ñâîéñòâ P1, . . . , Pm. Ýòî  ôîðìóëàõ âêëþ÷åíèÿ-èñêëþ÷åíèÿ ÷èñëà N (j1 , . . . , jr ) ïðåäïîëàãàþòñÿ èçâåñòíûìè, õîòÿ îíè íå âñåãäà óêàçàíû â óñëîâèè çàäà÷è.  òàêèõ ñëó÷àÿõ èõ íàäî íàéòè ñ ïîìîùüþ ïðàâèë êîìáèíàòîðíûõ âû÷èñëåíèé. Ðàññìîòðèì ðÿä ïðèìåðîâ. Âåðíåìñÿ ê ïðèìåðó 1 è èíòåðïðåòèðóåì åãî êàê ÷àñòíûé ñëó÷àé ðàññìîòðåííîé îáùåé ïîñòàíîâêè çàäà÷è. Îáúåêòû çäåñü  ýëåìåíòû ìíîæåñòâà U = = A1 ∪ · · · ∪ Am , ïðè ýòîì N = |U |, ñâîéñòâî Pj ñîñòîèò â ïðèíàäëåæíîñòè ýëåìåíòà ìíîæåñòâó Aj , j = 1, . . . , m. Êàæäûé èç ýëåìåíòîâ ïðèíàäëåæèò õîòÿ áû îäíîìó ìíîæåñòâó Aj , ò. å. êàæäûé îáúåêò îáëàäàåò õîòÿ áû îäíèì èç ñâîéñòâ, ïîýòîìó N0 = 0. Óñëîâèå "îáúåêò îáëàäàåò ñâîéñòâàìè Pj1 , . . . , Pjr " ðàâíîñèëüíî ïðèíàäëåæíîñòè ýëåìåíòà ïåðåñå÷åíèþ Aj1 ∩ · · · ∩ Ajr , ïîýòîìó N (j1 , . . . , jr ) = = |Aj1 ∩ · · · ∩ Ajr |. Ïîäñòàâëÿÿ ýòè çíà÷åíèÿ â (4), (6), ïîëó÷àåì,  0 = |U | +  m X  X (−1)r |Aj1 ∩ · · · ∩ Ajr | , 1 ≤ j1 < j2 < · · · < jr ≤ m r=1 îòêóäà  |U | = |A1 ∪ · · · ∪ Am | = −  m X  X (−1)r r=1 |Aj1 ∩ · · · ∩ Ajr | , 1 ≤ j1 < j2 < · · · < jr ≤ m ò.å.  |A1 ∪ · · · ∪ Am | =  m X r=1  X (−1)r+1 |Aj1 ∩ · · · ∩ Ajr | . 1 ≤ j1 < j2 < · · · < jr ≤ m Ïðè m = 2, 3, 4 ýòà îáùàÿ ôîðìóëà èìååò âèä (1), (2) è (3) ñîîòâåòñòâåííî. 31 Ïðèìåð 2. Íàéäåì êîëè÷åñòâî π(100) ïðîñòûõ ÷èñåë p òàêèõ, ÷òî p ≤ 100. Íàòóðàëüíîå ÷èñëî p íàçûâàåòñÿ ïðîñòûì, åñëè p ≥ 2 è åãî äåëèòåëÿìè ÿâëÿþòñÿ òîëüêî 1 è ñàìî p. Äëÿ ýòîãî âîñïîëüçóåìñÿ äàâíî (åùå â àíòè÷íûå âðåìåíà) èçâåñòíîé òåîðåìîé: ÷èñëî m ïðîñòîå òîãäà è òîëüêî òîãäà, êîãäà îíî íå äåëèòñÿ íè √ íà îäíî ïðîñòîå ÷èñëî q òàêîå, ÷òî q ≤ m. Äîêàçàòü òåîðåìó î÷åíü ëåãêî: íàäî ðàçëîæèòü ÷èñëî íà ïðîñòûå ìíîæèòåëè, òàêîå ðàçëîæåíèå äëÿ ëþáîãî íàòóðàëüíîãî åäèíñòâåííî ñ òî÷íîñòüþ äî ïîðÿäêà çàïèñè ìíîæèòåëåé. Íàéäåì êîëè÷åñòâî íàòóðàëüíûõ ÷èñåë ñðåäè ïåðâûõ 100, íå äåëÿùèõñÿ íè íà 2, íè íà 3, íè íà 5, íè íà 7. Áóäåì ñ÷èòàòü ÷èñëà 1, . . . , 100 îáúåêòàìè, äåëèìîñòü íà q  ñâîéñòâîì Pq . Òîãäà N = S0 = 100, N (2) = 100/2 = 50, N (3) = b100/3c = 33, N (5) = 100/5 = 20, N (7) = b100/7c = 14, N (2, 3) = b100/6c = 16, N (2, 5) = 100/10c = 10, N (2, 7) = b100/14c = 7, N (3, 5) = b100/15c = 6, N (3, 7) = b100/21c = 4, N (5, 7) = b100/35c = 2, N (2, 3, 5) = b100/30c = 3, N (2, 3, 7) = b100/42c = 2, N (2, 5, 7) = b100/70c = 1, N (3, 5, 7) = b100/105c = 0, N (2, 3, 5, 7) = b100/210c = 0, S1 = N (2) + N (3) + N (5) + N (7) = 117, S2 = N (2, 3) + N (2, 5) + N (2, 7) + N (3, 5) + N (3, 7) + N (5, 7) = 45, S(3) = N (2, 3, 5) + N (2, 3, 7) + N (2, 5, 7) + N (3, 5, 7) = 6, S4 = N (2, 3, 5, 7) = 0. Ïî ôîðìóëå (6) ïîëó÷àåì N0 = S0 − S1 + S2 − S3 + S4 = 100 − 117 + 45 − 6 + 0 = 22. Ñðåäè ýòèõ 22 ÷èñåë îêàçûâàåòñÿ è ÷èñëî 1, íå ÿâëÿþùååñÿ ïðîñòûì ïî îïðåäåëåíèþ, à ïðîñòûå ÷èñëà 2, 3, 5, 7 îòñóòñòâóþò, ïîýòîìó π(100) = 22 − 1 + 4 = 25. Âîò âñå ïðîñòûå ÷èñëà íå áîëüøèå, ÷åì 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. Çàìåòèì, ÷òî ñëåäóþùåå ÷èñëî 101 òàêæå ïðîñòîå. 4 Ïðèìåð 3. Òàêèì æå îáðàçîì ìîæíî àíàëèçèðîâàòü ïåðåñòàíîâêè ñ íåïîäâèæ- íûìè ýëåìåíòàìè. Îáúåêòû  âñå m! ïåðåñòàíîâîê α(x) ýëåìåíòîâ x = 1, 2, . . . , m. 4 îáùåì ñëó÷àå ñîîòíîøåíèå x ln x ïðè x → ∞ äëÿ ëþáîãî âåùåñòâåííîãî ïîëîæèòåëüíîãî ÷èñëà x óñòàíîâëåíî âî âòîðîé ïîëîâèíå XIX â. ðóññêèì ìàòåìàòèêîì è ìåõàíèêîì ×åáûø¼âûì Ïàôíóòèåì Ëüâîâè÷åì è ôðàíöóçñêèìè ìàòåìàòèêàìè Æàêîì Àäàìàðîì è Øàðëåì äå ëà Âàëëå Ïóññåíîì. π(x) ∼ 32 Ñâîéñòâî Pj ñîñòîèò â íåïîäâèæíîñòè ýëåìåíòà j (α(j) = j ), j = 1, . . . , m, ò. å. ïåðåñòàâëÿþòñÿ òîëüêî ýëåìåíòû, îòëè÷íûå îò j . Òîãäà N = m!, N (j1 , . . . , jr ) = (m − r)!, ÷èñëî ïåðåñòàíîâîê, èìåþùèõ ðîâíî k íåïîäâèæíûõ ýëåìåíòîâ, íàõîäèòñÿ êàê Nk ïî ôîðìóëå (5). Çàäàíèå äëÿ ñàìîñòîÿòåëüíîãî ðåøåíèÿ 6. Íàéäèòå ÷èñëî ïåðåñòàíîâîê ýëåìåíòîâ íî k 1, . . . , m, îñòàâëÿþùèõ ðîâ- ýëåìåíòîâ íåïîäâèæíûìè. N 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Íîìåð âàðèàíòà N m 4 5 4 6 4 5 5 5 4 5 6 5 7 6 7 6 k 1 1 1 2 2 3 3 4 2 5 7 3 6 4 îñòàåòñÿ òàêèì æå, êàê â ïðåäûäóùèõ çàäàíèÿõ. Ðåøåíèÿ ïðèñûëàéòå ïî ïðåæíåìó àäðåñó MeshchaninovDG@mpei.ru Ìåùàíèíîâó Äìèòðèþ Ãåðìàíîâè÷ó 7 Îñíîâíûå ïîíÿòèÿ òåîðèè ãðàôîâ Âàæíûì èíñòðóìåíòîì äèñêðåòíîé ìàòåìàòèêè ÿâëÿþòñÿ ãðàôû. íàçûâàåòñÿ ïàðà ìíîæåñòâ G = (V, E), V = {v1 , . . . , vn }, E = {e1 , . . . , em }. Ýëåìåíòû vi ìíîæåñòâà V íàçûâàþòñÿ ãðàôà G, ýëåìåíòû ej ìíîæåñòâà E  , ýòî ïàðû ej = {vj1 , vj2 } ðàçëè÷íûõ âåðøèí. Åñëè âåðøèíû Ãðàôîì ðåáðàìè âåðøèíàìè 33 ñìåæíûìè vj1 , vj2 îáðàçóþò ðåáðî ej , îíè íàçûâàþòñÿ , ïðè ýòîì âåðøèíà vj1 è ðåáðî ej íàçûâàþòñÿ äðóã äðóãó, ýòî æå ñïðàâåäëèâî è äëÿ âåðøèíû vj2 è òîãî æå ðåáðà ej . ×èñëî ðåáåð, èíöèäåíòíûõ âåðøèíå vi , íàçûâàåòñÿ ñòåïåíüþ ýòîé âåðøèíû è îáîçíà÷àåòñÿ d(vi ). V E ( n m). Ïðèìåð 1. Ðàññìîòðèì ãðàô G ñî ñëåäóþùèìè âåðøèíàìè è ðåáðàìè: èíöèäåíòíûìè V = {v1 , . . . , v7 }, E = {e1 , e2 , e3 , e4 , e5 }, e1 = {v1 , v2 }, e2 = {v1 , v3 }, e3 = {v2 , v3 }, e4 = {v2 , v4 }, e5 = {v5 , v6 }. Òîãäà n = 7, m = 5, G íåîðèåíòèðîâàííûé è èìååò ñëåäóþùèå ñòåïåíè âåðøèí: i 1 2 3 4 5 6 7 d(vi ) 2 3 2 1 1 1 0 Åñëè ñëîæèòü ñòåïåíè, òî ïîëó÷èì 2 + 3 + 2 + 1 + 1 + 1 + 0 = 2 · 5. Òåîðåìà 1. Ñóììà ñòåïåíåé âñåõ âåðøèí ãðàôà ðàâíà óäâîåííîìó ÷èñëó ðåáåð: n X d(vi ) = 2m. (1) i=1 Äîêàçàòåëüñòâî. Ïóñòü d(vi , vj )  ýòî ÷èñëî ðåáåð, ñîåäèíÿþùèõ âåðøèíû vi è vj . Òîãäà d(vi , vj ) = d(vj , vi ) ∈ {0, 1}, n X i=1 d(vi ) = n n X X d(vi , vj ) = n n X X d(vi , vj ), j=1 i=1 i=1 j=1 è â ëåâîé ÷àñòè ðàâåíñòâà (1) êàæäîå ðåáðî ó÷òåíî ðîâíî äâàæäû: â ñëàãàåìûõ d(vi ) è d(vj ).  Ñëåäñòâèå 1. .  ïðèìåðå 1 ÷åòûðå âåðøèíû íå÷åòíîé ñòåïåíè v2 , v4 , v5 , v6 . Âåðøèíà v7 èìååò ÷åòíóþ ñòåïåíü 0, òàêàÿ âåðøèíà íàçûâàåòñÿ . Ïðèâåäåì ïðèìåð, â êîòîðîì ãðàôû è ñòåïåíè âåðøèí ïðèìåíÿþòñÿ äëÿ ðåøåíèÿ ëîãè÷åñêîé çàäà÷è. Ïðèìåð 2. Ó÷åíèêè îäíîãî êëàññà ïðîâîäèëè íà óðîêå ìàòåìàòèêè êðóãîâîé òóðíèð ïî èãðå â "êðåñòèêè-íîëèêè". Ó÷àñòíèêîâ áûëî ïÿòåðî. Êîãäà ïðîçâåíåë çâîíîê ñ óðîêà, òóðíèð ïðåðâàëè, â ýòîò ìîìåíò îêàçàëîñü ñûãðàíî 6 ïàðòèé. Áîëüøå âñåãî èãð, ïî òðè, ïðîâåëè òîëüêî Àëåíà è Âàñÿ. Ñêîëüêî èãð ïðîâåëè îñòàëüíûå ó÷àñòíèêè? Êòî ñ êåì èãðàë? Îïèøåì òóðíèð ãðàôîì ñ 5 âåðøèíàìè, ñîîòâåòñòâóþùèìè ó÷àñòíèêàì. Ñîåäèíèì ïàðó âåðøèí ðåáðîì, åñëè ñîîòâåòñòâóþùèå ó÷àñòíèêè ñûãðàëè äðóã ñ äðóãîì. Íàçîâåì ó÷àñòíèêîâ À (Àëåíà),  (Âàñÿ), Ñ(Ñàøà), D (Äàøà) è Å (Åãîð), ×èñëî âåðøèí íå÷åòíîé ñòåïåíè â ãðàôå ÷åòíî èçîëèðîâàííîé 34 òàê æå îáîçíà÷èì è âåðøèíû. Òîãäà ÷èñëî ïàðòèé, ñûãðàííûì êàæäûì ó÷àñòíèêîì X , åñòü ñòåïåíü d(X) âåðøèíû X . B ñèëó òåîðåìû 1 èìååì d(A) + d(B) + d(C) + d(D) + d(E) = 2 · 6, d(A) = d(B) = 3. Íå îãðàíè÷èâàÿ îáùíîñòè, ïîëàãàåì d(C) ≥ d(D) ≥ d(E). Òîãäà d(C) < 3 è d(C), d(D), d(E) ∈ {0, 1, 2}, (2) d(C) + d(D) + d(E) = 6. (3) Åñëè d(E) = 0, òî d(C) + d(D) = 6 è óñëîâèÿ (2) è (3) íå ìîãóò âûïîëíÿòüñÿ îäíîâðåìåííî. Åñëè d(E) = 1, òî d(C) + d(D) = 5 è óñëîâèÿ (2) è (3) òàêæå íå âûïîëíÿþòñÿ îäíîâðåìåííî. Îñòàåòñÿ åäèíñòâåííàÿ âîçìîæíîñòü d(E) = 2. Ïðè ýòîì è d(C) = d(D) = 2. Íåîáõîäèìî ïðîâåðèòü, ÷òî òàêàÿ âîçìîæíîñòü äåéñòâèòåëüíî ðåàëèçóåòñÿ, ò. å. ïîñòðîèòü ãðàô òóðíèðà. Ýòî ìîæíî ñäåëàòü åäèíñòâåííûì ñïîñîáîì, ñîîòâåòñòâóþùèì ñëåäóþùåìó ìíîæåñòâó èç 6 èãðàâøèõ ïàð (ðåáåð ãðàôà): A è C , A è D, A è E , B è C , B è D, B è E . Ðàññìîòðèì ñïîñîáû çàäàíèÿ ãðàôîâ. 1. Óêàçàíèåì ñïèñêîâ âåðøèí è ðåáåð. Ýòèì ñïîñîáîì áûëè çàäàíû ãðàôû â ïðèâåäåííûõ ïðèìåðàõ. 2. Äèàãðàìîé íà ïëîñêîñòè (ãðàôè÷åñêèì èçîáðàæåíèåì). Âåðøèíàì ñîîòâåòñòâóþò òî÷êè íà ïëîñêîñòè, èõ ðàñïîëîæåíèå íå èìååò çíà÷åíèÿ. Ðåáðà ãðàôà èçîáðàæàþòñÿ îòðåçêàìè èëè äóãàìè êðèâûõ, ñîåäèíÿþùèìè ïàðû òî÷åê. Ãðàôû èç ïðèìåðîâ 1 è 2 ìîæíî çàäàòü ñëåäóþùèìè èçîáðàæåíèÿìè. v1 e1 r r v2 A r v5


e2 e3



e4 e5 v7 r



v3
r r v4 r v6 C e eB CC CS CS   C  C S  C S   C S  C  C  C C S  C S C    C C   S S C C    S C C    SC C   SCr E  r D Cr 3. Ìàòðèöàìè èç íóëåé è åäèíèö. A(G) ãðàôà G = ({v1 , . . . , vn }, {e1 , . . . , em })  êâàäðàòíàÿ ïîðÿäêà n, îíà óñòðîåíà ñëåäóþùèì îáðàçîì: A(G) = (aij )n × n , ãäå Ìàòðèöà ñìåæíîñòè  aij = 1, 0, åñëè âåðøèíû vi è vj ñìåæíû, â ïðîòèâíîì ñëó÷àå. 35 Ìàòðèöà A(G) ñèììåòðè÷íà, åå äèàãîíàëüíûå ýëåìåíòû ðàâíû 0, ÷èñëî åäèíèö â ñòðîêå i (êàê è ÷èñëî åäèíèö â ñòîëáöå i) ðàâíî d(vi ), îáùåå ÷èñëî åäèíèö â ìàòðèöå ðàâíî 2m. B(G) ãðàôà G èìååò ðàçìåð m × n, B(G) = (bij )m × n , ãäå  1, åñëè ðåáðî ei è âåðøèíà vj èíöèäåíòíû, bij = 0, â ïðîòèâíîì ñëó÷àå. Ìàòðèöà èíöèäåíöèé Êàæäàÿ ñòðîêà ìàòðèöû B(G) ñîäåðæèò ðîâíî äâå åäèíèöû, ÷èñëî åäèíèö â ñòîëáöå j ðàâíî d(vj ). Ìàòðèöû è ñïèñêè ïðèìåíÿþòñÿ ïðè ðåøåíèè çàäà÷ î ãðàôàõ íà êîìïüþòåðå. Ïðè "ðó÷íîì" ðåøåíèè çàäà÷ íà íåáîëüøèõ ãðàôàõ ïðèâû÷íåå äèàãðàììû, îíè îáëàäàþò íàãëÿäíîñòüþ è ëàêîíè÷íîñòüþ. Êàæäûé èç ñïîñîáîâ ïîëíîñòüþ îïðåäåëÿåò ãðàô è ëåãêî ïðåîáðàçóåòñÿ â äðóãîé ñïîñîá ïðåäñòàâëåíèÿ ýòîãî æå ãðàôà. Ìû ÷àñòî áóäåì èñïîëüçîâàòü ìàòðèöû è ñïèñêè, ÷òîáû íå ðèñîâàòü äèàãðàììû. Äëÿ ãðàôà èç ïðèìåðà 1 ïîëó÷àåì       A(G) =      1 1 1 1 1 1 1 1 1 1           . B(G) =        1 1 1 1 1 1 1 1 1 1    .   Ìåòîäàìè êîìáèíàòîðíûõ âû÷èñëåíèé íåòðóäíî ïîëó÷èòü ×èñëî ðàçëè÷íûõ ãðàôîâ, èìåþùèõ âåðøèíû v1, . . . , vn, ðàâíî . ×èñëî ðàçëè÷íûõ ãðàôîâ, èìåþùèõ âåðøèíû v1, . . . , vn è ðîâíî m m ðåáåð, ñîñòàâëÿåò Cn(n . − 1)/2 Ââåäåì åùå íåñêîëüêî âàæíåéøèõ ïîíÿòèé. Ìàðøðóò, ñîåäèíÿþùèé âåðøèíû vi è vj ãðàôà,  ýòî ÷åðåäóþùàÿñÿ ïîñëåäîâàòåëüíîñòü èíöèäåíòíûõ äðóã äðóãó Ñëåäñòâèå 2. 2n(n − 1)/2 âåðøèí è ðåáåð, êðàéíèìè ýëåìåíòàìè êîòîðîé ÿâëÿþòñÿ vi è vj . Åñëè vi = vj , òî ìàðøðóò íàçûâàåòñÿ . ×èñëî ðåáåð â ìàðøðóòå íàçûâàåòñÿ åãî .  ãðàôå èç ïðèìåðà 1 ïîñëåäîâàòåëüíîñòü v1 e1 v2 e4 v4 e4 v2 e3 v3 îáðàçóåò ìàðøðóò äëèíû 4, ïîñëåäîâàòåëüíîñòü v1 e1 v2 e3 v3 e2 v1  öèêë äëèíû 3. Ãðàô íàçûâàåòñÿ , åñëè ëþáûå äâå åãî âåðøèíû ìîæíî ñîåäèíèòü íåêîòîðûì ìàðøðóòîì. Ãðàô G1 (V1 , E1 ) íàçûâàåòñÿ G(V, E), åñëè öèêëîì äëèíîé ñâÿçíûì ïîäãðàôîì ãðàôà 36 ìíîæåñòâà åãî âåðøèí è ðåáåð îáðàçóþò ïîäìíîæåñòâà V1 ⊆ V , E1 ⊆ E . Ìàêñèìàëüíûé ñâÿçíûé ïîäãðàô ãðàôà íàçûâàåòñÿ åãî . Ñâÿçíûé ãðàô èìååò ðîâíî îäíó êîìïîíåíòó ñâÿçíîñòè. Åñëè èìååòñÿ íå ìåíåå äâóõ êîìïîíåíò, ãðàô íåñâÿçåí. Åñëè ãðàô G èìååò n âåðøèí è k ≥ 2 êîìïîíåíò, ñîäåðæàùèõ n1 , . . . nk âåðøèí, n1 + · · · + nk = n, òî åãî ìàòðèöà ñìåæíîñòè ðàçáèâàåòñÿ íà áëîêè  ïîäìàòðèöû ïîðÿäêîâ n1 , . . . , nk , îêðóæåííûå ëèøü íóëåâûìè ýëåìåíòàìè. (Ýòî õîðîøî âèäíî â ìàòðèöå äëÿ ãðàôà èç ïðèìåðà 1, â äðóãèõ ñëó÷àÿõ äëÿ áîëüøåé íàãëÿäíîñòè óäîáíî ïðîâåñòè ïåðåñòàíîâêó ñòðîê (è ñòîëáöîâ) ìàòðèöû A(G).) Ãðàô èç ïðèìåðà 1 íåñâÿçåí, îí èìååò òðè êîìïîíåíòû êîìïîíåíòîé ñâÿçíîñòè G1 = ({v1 , v2 , v3 , v4 }, {e1 , e2 , e3 , e4 }), ãðàô èç ïðèìåðà 2 G2 = ({v5 , v6 }, {e5 }), G3 = ({v7 }, ∅); ñâÿçåí. Ýéëåðîâûì 5 Íåêîòîðûå öèêëû îñîáåííî âàæíû. íàçûâàåòñÿ öèêë, ïðîõîäÿùèé ÷åðåç êàæäîå ðåáðî ãðàôà ðîâíî îäèí ðàç. Åñëè, íàïðèìåð, âåðøèíû ãðàôà ñîîòâåòñâóþò ïóíêòàì íà ìåñòíîñòè, à ðåáðà  äîðîãàì, ñîåäèíÿþùèì ýòè ïóíêòû, òî ýéëåðîâ öèêë äàåò âîçìîæíîñòü îêàçàòüñÿ íà êàæäîé äîðîãå (÷òîáû âûïîëíèòü êàêîå-ëèáî äåéñòâèå íà íåé, íàïðèìåð, óñòàíîâèòü çíàê) ðîâíî îäèí ðàç è âåðíóòüñÿ â ìåñòî ñòàðòà.  òàêîé ïîñòàíîâêå ýòà çàäà÷à è ïîÿâèëàñü âïåðâûå, â 1752 ã., êàê çàäà÷à î êåíèãñáåðãñêèõ ìîñòàõ. Ðîëü âåðøèí ãðàôà èãðàëè ó÷àñòêè ñóøè  áåðåãà è îñòðîâà ïðîòåêàþùåé â ã. Êåíèãñáåðãå (íûíå Êàëèíèíãðàä) ðåêè Ïðåãîëü, ðåáåð  ìîñòû. Ëåîíàðä Ýéëåð, ðàáîòàâøèé â òî âðåìÿ â Ïåòåðáóðãñêîé Àêàäåìèè íàóê, äàë èñ÷åðïûâàþùåå ðåøåíèå çàäà÷è. Èì äîêàçàíà Òåîðåìà 2. Ýéëåðîâ öèêë â ãðàôå ñóùåñòâóåò òîãäà è òîëüêî òîãäà, êîãäà âûïîëíåíû äâà óñëîâèÿ: 1) ãðàô ñâÿçåí, 2) ñòåïåíü êàæäîé âåðøèíû ÷åòíà. Ýòîò ôàêò èíîãäà íàçûâàþò èñòîðè÷åñêè ïåðâîé òåîðåìîé òåîðèè ãðàôîâ, õîòÿ Ë. Ýéëåð è åãî ñîâðåìåííèêè òàêîãî ïîíÿòèÿ íå çíàëè è íå ââîäèëè.  ïðèìåðe 1 ýéëåðîâà öèêëà íåò, òàê êàê ãðàô G íå ÿâëÿåòñÿ ñâÿçíûì. Ýéëåðîâà öèêëà íåò è â êîìïîíåíòå ñâÿçíîñòè G1 ýòîãî ãðàôà, òàê êàê âåðøèíû v2 , v4 , v5 , v6 èìåþò íå÷åòíûå ñòåïåíè. 5 Ëåîíàðä Ðîññèè Ýéëåð (17071783)  ìàòåìàòèê, ôèçèê è àñòðîíîì, ðîäèëñÿ â Øâåéöàðèè, ðàáîòàë â Ãåðìàíèè è 37 Ïðèìåð 3. Ïóñòü ãðàô çàäàí ìàòðèöåé ñìåæíîñòè     A(G) =     1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1     .    Ìàòðèöà A(G) íå ðàçáèâàåòñÿ íà áëîêè, ïîýòîìó ãðàô ñâÿçåí. ×èñëî åäèíèö â êàæäîé ñòðîêå ÷åòíî, ò. å ñòåïåíü êàæäîé âåðøèíû ÷åòíà. Ïî òåîðåìå 2 ñóùåñòâóåò ýéëåðîâ öèêë. Óêàæåì ðåáðà â ïîðÿäêå èõ ïðîõîæäåíèÿ ýéëåðîâûì öèêëîì: e1 = {v1 , v2 }, e2 = {v2 , v3 }, e3 = {v3 , v6 }, e4 = {v6 , v2 }, e5 = {v2 , v4 }, e6 = {v4 , v6 }, e7 = {v6 , v5 }, e8 = {v5 , v4 }, e9 = {v4 , v1 }. Ãàìèëüòîíîâûì6 íàçûâàåòñÿ öèêë, ïðîõîäÿùèé ðîâíî îäèí ðàç ÷åðåç êàæäóþ âåðøèíó ãðàôà. Çàäà÷à î ñóùåñòâîâàíèè ãàìèëüòîíîâà öèêëà, èçâåñòíà ñ XIX â. è, â îòëè÷èå îò çàäà÷è îá ýéëåðîâîì öèêëå, íå ðåøåíà äî ñèõ ïîð.  ãðàôå èç ïðèìåðà 3 åñòü ãàìèëüòîíîâ öèêë (v1 , v2 , v3 , v6 , v5 , v4 , v1 ) (óêàçàíû òîëüêî âåðøèíû), â ïðèìåðå 1 îí îòñóòñòâóåò â ñèëó íåñâÿçíîñòè ãðàôà. Ðàññìîòðèì ïðèìåð 2. Öèêë, ñîäåðæàùèé âåðøèíû A è B , ïðèâîäèò âíîâü â îäíó èç ýòèõ âåðøèí, òàê êàê êàæäàÿ èç âåðøèí C, D, E ñìåæíà òîëüêî ñ A è B . Òàêèì îáðàçîì, ãàìèëüòîíîâ öèêë â ýòîì ãðàôå îòñóòñòâóåò. Âî ìíîãèõ ïðèêëàäíûõ çàäà÷àõ èñïîëüçóþòñÿ ãðàôû, íàçûâàåìûå äåðåâüÿìè. Äåðåâî  ýòî ñâÿçíûé ãðàô áåç öèêëîâ.Äåðåâüÿìè óäîáíî ïðåäñòàâëÿòü èåðàðõè÷åñêèå ñòðóêòóðû, ò. å. ìíîæåñòâà îáúåêòîâ, èç êîðûõ îäíè íàõîäÿòñÿ â ïîä÷èíåíèè îòíîñèòåëüíî äðóãèõ. Âñåì èçâåñòíû ãåíåàëîãè÷åñêèå äåðåâüÿ, îïèñûâàþùèå ðîäîñëîâíûå ñåìåé â èñòîðèè, ïðîèñõîæäåíèå îðãàíèçìîâ è âèäîâ â áèîëîãèè, ñòðóêòóðû äàííûõ â èíôîðìàòèêå è ìíîãîå äðóãîå. Âîò îäèí èç ïðèìåðîâ äåðåâà. 6 Óèëüÿì Ãàìèëüòîí (18051865)  èðëàíäñêèé ìàòåìàòèê. Çàäà÷ó î òàêîì öèêëå â ãðàôå ñ 20 âåðøèíàìè îí èñïîëüçîâàë â 1859 ã. êàê îñíîâó äëÿ èãðóøêè-ãîëîâîëîìêè, ïîëó÷èâ ïàòåíò è íàëàäèâ (õîòÿ è áåç êîììåð÷åñêîãî óñïåõà) åå ïðîèçâîäñòâî. 38 Ïðèìåð 4. ev5 @ @ @ ev6 ev7 @uv3 ruv4 @ @ @ @ @ uv2 @ @ @ @ @ @ @ @ @e v1 Äåðåâî îáëàäàåò çàìå÷àòåëüíûìè ñâîéñòâàìè. Óêàæåì íåêîòîðûå èç íèõ. Òåîðåìà 3. G n m Åñëè  äåðåâî, èìåþùåe âåðøèí è ðåáåð, òî 1) m = n − 1; 2) ëþáûå äâå ðàçëè÷íûå âåðøèíû ñîåäèíåíû åäèíñòâåííûì ìàðøðóòîì áåç ïîâòîðåíèé âõîäÿùèõ â íåãî âåðøèí è ðåáåð; 3) ïðè óäàëåíèå ëþáîãî ðåáðà îáðàçóåòñÿ ðîâíî äâå êîìïîíåíòû ñâÿçíîñòè: 4) ïðè äîáàâëåíèè ðåáðà, ñîåäèíÿþùåãî ëþáûå äâå íå ñìåæíûå ïðåæäå âåðøèíû, îáðàçóåòñÿ ðîâíî îäèí öèêë. Ýòè ñâîéñòâà ëåãêî âèäåòü íà äèàãðàììå èç ïðèìåðà 4. ñ âåðøèíàìè v1 , . . . , vn íàçûâàåòñÿ íàáîð  íàòóðàëüíûõ ÷èñåë c1 , . . . cn , ïðèïèñàííûõ âåðøèíàì òàê, ÷òî ëþáûå äâå ñìåæíûå âåðøèíû vi è vj èìåþò ðàçëè÷íûå öâåòà ci 6= cj . Ìèíèìàëüíîå ÷èñëî öâåòîâ, äîñòàòî÷íîå äëÿ ðàñêðàñêè ãðàôà G, íàçûâàåòñÿ åãî χ(G). Ãðàô íàçûâàåòñÿ , åñëè îí ñîäåðæèò n âåðøèí è âñå n(n − 1)/2 ðåáåð, ñîåäèíÿþùèõ âñå ïàðû âåðøèí. Êàæäûé âíåäèàãîíàëüíûé ýëåìåíò ìàòðèöû ñìåæíîñòè ïîëíîãî ãðàôà ðàâåí 1. Ïîëíûé ãðàô, èìåþùèé n âåðøèí, îáîçíà÷àåòñÿ Kn . Òåîðåìà 4 (ñâîéñòâà õðîìàòè÷åñêîãî ÷èñëà). 1. G n χ(G) ≤ n Ðàñêðàñêîé ãðàôà öâåòîâ ïîëíûì õðîìàòè÷åñêèì ÷èñëîì Åñëè ãðàô ñîäåðæèò ðîâíî âåðøèí, òî . 2. Åñëè ãðàô G ñîäåðæèò ïîäãðàô G1 , òî χ(G) ≥ χ(G1 ). 3. χ(Kp ) = p. 4. Åñëè ãðàô G ñîäåðæèò ïîäãðàô Kp , òî χ(G) ≥ p. 5. Åñëè n ≥ 3 è ãðàô Cn ïðåäñòàâëÿåò ñîáîé n-óãîëüíèê (öèêë èç n âåðøèí è 39 n ðåáåð, ïðè ýòîì C3 = K3), òî åñëè n ÷åòíî, åñëè n íå÷åòíî. 6. Åñëè ãðàô G  äåðåâî, òî χ(G) = 2. 7. Åñëè ãðàô G ïëàíàðíûé, ò. å. ìîæåò áûòü èçîáðàæåí äèàãðàììîé íà ïëîñêîñòè, â êîòîðîé ðåáðà ïåðåñåêàþòñÿ òîëüêî â âåðøèíàõ, òî χ(G) ≤ 4 (òåîðåìà î 4 êðàñêàõ).  χ(Cn ) = 2, 3, Ïðîñòåéøèìè íåïëàíàðíûìè ãðàôàìè ÿâëÿþòñÿ K5 è K3,3 . K5 u B@@  B @  B @  B @  B @  B @  B @  B u @u  B b " " Bbb "  B  B b "  B b  B " b "  B b "B b "  B  B b "  b  B " B " b B  B  b " b B  B  "" b bBu B" u u e @
A@
A A@

A @
A @ K3,3
A @ @
A @
A
@ A
@ A @ A
@e u A
@
A @ @
A @
A
@ A A
@
@ A
@ A
@ A
@ A
@A u
@ Ae  ñèëó ñâîéñòâà 3 èìååì χ(K5 ) = 5. À äëÿ âòîðîãî ãðàôà, êàê íåòðóäíî ïðîâåðèòü, χ(K3,3 ) = 2.  ïðèìåðå 1 ãðàô G cîäåðæèò òðåóãîëüíèê, ïîýòîìó χ(G) ≥ 3. Ñ äðóãîé ñòîðîíû, ìîæíî ïîñòðîèòü ðàñêðàñêó â 3 öâåòà, íàïðèìåð, c(v3 ) = c(v4 ) = c(v6 ) = c(v7 ) = 1, c(v1 ) = c(v5 ) = 2, c(v2 )3, ïîýòîìó χ(G) ≤ 3. Òàêèì îáðàçîì, χ(G) = 3. Ãðàôû èç ïðèìåðîâ 2 è 3 èìåþò õðîìàòè÷åñêèå ÷èñëà 2 è 3 ñîîòâåòñòâåííî. Äåðåâî èç ïðèìåðà 4 èìååò â ñèëó ñâîéñòâà 6 õðîìàòè÷åñêîå ÷èñëî 2, íà äèàãðàììå ïðåäñòàâëåíà åãî ðàñêðàñêà â 2 öâåòà (òåìíûå è ñâåòëûå êðóæêè). 40 Çàäàíèå äëÿ ñâìîñòîÿòåëüíîãî ðåøåíèÿ Ïîñòðîéòå ìàòðèöû ñìåæíîñòè è èíöèäåíöèé ãðàôà. Ïîñòðîéòå ýéëåðîâ è ãàìèëüòîíîâ öèêëû èëè äîêàæèòå, ÷òî ñîîòâåòñòâóþùèé öèêë íå ñóùåñòâóåò. Íàéäèòå õðîìàòè÷åñêîå ÷èñëî è îïòèìàëüíóþ ðàñêðàñêó âåðøèí ãðàôà. Âñå ãðàôû èìåþò ìíîæåñòâî âåðøèí {1, 2, 3, 4, 5, 6}. Ðåáðà îïðåäåëÿ- þòñÿ â âàðèàíòå çàäàíèÿ. Äëÿ êðàòêîñòè îíè óêàçûâàþòñÿ áåç ñêîáîê è çàïÿòûõ. 1. Ðåáðà 12, 14, 23, 24, 35, 36, 45, 56. 2. Ðåáðà 12, 14, 16, 23, 25, 26, 36, 45. 3. Ðåáðà 12, 14, 24, 25, 35, 36, 45, 56. 4. Ðåáðà 12, 14, 23, 24, 25, 35, 36, 45. 5. Ðåáðà 12, 14, 15, 23, 26, 35, 45, 56. 6. Ðåáðà 12, 14, 23, 24, 25, 35, 36, 56. 7. Ðåáðà 12, 14, 23, 24, 26, 36, 45, 56. 8. Ðåáðà 12, 14, 15, 25, 34, 36, 45, 56. 9. Ðåáðà 12, 13, 14, 24, 25, 26, 36, 45. 10. Ðåáðà 12, 13, 14, 23, 24, 36, 45, 56. 11. Ðåáðà 12, 14, 16, 23, 25, 35, 45, 46. 12. Ðåáðà 12, 13, 14, 23, 25, 45, 46, 56. 13. Ðåáðà 12, 14, 25, 26, 35, 36, 45, 56. 14. Ðåáðà 12, 14, 15, 23, 26, 35, 36, 45. 15. Ðåáðà 12, 14, 23, 24, 25, 26, 35, 45. 16. Ðåáðà 12, 13, 15, 16, 23, 34, 36, 56. 17. Ðåáðà 12, 14, 23, 24, 34, 35, 36, 56. 18. Ðåáðà 13, 14, 15, 23, 25, 36, 46, 56. 19. Ðåáðà 12, 14, 15, 23, 25, 26, 35, 45. 41 8 Àëãåáðà âû÷åòîâ ïî ìîäóëþ m Ïóñòü m  íàòóðàëüíîå ÷èñëî, m ≥ 2. Íà ìíîæåñòâå Z öåëûõ ÷èñåë îïðåäåëèì äâóõìåñòíûå îïåðàöèè +, −, · (mod m) m êàê ôóíêöèè Z → {0, 1, . . . , m − 1}. Ðåçóëüòàòîì îïåðàöèè x + y, x − y, x · y (mod m) ÿâëÿåòñÿ îñòàòîê îò äåëåíèÿ îáû÷íîé ñóììû (ñîîòâåòñòâåííî ðàçíîñòè, ïðîèçâåäåíèÿ) öåëûõ ÷èñåë x, y íà m. Íàïðèìåð, 6 + 11 = 2 (mod 5), 9 − 20 = 1 (mod 6), 3 · 12 = 4 (mod 8), 23 = 2·2·2 = 1 (mod 7). ×èñëà 0, 1, . . . , m−1 íàçûâàþòñÿ m. Ìíîæåñòâî {0, 1, . . . , m − 1} ñ îïåðàöèÿìè +, · (mod m) íàçûâàåòñÿ m è îáîçíà÷àåòñÿ êàê Zm : ñëîæåíèÿ, âû÷èòàíèÿ è óìíîæåíèÿ ïî ìîäóëþ öàòåëüíûìè âû÷åòàìè ïî ìîäóëþ àëãåáðîé âû÷åòîâ ïî ìîäóëþ íàèìåíüøèìè íåîòðè- Zm = ({0, 1, . . . , m − 1}; +, · (mod m)). Îïåðàöèè +, · (mod m) äîñòàòî÷íî çàäàòü òîëüêî íà ìíîæåñòâå {0, 1, . . . , m − 1}. Ýòî ìîæíî ñäåëàòü, óêàçûâàÿ ðåçóëüòàòû îïåðàöèé â äâóõ òàáëèöàõ ðàçìåðà m × m, íàïðèìåð, x 0 1 + (÷àñòî x + y (mod 2) y 1 x 0 1 · 0 1 1 0 (mod 2) y 1 (mod 2) çàïèñûâþò êàê x ⊕ y ), x 0 1 2 x 0 1 2 + y (mod 3) 0 1 2 0 1 2 1 2 0 2 0 1 · y (mod 3) 0 1 2 x 0 1 2 3 + 0 0 0 1 y (mod 4) 1 2 3 1 2 3 1 2 3 2 3 1 0 0 0 0 1 2 0 2 1 x 0 1 2 3 3 1 2 · y (mod 4) 1 2 3 1 2 3 2 2 3 2 1  àëãåáðå âàæíåéøåé çàäà÷àåé ÿâëÿåòñÿ ðåøåíèå óðàâíåíèé. Ðàññìîòðèì ïðîñòåéøåå óðàâíåíèå ax = b (mod m) 42 (1) â àëãåáðå âû÷åòîâ. Òåîðåìà 1 (î ðåøåíèè óðàâíåíèÿ ïåðâîé ñòåïåíè â àëãåáðå âû÷å- Ïóñòü d =ÍÎÄ(a, m) (íàèáîëüøèé îáùèé äåëèòåëü), òîãäà ñïðàâåäëèâî ñëåäóþùåå. 1. Åñëè ÷èñëî b íå äåëèòñÿ íà d, òî óðàâíåíèå (1) íå èìååò ðåøåíèÿ. 2. Eñëè b êðàòíî d, òî óðàâíåíèå (1) èìååò â ìíîæåñòâå {0, 1, . . . , m − 1} ðîâíî d ðàçëè÷íûõ ðåøåíèé. Åñëè x0  ðåøåíèå, òî îñòàëüíûå d − 1 ðåøåíèé åñòü òîâ). xk = x0 + k(m/d) (mod m), Ïðèìåð 1. Óðàâíåíèå 12x = 45 ÍÎÄ(12, 32) = 4, à 45 íå÷åòíî. Ïðèìåð 2. Ðàññìîòðèì óðàâíåíèå 20x = 44 k = 1, . . . , d − 1. (mod 32) íå èìååò ðåøåíèé, òàê êàê (mod 108). (2) Èìååì ÍÎÄ(20, 108) = 4, 44 êðàòíî 4. Pàçäåëèì îáå ÷àñòè óðàâíåíèÿ (2) è ìîäóëü íà 4, ïîëó÷èì áîëåå ïðîñòîå óðàâíåíèå 5x = 11 (mod 27). (3) Äëÿ íåãî ÍÎÄ(5, 27) = 1, ïîýòîìó óðàâíåíèå (3) èìååò ðîâíî îäíî ðåøåíèå x0 ∈ {0, 1, . . . , 26}. Íåòðóäíî ïðîâåðèòü, ÷òî x0 = 13. (Ê ñîæàëåíèþ, íàéòè ðåøåíèå ìîæíî òîëüêî ïåðåáîðîì ðàçëè÷íûõ ýëåìåíòîâ êîíå÷íîãî ìíîæåñòâà âû÷åòîâ, õîòÿ âî ìíîãèõ ñëó÷àÿõ ïåðåáîð íå ïîëíûé.) Òîãäà îñòàëüíûå ðåøåíèÿ óðàâíåíèÿ (2) â ìíîæåñòâå {0, 1, . . . , 107} åñòü x1 = 13 + 27 = 40, x2 = 13 + 2 · 27 = 67, x3 = 12 + 3 · 27 = 94. Îòâåò: x = 13, 40, 67, 94. Ïîÿñíèì, êàê ìîæíî ñîêðàòèòü ïåðåáîð ïðè ðåøåíèè óðàâíåíèÿ (3). ×èñëà 11 è 11 + 27n, n ∈ Z, èìåþò îäèíàêîâûé îñòàòîê îò äåëåíèÿ íà 27, ïîýòîìó äîñòàòî÷íî íàéòè òàêîå íàèìåíüøåå íàòóðàëüíîå n, ÷òîáû ÷èñëî 11 + 27n äåëèëîñü íà 5. Äëÿ n = 1 ÷èñëî 11 + 27 = 38 íå äåëèòñÿ íà 5, äëÿ n = 2 ïîëó÷àåì ÷èñëî 11 + 27 · 2 = 65, êðàòíîå 5. Òàêèì îáðàçîì, óðàâíåíèå (3) ðàâíîñèëüíî óðàâíåíèþ 5x = 65 (mod 27), îòêóäà x = x0 = 65/5 = 13. Ê óðàâíåíèþ (1) ñâîäÿòñÿ è áîëåå ñëîæíûå âèäû óðàâíåíèé â àëãåáðå âû÷åòîâ. Ðàññìîòðèì ñèñòåìó ðèöåé. ëèíåéíûõ óðàâíåíèé 43 ïî ìîäóëþ m ñ êâàäðàòíîé ìàò- Tåîðåìà 2. Åñëè êâàäðàòíàÿ ñèñòåìà ëèíåéíûõ óðàâíåíèé   a11 x1 + · · · +a1n xn = b1 (mod m) an1 x1 + · · · +ann xn = bn (mod m)  .. .. èìååò îïðåäåëèòåëü ∆ òàêîé, ÷òî ÍÎÄ(∆, m) = 1, òî ýòà ñèñòåìà óðàâíåíèé èìååò ðîâíî îäíî ðåøåíèå (x1, . . . , xn) â ìíîæåñòâå {0, 1, . . . , m − 1}n. Ïðèìåð 3. Ðåøèì ñèñòåìó ïîðÿäêà 2  3x − 2y = 1 (mod m) 4x + 7y = 2 (mod m) äëÿ ìîäóëåé m = 4, 9, 10, 16, 20, 30, 50, 100. Îïðåäåëèòåëü ñèñòåìû 3 · 7 + 2 · 4 = 29 ÿâëÿåòñÿ ïðîñòûì ÷èñëîì, óñëîâèå òåîðåìû 2 âûïîëíÿåòñÿ, ñèñòåìà èìååò åäèíñòâåííîå ðåøåíèå äëÿ êàæäîãî ìîäóëÿ. Íàéäåì åãî. Âû÷èòàÿ èç âòîðîãî óðàâíåíèÿ ïåðâîå, ïîëó÷àåì x + 9y = 1 (mod m). (4) Óìíîæèì óðàâíåíèå (4) íà 3 è âû÷òåì èç ðåçóëüòàòà ïåðâîå óðàâíåíèå èñõîäíîé ñèñòåìû, ïîëó÷èì 29y = 2, x = 1 − 9y (mod m). Ýòè ôîðìóëû îäíîçíà÷íî îïðåäåëÿþò ðåøåíèå. Çàïèøåì ðåøåíèÿ (ïàðû (x, y)) äëÿ êàæäîãî èç ðàññìàòðèâàåìûõ ìîäóëåé â òàáëèöó: m 4 9 10 16 20 30 50 100 x 3 1 9 7 19 19 9 59 y 2 1 8 10 18 28 38 38 Êâàäðàòíîå óðàâíåíèå ax2 + bx + c = 0 (mod m) ìîæíî ðåøèòü íåñêîëüêèìè ñïîñîáàìè. Îäèí èç íèõ  ðàçëîæåíèå íà ìíîæèòåëè ax2 + bx + c = a(x − x1 )(x − x2 ) (mod m). Äðóãîé ñïîñîá ñîñòîèò â ïðèìåíåíèè òåîðåìû Âèåòà7 è ôîðìóë äëÿ êîðíåé x1 + x2 = a−1 b, x1 x2 = a−1 c (mod m). Òðåòèé ñïîñîá ñîñòîèò â ïðèìåíåíèè îáùåé ôîðìóëû äëÿ êîðíåé êâàäðàòíîãî óðàâíåíèÿ â àðèôìåòèêå ïî ìîäóëþ m: p x = (2a) (−b ± b2 − 4ac ) −1 7 Ôðàíñóà (mod m). Âèåò (15401603)  ôðàíöóçñêèé ìàòåìàòèê, "îòåö àëãåáðû" 44 Ïðèìåíÿòü åå ìîæíî òîëüêî ïðè íå÷åòíîì ìîäóëå m.  ýòîì ñëó÷àå ôîðìóëó ìîæíî óïðîñòèòü: x = a−1 (−2−1 b ± p (2−1 b)2 − ac ) (mod m). (5) Ïðèìåð 4. Ðåøèì óðàâíåíèå x2 + x + 2 = 0 (mod 11). Åãî ìîæíî çàïèñàòü â âèäå x2 − 10x + 24 = 0 (mod 11) è ðàçëîæèòü x2 + x + 2 = x2 − 10x + 24 = (x − 4)(x − 6) (mod 11), îòêóäà x1 = 4, x2 = 6. (6) Ëåãêî ïðîâåðèòü âûïîëíèìîñòü ôîðìóë Âèåòà: 4+6 = −1, Åñëè æå ïðèìåíèòü òðåòèé ñïîñîá è ôîðìóëó (5), òî x = −2−1 ± 4×6 = 2 (mod 11). p p √ (2−1 )2 − 2 = −6 ± 62 − 2 = 5 ± 1 (mod 11). √ Èìååòñÿ äâà çíà÷åíèÿ êâàäðàòíîãî êîðíÿ èç 1 ïî ìîäóëþ 11: 1 = 1 (mod 11) √ 1 = −1 = 10 (mod 11), ïîýòîìó ïîëó÷àåì òå æå ðåøåíèÿ (6). è 9 Óðàâíåíèÿ â öåëûõ ÷èñëàõ  äèñêðåòíîé ìàòåìàòèêå ïðèìåíÿþòñÿ òîëüêî öåëûå ÷èñëà, à ðàçðåøèìîñòü óðàâíåíèé â öåëûõ ÷èñëàõ îïðåäåëÿåòñÿ ñâîéñòâàìè äåëèìîñòè. Íàïðèìåð, î÷åíü ïðîñòîå óðàâíåíèå 2x = 1 íå èìååò öåëî÷èñëåííûõ ðåøåíèé.  àëãåáðå âû÷åòîâ ðàññìàòðèâàþòñÿ îñòàòêè îò äåëåíèÿ öåëûõ ÷èñåë íà ìîäóëü, ïîýòîìó âû÷åòû ïðèìåíÿþòñÿ ïðè àíàëèçå è ðåøåíèè öåëî÷èñëåííûõ óðàâíåíèé. Ðàññìîòðèì îäíî èç òàêèõ óðàâíåíèé  ëèíåéíîå óðàâíåíèå îòíîñèòåëüíî n íåèçâåñòíûõ a1 x1 + · · · + an xn = c. Çäåñü êîýôôèöèåíòû a1 , . . . , an , c è íåèçâåñòíûå x1 , . . . , xn  öåëûå ÷èñëà. Íåîáõîäèìûì óñëîâèåì ðàçðåøèìîñòè òàêîãî óðàâíåíèÿ ÿâëÿåòñÿ äåëèìîñòü êîýôôèöèåíòà c íà ÍÎÄ(a1 , . . . , an ). Èíòåðåñíî, ÷òî ýòî æå óñëîâèå ÿâëÿåòñÿ è äîñòàòî÷íûì äëÿ ðàçðåøèìîñòè óðàâíåíèÿ. Åñëè n = 1, òî ðåøåíèå, êîãäà îíî ñóùåñòâóåò, åäèíñòâåííî: x1 = c/a1 . Ïðè n ≥ 2 óðàâíåíèå â ñëó÷àå ðàçðåøèìîñòè èìååò áåñêîíå÷íîå ìíîæåñòâî ðåøåíèé. Ðàññìîòðèì óðàâíåíèå ñ äâóìÿ íåèçâåñòíûìè. Äëÿ óïðîùåíèÿ îáîçíà÷åíèé çàïèøåì åãî â âèäå ax + by = c, a > 0, 45 b 6= 0. (1) Ïóñòü d =ÍÎÄ(a, |b|). Tîãäà: åñëè c íå êðàòíî d, òî óðàâíåíèå (1) íåðàçðåøèìî, åñëè c êðàòíî d, òî óðàâíåíèå (1) èìååò áåñêîíå÷íîå ìíîæåñòâî ðåøåíèé, çàâèñÿùèõ îò öåëî÷èñëåííîãî ïàðàìåòðà k: Òåîðåìà. x = x0 + bk, ãäå x0 ax0 = c  ëþáîå öåëîå ïðè b = ±1. y= c − ax0 − ak, b k ∈ Z, (2) ïðè |b| > 1, (mod |b|) Ïðèìåð. Ðàññìîòðèì óðàâíåíèå 3x − 7y = −24. Èìååì a = 3, b = −7, d =ÍÎÄ(3, 7) = 1, óðàâíåíèå ðàçðåøèìî. Èç óðàâíåíèÿ â àëãåáðå âû÷åòîâ 3x0 = −24 (mod 7) íàõîäèì x0 = 6. Òîãäà, ñîãëàñíî (2), x = 6 − 7k, y= −24 − 3 · 6 − 3k = 6 − 3k, −7 k ∈ Z. Ïîëåçíî áûâàåò ñäåëàòü ïðîâåðêó. Ïîäñòàâëÿÿ ïîëó÷åííûå âûðàæåíèÿ x = x(k), y = y(k) â ëåâóþ ÷àñòü èñõîäíîãî óðàâíåíèÿ, âèäèì, ÷òî ñëàãàåìûå, ñîäåðæàùèå k , óíè÷òîæàþòñÿ è ïîëó÷àåòñÿ ÷èñëî −24. Ôîðìóëû (2) îïðåäåëÿþò . Èç íåãî çàìåíîé ïåðåìåííîé k íà êîíêðåòíûå öåëûå ÷èñëà ïîëó÷àåòñÿ áåñêîíåñêîå ìíîæåñòâî . ðàññìîòðåííîì ïðèìåðå ïðè k = 0 ïîëó÷àåì ÷àñòíîå ðåøåíèå (x, y) = (6, 6), ïðè k = 1  ÷àñòíîå ðåøåíèå (x, y) = (−1, 3) è òàê äàëåå. îáùåå ðåøåíèå ÷àñòíûõ ðåøåíèé Çàäà÷à (ïîñëåäíÿÿ) äëÿ ñàìîñòîÿòåëüíîãî ðåøåíèÿ. Ðåøèòå ñëåäóþùåå óðàâíåíèå â öåëûõ ÷èñëàõ. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 2x − 11y = 5. 4x + 7y = −20. 9x − 5y = 10. 15x − 4y = −2. 12x + 5y = 6. 3x + 16y = 5. 14x − 9y = −3. 5x + 16y = 8. 7x + 11y = 9. 11x − 3y = −20. 11. 12 13. 14. 15. 16. 17. 18. 19. 20. 7x + 12y = −6. 8x − 17y = 4. 16x − 7y = −5. 12x + 5y = 10. 9x − 7y = −30. 11x + 8y = 6. 5x − 14y = 3. 4x + 17y = −6. 9x − 11y = 8. 9x + 13y = −7. Ðåøåíèÿ âñåõ çàäà÷ ïðèñûëàéòå ïî àäðåñó MeshchaninovDG@mpei.ru 46 10 ×èñëà Ñòèðëèíãà 2-ãî ðîäà è ÷èñëà Áåëëà Êîëè÷åñòâî ðàçáèåíèé n-ìíîæåñòâà íà k íåïóñòûõ ïîäìíîæåñòâ îáîçíà÷àåòñÿ êàê Sn,k . Çíà÷åíèÿ Sn,k , n, k ≥ 0, íàçûâàþòñÿ . Íàïðèìåð, S3,2 = 3, òàê êàê èìååòñÿ ðîâíî 3 ðàçáèåíèÿ ìíîæåñòâà {1, 2, 3} íà 2 ïîäìíîæåñòâà, îäíî èç êîòîðûõ ñîäåðæèò ðîâíî îäèí ýëåìåíò, à âòîðîå  äâà: 1|23, 2|13, 3|12. Óêàæåì ïðîñòåéøèå ñâîéñòâà ýòèõ ÷èñåë. n≥1 Sn,1 = Sn,n = 1, Sn,0 = 0. Äëÿ ÷èñëà S0,0 , íå èìåþùåãî ñîäåðæàòåëüíîãî ñìûñëà, ïðèìåì ôîðìàëüíîå ñîãëàøåíèå S0,0 = 1. Òåîðåìà 1. Sn,k : ÷èñëàìè Ñòèðëèíãà 2-ãî ðîäà Åñëè , òî Äëÿ ÷èñåë ñïðàâåäëèâà ñëåäóþùàÿ ðåêóððåíòíàÿ ôîðìóëà Sn,k = Sn−1,k−1 + kSn−1,k . Äîêàçàòåëüñòâî. Ðàññìîòðèì óíèâåðñàëüíîå ìíîæåñòâî U = {e1 , . . . , en−1 , en }. Âñå åãî ðàçáèåíèÿ íà k íåïóñòûõ ïîäìíîæåñòâ ðàçäåëèì íà äâå ãðóïïû: ñîäåðæàùèå îäíîýëåìåíòíîå ïîäìíîæåñòâî {en }, êîëè÷åñòâî òàêèõ ðàçáèåíèé ðàâíî ÷èñëó Sn−1,k−1 ðàçáèåíèé (n − 1) ïîäìíîæåñòâà {e1 , . . . , en−1 } íà k − 1 íåïóñòûõ ïîäìíîæåñòâ; íå ñîäåðæàùèå ïîäìíîæåñòâà {en }, ïðè ýòîì ýëåìåíò en ìîæåò îêàçàòüñÿ â ëþáîì èç k íåïóñòûõ ïîäìíîæåñòâ (n − 1)-ìíîæåñòâà {e1 , . . . en−1 }, êîëè÷åñòâî òàêèõ ðàçáèåíèé ðàâíî kSn−1,k . Îñòàåòñÿ ïðèìåíèòü ïðàâèëî ñóììû.  Íàïðèìåð, S4,3 = S3,2 + 3S3,3 = 3 + 3 · 1 = 6, S5,4 = S4,3 + 4S4,4 = 6 + 4 · 1 = 10. Ýòè ñâîéñòâà ïîçâîëÿþò çàïîëíèòü êîíå÷íîå ìíîæåñòâî ïåðâûõ ñòðîê áåñêîíå÷íîé òàáëèöû äëÿ ÷èñåë Sn,k , àíàëîãè÷íîé òðåóãîëüíèêó Ïàñêàëÿ äëÿ áèíîìèàëüíûõ êîýôôèöèåíòîâ: n 0 1 k 1 2 3 4 5 1 2 3 4 5 1 1 1 1 3 1 1 7 6 1 1 15 25 10 1 ×èñëà Ñòèðëèíãà 2-ãî ðîäà ïðèìåíÿþòñÿ, â ÷àñòíîñòè ïðè ðåøåíèè ñëåäóþùåé çàäà÷è. 47 Ïðèìåð. Èìååòñÿ n ðàçëè÷íûõ (ïî âíåøíåìó âèäó ïèðîæêîâ) è k òàðåëîê. Êàæäàÿ òàðåëêà äîñòàòî÷íî áîëüøàÿ è ìîæåò âìåñòèòü âñå n ïèðîæêîâ. Ñêîëüêèìè ñïîñîáàìè ïèðîæêè ìîæíî ðàçëîæèòü íà òàðåëêè òàê, ÷òîáû ïóñòûõ òàðåëîê íå áûëî? Îòâåò: k!Sn,k . Bn íàçûâàåòñÿ êîëè÷åñòâî âñåõ ðàçáèåíèé n-ìíîæåñòâà íà íåïóñòûå ïîäìíîæåñòâà/ Ñëåäñòâèå. ×èñëîì Áåëëà Ñïðàâåäëèâû ðàâåíñòâà B0 = B1 = 1, Bn = n X Sn,k . k=0 Òåîðåìà 2. Äëÿ ÷èñåë Áåëëà ñïðàâåäëèâà ñëåäóþùàÿ ðåêóððåíòíàÿ ôîðìóëà: Bn+1 = n X Cnk Bk . k=0 Äîêàçàòåëüñòâî. Ðàññìîòðèì óíèâåðñàëüíîå (n+1)-ìíîæåñòâî U = {e1 , . . . , en , ïîäìíîæåñòâ en+1 }. Ôèêñèðóåì öåëîå k , 0 ≤ k ≤ n. Äëÿ êàæäîãî èç A ⊆ {e1 , . . . , en }, ñîñòîÿùèõ èç k ýëåìåíòîâ, èìååòñÿ ðîâíî Bk ðàçáèåíèé ìíîæåñòâà A íà íåïóñòûå ïîäìíîæåñòâà (íàçîâåì èõ ). Åñëè ýëåìåíò en+1 çàíåñòè â ëþáîé èç ýòèõ áëîêîâ, òî ïîëó÷èì ðàçáèåíèå ìíîæåñòâà U .  Óêàæåì ïåðâûå ÷ëåíû ïîñëåäîâàòåëüíîñòè ÷èñåë Áåëëà: Cnk áëîêàìè n 0 1 2 3 4 5 6 ... Bn 1 1 2 5 15 52 203 . . .  ÷àñòíîñòè, âñå B3 = 5 ðàçáèåíèé ìíîæåñòâà {1, 2, 3} åñòü 1|2|3, 1|23, 2|13, 48 3|12, 123.