dm3 (1272352), страница 3
Текст из файла (страница 3)
Ôóíêöèÿ 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−1kCnk = Cn−1+ Cn−1.kCn×èñëà îáðàçóþò áåñêîíå÷íóþ ìàòðèöó, íàçûâàåìóþ òðåóãîëüíèêîì Ïàñêàëÿ. Åå ñòðîêè ñîîòâåòñòâóþò çíà÷åíèÿì n = 0, 1, 2 .
. ., ñòîëáöû çíà÷åíèÿì k = 0, 1, . . . , n. Âîò ïåðâûå ñòðîêè òðåóãîëüíèêà Ïàñêàëÿ:111111112 13 3 14 6 4 15 10 10 5 16 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=KXCNM1 CNK−M.2M =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 \BU è B ), ñîñòîÿùåå â òî÷íîñòè èç âñåõ ýëåìåíòîâ âkU , íå âõîäÿùèõ â B . ×èñëî Cn ìíîæåñòâ B ðàâíî ÷èñëó Cnn−k ìíîæåñòâ B .5.
Ïîëîæèì U1 = {e1 , . . . , en−1 }. Âñå Cnk ïîäìíîæåñòâ B ìîùíîñòè k â U ìîæíîðàçáèòü íà äâå íåïåðåñåêàþùèåñÿ ãðóïïû:k−11) ñîäåðæàùèå ýëåìåíò en , èõ êîëè÷åñòâî åñòü Cn−1, òàê êàê ýëåìåíòàìè ïîäìíîæåñòâà U1 çàïîëíÿþòñÿ ëèøü k − 1 ìåñò â ìíîæåñòâå B (îäíî ìåñòî â B çàíÿòîýëåìåíòîì en );k2) íå ñîäåðæàùèå en , èõ êîëè÷åñòâî åñòü Cn−1, òàê êàê ýëåìåíòàìè ïîäìíîæåñòâàU1 çàïîëíÿþòñÿ âñå k ìåñò â ìíîæåñòâå B .k−1k.+ Cn−1Ïî ïðàâèëó ñóììû ïîëó÷àåì Cnk = Cn−16. Êàæäûé 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âûáðàòü, ïî ïðàâèëó ïðîèçâåäåíèÿ, CNCN2 ñïîñîáàìè. Ïðè ýòîì M = 0, .
. . , K .1Îñòàåòñÿ ïðèìåíèòü ïðàâèëî ñóììû. ðàçíîñòüþäîïîëíåíèåììíîæåñòâ163.4Ôîðìóëû áèíîìà è ïîëèíîìà. Áèíîìèàëüíûå è ïîëèíîìèàëüíûåêîýôôèöèåíòûÒåîðåìà 5.Ôîðìóëà áèíîìà Íüþòîíà:n(a + b) =nXCnk 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 .Ñïðàâåäëèâû ñëåäóþùèå ñâîéñòâà ñóìì áèíîìèàëüíûõ êîýôôènXCnk = 2n ,(3)(−1)k Cnk = 0,(4)k=0nXk=0Cn0 + 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 (ïîëèíîìèàëüíàÿ ôîðìóëà).Xn(x1 + · · · + xm ) =k1 +···+km =nk!xk11 · · · xkmm .k1 ! · · · km !Ñóììèðîâàíèå âåäåòñÿ ïî âñåì íåîòðèöàòåëüíûì öåëûì ÷èñëàì k1, . . . , km òàêèì, ÷òî k1 + · · · + km = n.×èñëàíàçûâàþòñÿk!k1 ! · · · km !ïîëèíîìèàëüíûìè êîýôôèöèåíòàìè. Èõ ñóììà ðàâíà mn:Xk1 +···+km =nk!= mn .k1 ! · · · km !Ôîðìóëà áèíîìà ÷àñòíûé ñëó÷àé ïîëèíîìèàëüíîé ôîðìóëû ïðè m = 2.Ïðèìåð 2. Çàïèøåì ïîëèíîìèàëüíóþ ôîðìóëó äëÿ (x1 +x2 +x3 )4 .
Âû÷èñëèì18ïîëèíîìèàëüíâå êîýôôèöèåíòû:k1 k2 k3 4!/(k1 !k2 !k3 !)0 0 410 1 3460 2 20 3 140 4 011 0 34121 1 21 2 1121 3 0462 0 22 1 11262 2 03 0 1443 1 04 0 01Òåïåðü ìîæíî âûïèñàòü âñþ ôîðìóëó, èçìåíèâ äëÿ êðàñîòû ïîðÿäîê ñëàãàåìûõ:(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. Âûïèøåì âñå òàêèå âåêòîðû (äëÿ êðàòêîñòèñêîáêè îïóñêàåì):Ïðèìåð30003, 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 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
