Binomial koefficenler
Download 33.43 Kb.
|
BINOMIAL KOEFFICENLER
|
BINOMIAL KOEFFICENLER Kiriwiw
Tuwrıdan-tuwrı ónim qaǵıydasi Tákirarlanmasdan jaylastırıw Permutatsiyalar Kombinatsiyalar Nyuton bınamial Ádebiyatlar KIRISIW
Kombinatorika tek XvII asirde - itimallıq teoriyası payda bolǵan dáwirde ilmga aylandı. Teoriyalıq hám itimallıq máselelerin sheshiw ushın arnawlı bir shárt menen esaplanǵan túrli kombinatsiyalar sanın esaplaw zárúr edi. Italiya ilimpazları G. Kardano, N. Tartagliya hám G. Galiley tárepinen XvI asirde orınlanǵan birinshi dóretpelerden keyin bunday máseleler fransuz matematigi B. Paskal tárepinen úyrenildi. 1665 jılda " Arifmetika" temasındaǵı shártnama Paskal úshmuyeshten ibarat sanlardıń ataqlılıǵı ájep emes: olar algebraning eń tábiyiy máselelerinde, kombinatorikada, itimallar teoriyasında, matematikalıq analizda, nomer teoriyasında payda boladı. Turmısımızdıńda kombinatorial analiz dep atalıwshı matematika shaqapshasınan keń paydalanamız. Matematikanıń bul bólegi sanlı jıynaqlardı úyrenedi. n elementten ibarat jıynaqlar n-elemental dep ataladı. Biraq n - element kompleksinen k elementlerdi tańlawımız múmkin. n- element kompleksiniń hár bir k-element bólegi k boyınsha n elementlerdiń birikpesi dep ataladı. Kombinatorial analizning wazıypalarınan biri n elementlerdiń k boyınsha birikpeleri sanın tabıw bolıp tabıladı. Ádetde bul nomer menen belgilenedi. Bul notatsiya bınamial koefficiyentler dep ataladı hám C = formulası bınamial teorema yamasa Nyutondıń bınamial dep ataladı. Nyutondıń ılayıqlıǵı sonda, ol bul formulanı integer bolmaǵan kórsetkish n ushın birlestiriwtirdi. Bul kurs jumısında esaplaw máseleleri ushın eń zárúrli bolǵan kombinatorial formulalar hám bınamial koefficiyentler haqqında ulıwma maǵlıwmat beriledi. Jumıstıń maqseti: bınamial koefficiyentler menen baylanıslı ámeliy mashqalalardıń úlken bólegin sheshiw múmkin bolǵan salıstırǵanda az sanlı ápiwayı hukmdorlarni kórip shıǵıw. Bul jumıs matematika fakulteti studentleri ushın kombinat sxemaları hám bınamial koefficiyentlerdi úyreniwde paydalı boladı. 1. 1 Tákirarlanmasdan tártip Shama menen oylayıq, eki A hám B jıynaqları bar. Birinshi element A jıynaqtan, ekinshi element bolsa B kompleksinen alınǵan bolsa, barlıq jup elementlerdi kórip shıǵayıq. Sonday etip, alınǵan jıynaq A hám B jıynaqlarınıń tuwrıdan-tuwrı ónimi AB dep ataladı. Keling, biz waqtı -waqtı menen paydalanatuǵın jıynaqlar daǵı birpara operatsiyalardı eslaylik. AB ={ ()|, }-meniń jumıs jıynaqların aylandırıw. AB ={| } jıynaqlar birlespesi bolıp tabıladı. Jıynaqlardıń AB-kesindisi. A\B = - jıynaqlar daǵı parq. Ø - bos jıynaq. Ol universal jıynaq bolıp tabıladı. =Ol A={x| xA } - setning tolıqlawıshsı. 1. 1. 1. Swm qaǵıydası A hám B dıń ab=Ø, hám. sıyaqlı sheksiz jıynaqları bolsın. Keyininen. Túsindiriw. Eger qandayda bir elementti m jollar menen tańlaw múmkin bolsa hám qandayda bir elementti n usılda tańlaw múmkin bolsa, ol halda elementti t + n jollar menen tańlaw múmkin. Juplıq bolsın kesilispeytuǵın jıynaqlar, Ø, bul jerde i ≠ j. Keyin, anıqrog'i, teńlik ámelge asadı. 1. 1. 2. Tuwrıdan-tuwrı ónimdiń qaǵıydası A hám B sheksiz jıynaqlar bolsın hám, keyin. Túsindiriw. Eger qandayda bir elementti m metodları boyınsha tańlaw múmkin bolsa hám eger hár bir sonday tańlawdan keyin elementti n usılda tańlaw múmkin bolsa, ol halda belgilengen tártipte jup (a, b) tańlaw jollar menen ámelge asırılıwı múmkin. Bunda A jıynaq elementlerin tańlaw B kompleksi elementlerin tańlaw usılına baylanıslı emes, dep aytıladı. Endi arbitraj jıynaqlar bolsın,. Keyin 3. 1-qosımsha. 1. 1. 3. Tákirarlanmasdan jaylastırıw n qıylı ob'ektler bar. Olardıń neshesin uzınlıqtaǵı tártiplerden shólkemlestiriw múmkin? Eger olar quramına kiritilgen elementler túri yamasa tártip degi tártibi menen parq qilsa, eki tártip parıq etedi. Bunday tártipler tákirarlanmasdan jaylastırıwlar dep ataladı hám olardıń sanı A. ni ańlatadı. Bul tártiplerdi dúziwde birinshi orında ámeldegi n zatlardan qandayda-birın qoyıw múmkin. Endi n - 1 qalǵan zatlardan tek qandayda-birın ekinshi orınǵa qoyıw múmkin. hám, aqır-aqıbetde, k-orında - p-k + 1 qalǵan zatlardıń qandayda-birı. Tuwrıdan-tuwrı ónim qaǵıydasına kóre, biz n den repetitsiyasiz jaylastırıwlardıń ulıwma sanın alamız k; teńler Sonı eslep kóriń 0! =1 3. 2-qosımsha. 1. 1. 4. Permutatsiyalar n den k ge shekem tákirarlarsız jaylastırıwlardı quram tapqanda ; elementlerdiń quramı yamasa tártibi tárepinen bir-birinen parq etiwshi tártiplerdi aldı. Lekin barlıq n elementlerdi óz ishine alǵan tártiplerdi alsańız, olar bir-birinen tek olarǵa kiritilgen elementler tártibinde parıq etiwi múmkin. Bunday tártipler n elementlerdiń permutasiyalari dep ataladı hám olardıń sanı P. menen belgilenedi. Sol sebepli permutatsiyalar sanı! ga teń. Permutatsiyalar π= (π. π,.. ., π) elementleri 1, 2,.. ., n da matritsa formasında jazıladı, ol jaǵdayda joqarı sızıq permutatsiyadagi elementlerdiń pozitsiyalarining 1, 2,.. ., n qatar nomerleri boyınsha boladı ; tómengi sızıq - hár qanday tártipte alınǵan 1, 2,.. ., n sanlardıń birdey kompleksi; P - elementtiń j ga bolǵan sanı -m permutatsiya ornı. Matritsa formasında jazılǵan permutatsiyalardagi ústinler tártibi áhmiyetli emes, sebebi bunda permutatsiyadagi hár bir elementtiń pozitsiya nomeri joqarı qatarda anıq kórsetiledi. Mısalı, tórt elementten ibarat permutatsiya (3, 2, 4, 1) da jazılıwı múmkin. 3. 3-qosımsha 1. 1. 5. Kombinatsiyalar Tártip degi elementlerdiń tártibi sizdi qızıqtirmaydigan, biraq tek onıń quramı menen qızıǵatuǵın jaǵdaylarda, olar kombinatsiyalar haqqında sóylesedi. k boyınsha n qıylı elementlerdiń birikpeleri; bul elementlerden payda bolǵan hám bir-birinen kompozitsiya tárepinen parq etiwshi uzınlıqtaǵı barlıq múmkin bolǵan tártiplermi, lekin elementler tártibinde emes. Birikpelerdiń ulıwma sanı C yamasa. Keling, bul sannı anıqlaylik. n den k ge shekem bolǵan barlıq birikpelerdi yasaylik. Keyin hár bir bir kombinatsiya daǵı elementlerdi hár tárepleme qayta tártipke keltiraylik. Endi bizde yaǵnıy kompozitsiya yamasa tártipte parıq etetuǵın tártipler ámeldegi, sol sebepli bulardıń hámmesi n den k ge shekem tákirarlanmasdan jaylastırıwlar bolıp tabıladı. Olardıń sanı A. Sonı esapqa alsaq, hár bir kombinatsiya k beredi! jaylastırıwlar, keyin jumıs qaǵıydasına kóre jazılıwı múmkin yamasa. Keyin 3. 4-qosımsha. 1. 2 Polinom formulası Formula dep ataladı teńlemediń barlıq sheshimleri boyınsha jıyındısı integer teris bolmaǵan sanlarda ámelge asırilatuǵın polinom, tastıyıq ushın biz kóp aǵzalılardı atqaramız Alınǵan ańlatpada soǵan uqsawlıqtı beriw ushın hár bir bólektiń túrine bir aǵzalar sanın esaplaw kerek. Birdey jalǵız a'zoni alıw ushın ańlatpanı keńeytiwde qawıslarda kópaytuvchi retinde tańlaw kerek. Bul tómendegi jollar menen ámelge asırılıwı múmkin. qalǵan ashılmaǵan qawıslardan, parentetik kóbeyiwshi retinde saylań. Bul jollar menen ámelge asırılıwı múmkin hám taǵı basqa. e. Keyininen ańlatpa nozil bolǵanda jalǵız shártler sanı tártiplengen bóliniwi sanına teń boladı. 1. 2. 1. Nyuton bınamial Polinom formulasınıń saatlıq kórinisi (x+y) = C x y + C x y +... .. + C x y +... .. + C x y (1. 1) qayda C= yamasa ( 1. 2) qay jerde. Bul formula kóbinese bınamial teoremasi dep ataladı, C sanlar bolsa bınamialkoeffitsientlar bolıp tabıladı. Teńlik (1. 1) hám (1. 2) kóbinese Nyutondıń bınamial dep ataladı. Nyutondıń ılayıqlıǵı sonda, ol bul formulanı integer bolmaǵan n ushın birlestiriwtirdi. Nyutondıń formulasın tastıyıqlaw bir neshe jollar menen ámelge asırılıwı múmkin. Eń dástúriy usıl matematikalıq induksiya usılı járdeminde tastıyıq bolıp tabıladı. Usıldı tómendegishe tariyplew múmkin: Induktsiya bazasy. 1 ushın protokoldıń haqıyqatın tekseriw. Induksiya qádemi. n den kem yamasa teń bolǵan barlıq natural sanlar ushın gáp rostligini qoyıng. Induksion ótiw. Shamaǵa tıykarlanıp, n+1 ushın da gáp rostligini kórsetiń. Bınamial teoremada jıyındınıń nchi kúshi (x+y) tariyplanadi: (1. 2) gde: Tastıyıqlaw ushın bul sanlardıń eki zárúrli ózgesheligi kerek. (bınamial koefficiyentler dep ataladı ): (1. 3. 1) (1. 3. 2) Keling, tastıyıqtı usınıs etilgen sxemaǵa kóre ózińiz menen birge isleylik. Birinshiden, 1 ushın (2) dıń haqıyqatın kórseteylik: Endi shama menen oylayıq, (2) ras, barlıq m ≤ n ushın : (1. 5) m shep hám oń táreplerin (5) (x+y) menen kópaytirib, braklarni kesing: Birinshi elementti birinshi jıyındınan, aqırǵısın bolsa ekinshiden alamız Bınamial koefficiyentlerdiń buyım-múlkinen paydalanǵan halda birinshi hám ekinshi summalardı qosıw múmkinshiligi bar ekenin kóriw qıyın emes (1. 3. 1) Biz gapning n ergashgan natural san ushın aqsha ekenligin kórsetdik, sol sebepli ol barlıq natural sanlar ushın tuwrı. Teorem tastıyıqlanǵan. Ekinshi usıl bolsa funksiyalar payda etiw usılına tiykarlanadı. Arnawlı jaǵday ushın formulanı (1. 1) tastıyıqlaylik: x = 1, y = m, yaǵnıy formulanı tastıyıqlaylik: (1+x) =1+ n m + n (n-1) m2/2! + n (n-1) (n-2) m3/3! +.... + m (1. 6 ) Keling, ıdıraw daǵı (1 + m) koefficiyentlerdi B, B, B,... B, yaǵnıy (1+m) = B + Bm + Bm +... + Bm (1. 7) Rekordda almastırıw (1. 7) x=0, B=1 ma`nisin tabıń. Keyin teńlemediń eki bóleginiń tuwındın alın ( 1. 7), keyin alamız : n (1+m) = B + 2 B m +... + nB m (1. 8) Bul mannan x=0 de B=n tabamız. Endi teńlemediń eki bóleginiń ekinshi tuwındın alaylıq (1. 7), alamız : n (n-1) (1+m) = 2 B +.... + n (n-1) Bm (1. 9 ) x =0 de biz B = n (n-1) / 2 hám basqalar alamız. k-th qádemde teńlik ushın k-th derivativini esaplawda (7) B = (n (n-1) (n-2) alamız ).... (n-k)) / k!, t. b. 2-bap. Bınamiykoeffitsientlar 2. 1 Bınamial koefficiyentler túsinigi Sınap - bınamial teoremdan óz atınıń qarızdar bolǵan bınamial koefficiyent. 1. 2-bandda bınamial koefficiyentlerdiń talqinini qashannan berli kórip shıqtıq hám k orınlar boyınsha n elementlerdiń birikpeleri sanın esaplaw formulasın payda etdik = C = Keling, n ni joqarı indeks hám k ni tómengi indeks dep ataylik. Olardıń kombinatorial talqiniga muwapıq, bul indeksler teris bolmaǵan integerlar menen shegaralanǵan, sebebi setlar elementlerdiń teris yamasa fraktsiyali sanına iye bola almaydı. Biraq bınamial koefficiyentler tekǵana olardıń kombinatorial talqini ushın paydalı bolıp tabıladı hám sol sebepli biz birpara sheklewlerden qutılamız. Ekenin aytıw kerek, joqarı indeksti arbitrial haqıyqıy dep esaplaw eń paydalı esaplanadı. (yamasa hátte quramalı ) san, tómengi bolsa óz basımshalıq menen integer esaplanadı. Soǵan kóre, biziń rásmiy tariypimiz tómendegi formanı aladı : (2. 1) Bul klassifikaciya bir qatar dıqqatqa iye ayrıqshalıqlarǵa iye. Birinshiden, joqarı indeks n- hárıbi menen emes, r menen de aytnadı. Bınamial koefficiyentler bul orında hár qanday haqıyqıy san bolǵanda da mánisti saqlap qalıwın aytıp otedi. Sonday eken, (-1) (-2) (-3) / (3∙2∙1) = -1. Kombinator mánisi bolmasa -de, másele r = - 1 eń zárúrli arnawlı jaǵdaylardan biri bolıp shıǵadı. r = -1/2 sıyaqlı birpara integer bolmaǵan indeksler da paydalı ekenligin tastıyıqlaydı. Ekinshiden, onı r ga salıstırǵanda kth dárejesiniń polinomi dep esaplaw múmkin. Kóremizki, bul kózqaras kóbinese nátiyje beredi. Úshinshiden, bınamial koefficiyentlerdi integer bolmaǵan tómen indeksler uǵımsız qaldıramiz. Bul jaǵdayda maqul túsetuǵın anıqlama beriw múmkin, biraq ámelde bunday koefficiyentler kemnen-kem jaǵdaylarda kerek boladı, sol sebepli bunday birlestiriwtirishni keyin basıp jıljıtıp, bul baptın keyinine ol menen shuǵıllanamız. Aqırǵı bir zat. Tariypimizning ońında " integer k ≥ 0" hám " integer k < 0" sheklewleri bar. Bunday sheklewler kórip shıǵılıp atırǵan barlıq munasábetlerde sonday sheklewler berilediki, olardıń qollanıwı kólemi anıq boladı. Tiykarınan sheklewler kem bolsa, sonsha jaqsı: eń jaqsısı sheklewlersiz koefficient bolıp tabıladı. Biraq olar ámeldegi bolsa, koefficienttiń zárúrli bólegin quraydı. Bınamial koefficiyentlerdi manipulyatcıya qılıwda qıyın bolǵanlardı bir múddet unıtıw ańsatlaw boladı. sheklewlerdi eslep qalıw, keyininen olar buzılǵanlıǵın tekseriw. Biraq siz tekseriwdi unutolmaysiz. Sonday etip, derlik hár sapar koefficiyentke dus kelgenimizde, ol mudamı 1 ge teń boladı. Lekin (1) tariypini jaqınnan tekseriw sonı kórsetedi, ol 1 ge tek n ≥ 0 ge teń (eger n integer bolsa ); eger n < 0 bolsa, ol halda = 0. 2. 2 Tiykarǵı identifikatorlar Bınamialkoeffitsientlarni ápiwayılastırıw ushın paydalanatuǵın ózliklerge ótiwden aldın olardıń bir neshe baslanǵısh bahalarına itibar beraylik. Keste degi sanlar Paskal úshmuyeshtiń baslanıwın quraydı, blaise Pascal 1623-1662) atı menen ataladı ). 1-JADvAL. Paskal úshmuyesh n
0 1
olar haqqında fundamental shártnama jazǵan. Bul keste degi bos jaylar tiykarınannumeratordagi nol sebepli 0 mánisin ańlatadı (2. 1); mısalı = (1∙2) / (2∙1) = 0. Bul boslıqlar tek kesteniń qalǵan bólegin ózgeshe qılıw ushın bos qaldıriladi. Dáslepki ush ústin ushın formulalardı eslep qalıw zálel etpeydi: =1, = r, = (2. 2) olar hár qanday haqıyqıy san ushın tuwrı (1/2 n (n+1) úshmúyeshlik sanlar formulası ekenligin unutpań ; bul nomerler tezlik penen keste baǵanasında ayqın kórinetuǵın boladı. Paskal úshmuyeshtiń dáslepki bes qatarı haqqında eslep qalıw da jaqsı pikir: eger hár qanday mashqalada 1, 4, 6, 4, 1 nomerleri kompleksi ámeldegi bolsa, ol halda bınamial koefficiyentler bolıwı múmkinligin shama etiwimiz múmkin. Paskal úshmuyesh degi nomerler derlik sheksiz sanlı ózliklerdi qaniqtiradi, sol sebepli jaqınlaw tekseriwden sońǵına bir neshe tańlanıwlanarli úlgilerdi tapsak ájep emes. Bul jerde, mısalı, kesteniń tómengi oń bólegindegi 84 nomerin qorshap turǵan altı san 56, 28, 36, 120, 210, 126 nomerleri mısalında keltirilgen " oltiburchakli mulk" bolıp tabıladı. Bul oltiburchakdan bir arqalı sanlardı kóbeytiwdiń eki variantı birdey nátiyje beredi: 56∙36∙210 = 28∙120∙126 = 423360. Paskal úshmuyeshtiń basqa qandayda bir bóleginen de soǵan uqsas oltiburchakni ajratsak, tap usınday boladi. Joqarı indeks r n dıń tómengi indeks k den úlken yamasa teń bolǵan birpara integer bolǵan normal jaǵdayda klassifikaciyaǵa (1) basqa forma beriliwi múmkin - faktoriallar kórinisinde:, integers n ≥ k ≥ 0. (2. 3) Bul formulanı alıw ushın ápiwayıginason hám denominatorni (n-k) boyınsha (n-k) kópaytiring!. Geyde bınamial koefficiyentti soǵan uqsas faktorial formada ańlatıw paydalı boladı (mısalı, " geksagonning ózgesheligini" tastıyıqlaganda). Lekin kóbinese keri jóneliste háreket qılıw, faktoriallarni bınamial koefficiyentler menen almastırıwǵa tuwrı keledi. Simmetriya baylanısı. Faktorial wákillik Paskal úshmuyeshtiń simmetriyasın kórsetedi: hár bir qatar shep tárepten ońǵa da, oń tárepten shepke de teń oqıladı. Bul qasiyetti sáwlelendiriwshi shaxs, simmetriya qatnası k ni n-k ga almastırıw arqalı alınadı :, integer n ≥0, Integer k (2. 4) Bul formula kombinatorial mániske iye, sebebi n den saylanǵan ob'ektler k ni anıqlaw arqalı biz sol arqalı tańlanbaǵan ob'ektlerdiń n-k ni anıqlaymız. Ne ushın identifikatordagi n hám k ni (2. 4) integerlar menen shegaralanǵanlıǵı anıq. Sebebi hár bir jazılıw integer bolıwı kerek. Lekin nege n teris bola almaydı? Mısalı, shama menen oylaıń n = - 1. Teńlik rostmi? Ásirese, shep bólekte k = 0 menen siz 1 alasız, oń tárepte bolsa - 0. Tiykarınan, hár qanday pútkil k ≥ 0 menen shep bólim teń = = yaǵnıy 1 yamasa -1 bolsa -de, jazılıw teris bolǵanı ushın ońı 0 ge teń. Teris k o 'nli menen bolsa shep bólegi 0 bolsa -de, oń bólegi = yaǵnıy 1 yamasa -1. Sonday eken, teńlik mudamı nadurıs! Simmetriya baylanısı basqa teris integerlar menen atqarılmaydı n. Lekin, ókiniw menen aytamız, bul sheklew ańsatlıq penen unutiladi, sebebi joqarı indeks degi ańlatpa geyde tek onıń ózgeriwshileriniń ayırım málim (lekin ámeldegi) bahaları menen teris boladı. Lekin simmetriya qatnasınıń bul nasharlıǵı onıń zárúrli abzallıǵı menen kompensatsiyalanadı : k < 0 yamasa k > n (sebebi bunday jaǵdaylarda eki bólim nolge teń bolǵanda da ) k dıń barlıq bahalarında atqarıladı. 0 ≤k ≤ n bolǵan jaǵdayda simmetriya tezlik penen ergashadi (2. 3): Bınamial koefficiyentti belgi astından kirgiziw hám kirgiziwde: =, integer k ≠ 0 (2, 5) k ga salıstırǵanda bul shekleniw bizni nolge bolıwımızǵa tosqınlıq etedi. Keling, shaxstı (2. 5) kirgiziw qaǵıydası dep ataylik, sebebi, qaǵıyda retinde, biz odan bınamial koefficiyent belgisi astında qanday da interferensiyalanuvchi ózgeriwshin kirgiziw ushın paydalanamız. Bul teńleme (2. 1) Sonnan berli hám k! = k (k- 1)! de k > 0, k< 0 de bolsa eki bólim nolge teń. Eger eki bólekti (2. 5) k ga kópaytirsak, qosıw qaǵıydasın alamız, ol hátte k = 0 de da ustap turadı :, bir integer k. (2. 6 ) Bul koefficient tómengi indeksti óz jaǵdayında saqlaytuǵın analogga iye:, integer k (2. 7) Shaxstı (2. 7) eki simmetriya baylanısı hám olar ortasında bir tanısıw qaǵıydasınan kelip shıǵıw múmkin: (simmetriya sebepli) = ( kúshda (2. 6 )) =. (simmetriya sebepli) Bul shaxs hár qanday haqıyqıy r ushın tuwrı bolıp, juwmaq tek r integer oń san bolǵandaǵana haqıyqıy esaplanadı. Joqarı indeks r-1 teris bolmaǵan integer bolıwı kerek. Juwmaqumumiy oń r menen haqıyqıy bolıp, soǵan qaramay, sonı atap ótiw múmkin, bul shaxs barlıq bahalarda ustap turadı d eki bólim (2. 7) r salıstırǵanda dáreje k+1 dıń polinomlari bolıwı sebepli. Nol bolmaǵan dárejeden ibarat polinom d yamasa odan kem bolmaǵan polinom túrli nollardıń kóbisinde bolıwı múmkin - sol sebepli, d yamasa odan kem dárejede bolǵan eki bunday polinom ortasındaǵı parq, d noqatlardan kóre nolge búrila almaydı, nolge uqsas bolmasa. Basqasha etip aytqanda, eger d dárejeden ≤ eki polinom d noqattan artıq bolsa, ol halda olar barlıq noqatlarǵa tuwrı keledi. Biz hár sapar r unamlı tamǵa bolǵanda ayriqshalıq ne ekenligin kórsetemiz, sonda bul eki polinom sheksiz sanlı noqatlarǵa tuwrı keledi hám sol sebepli de nátiyjeli teń boladı. Aldınǵı paragraf daǵı tastıyıqlaw usılı, biz polinom argumentatsiya dep ataymız, integerlar ushın haqıyqıy bolǵan kóplegen baylanıslardı haqıyqıy sanlarǵa ótkeriwde paydalı bolıp tabıladı. Biz bunı kóp ret kóremiz. Birpara teńlemeler, mısalı, simmetriya koefficientler (2. 4) polinomlar ushın ózlik emes, sol sebepli biz mudamı da bul usıldı qollay almaymız. Biraq, kóplegen baylanıslar qálegen formaǵa iye. Qosıw formulası Barlıq bınamial ózliklerden eń áhmiyetlisi qosıw formulası dep ataladı :, bir integer k. (2. 8) Eger r oń san bolsa, ol halda paskal úshmuyesh degi hár bir san aldınǵı ceriyaning eki nomeriniń jıyındısı ekenligin kórsetedi, biri tuwrıdan-tuwrı onıń ústinde hám shepke jaqın bolǵan zat. Bul formula da teris, haqıyqıy yamasa kompleks r ga tiyisli bolıp, k integer boladı (sonda bınamial koefficiyentler anıqlanǵan). Qosıw formulasın tastıyıqlawdıń bir jolı r oń san dep esaplaw hám kombinatorial itibarlardan paydalanıw bolıp tabıladı. Eskertip ótemiz, bul r-element kompleksinen saylanǵan barlıq múmkin bolǵan k-element tómen jıynaqlarınıń sanı bolıp tabıladı. Eger bizde r máyek bolsa, olardan biri shirip ketken bolsa, ol halda k ni tańlaw jolları ámeldegi Máyekdon. Anıq jaǵdaylarda bul saylaw nátiyjesi tek jańa máyek boladı hám jaǵdaylarda olar arasında chirigan máyek boladı. Sebebi bunday saylaw nátiyjesi k - 1 r den 1 jańa máyek boladı. Bul eki sannı qosıp, alamız (2, 8). Bul juwmaqta r unamsız san hám sol k ≥ 0 dep shama etiledi. At k 0 < bul shaxstıń eki bólegi nolge teń bolıp, basqa barlıq jaǵdaylarda shaxstıń haqıyqıylıǵı (2. 8) polinom argumentatsiyasi menen ornatıladı. Identifikatorni (2. 8) qoyıw hám tasıwdıń eki qaǵıydasın (2. 7) hám (2. 6 ) qosıw arqalı da anıqlaw múmkin: shep tárepi, sol sebepli, hár eki bólekti r boyınsha bolıw múmkin. Bul juwmaq r = 0 jaǵdayınan tısqarı barlıq r ushın ustap turadı, bunı bólek tekseriw ańsat. taǵı bir itimaldastlabki tariypni tuwrıdan-tuwrı ayırbaslaw arqalı (2. 8) alıw edi. Eger k > 0 bolsa, ol halda Taǵı k≤ 0 bolǵan jaǵdaylardı bólek tekseriw ańsat. Házirgina qosıw formulasınıń ush júdá túrme-túr tastıyıqın kórdik.jáne bul ájep emes: bınamial koefficiyentler hár qıylı ayrıqshalıqlarǵa iye, olardıń parqı bizge qızıǵıwshılıq munasábetleriniń hár qıylı tastıyıqlarına alıp keliwi kerek. Tiykarınan, qosıw formulası Paskal úshmuyeshten sanlar ushın tákirarlanıw bolıp, basqa induksion kimliklerdi tastıyıqlawda ásirese paydalı ekenligin kóremiz. Yamasa bul tákirarlanishni jaylastırıw arqalı tezlik penen jańa identifikaciyanı alıwıńız múmkin. Sonday etip = 0 bolǵanlıǵı sebepli, aqırǵı aǵza joǵaladı hám siz toqtap qalıwıńız múmkin. Bul usıl ulıwma formulanı beredi: integer n. (2. 9 ) Itibar beriń, summa indeksin tómenden shegaralawdıń hájeti joq, sebebi < 0 dagi summanıń barlıq aǵzaları nolge teń. Bul formula joqarı hám tómen kórsetkishleri qalǵan basqalar jıyındısı retinde bir bınamial koefficiyentin bildiredi " teńlik". Bınamial koefficiyentlerdi eń tómen indeks menen izbe-iz dekompozitsiyalash arqalı taptık: aldın koefficiyent, keyininen koefficiyent, keyininen koefficiyent hám aqır-aqıbetde koefficiyent. hám eger siz basqa tárzde kengaysangiz ne boladı - izbe-iz eń joqarı tómengi indekske iye bolǵan koefficiyentlerdi bóleklew? Qarang: Endi koefficiyent nolge teń (tap sonday, olar bul koefficientti azmaz qızıqlıq beriwse de), hám siz ulıwma naǵıstı tutıwıńız múmkin: Biz joqarı indeks degi jıyındı formulası dep ataydigan bul shaxs bir bınamial koefficiyentti basqalardıń jıyındısı retinde bildiredi, onıń tómengi indeksleri ózgermeytuǵınnan ózgeredi. Bunda jıyındına k ≥ 0 tómenlew shegara kerek, sebebi k < 0 menen jıyındınıń shártleri nolge teń emes. Bunnan tısqarı, m hám n ulıwma teris bola almaydı. Shaxsı (2. 10 ) qızıqlı kombinatorial aytıw imkaniyatın beredi. Eger m + 1 ni 0 den n ge shekem nomerler menen nomerlengen 1 shıptanı tańlawshı bolsańız, saylanǵan shıptanıń eń úlken sanı k bolsa, bunı jollar menen ámelge asırıw múmkin. Koefficient (2. 9 ) da, koefficient (2. 10 ) da qosıw formulası járdeminde induksiya arqalı tastıyıqlanıwı múmkin, lekin bir munasábetti ekinshisidan da alıw múmkin. Mısal ushın (2. 9 ) den alıw (2. 10 ): tastıyıq bınamial koefficiyentler menen birpara standart operatsiyalardı kórsetedi. Ulıwma kóriniste háreket jobası tómendegishe: birinshiden, koefficienttiń shep tárepin (2. 9 ) koefficienttiń shep tárepine uqsap kórinisi ushın transformaciya qılıw (2. 9 ); keyin sońǵı koefficient járdemine shaqırıq etip, pútkil muǵdardı bir bınamial koefficiyent menen almastırıń ; aqır-aqıbetde, bul koefficiyentti ońǵa keltiriń (2. 9 ). Qolaylıq ushın shama menen oylayıq, r hám n teris bolmaǵan integerlar bolıp tabıladı. Ulıwma alǵanda qatnası (2. 9 ) polinom argumentiga kóre bul arnawlı jaǵdaydan alınadı. Keling, d ornına m jazıwǵa razı bo'laylik, sebebi bul ózgeriwshi kóbirek integer teris bolmaǵan sanǵa uqsaydı. Endi rejamizning sistemalı orınlanıwına ótiwimiz múmkin: Qádem-qádem bul juwmaqqa ámel etemiz. Sheshiwshi qádem ekinshi qatarda qóyıladı, ol jaǵdayda ornına simmetriya qaǵıydasın (2. 4) qollaymiz. hám bunı tek m+k ≥ 0 de ámelge asırıw múmkin, sol sebepli birinshi qádem jıyındınıń shártlerin k< -m menen tastap k ózgeris kólemin chekleydi (bul nızamlı, taslanǵan shártler nolge teń bolǵanı ushın ). Endi biz derlik qóllawǵa tayınmız (2. 10 ): k ni k-m menen almastırıw hám summalaw aralıǵın tuwrılaw. Bul qádem birinshisine uqsaydı. Lekin házir k joqarı indeksde payda boladı hám summatsiya shegaraları tuwrı formada beriledi, sonda tórtinshi qatarda ol qollanıladı (2. 10 ). Hámmesiniń aqırında simmetriya qaǵıydası taǵı bir bar isletiledi. Birpara summalar tiykarınan bul baylanısıwdıń (2. 10 ) yamasa jasırın variantlarınıń arnawlı jaǵdayları bolıp tabıladı. Mısalı, jaǵday m = 1 teris bolmaǵan integerlarning jıyındısın n ge shekem hám sonday-aq jetkezip beredi: Juwmaq Bul kurs jumısında eń keń tarqalǵan kombinatorial sxemalar tapildi, yaǵnıy : summa qaǵıydası, tuwrıdan-tuwrı ónim qaǵıydası, tákirarlanmasdan jaylastırıw, permutatsiya, kombinatsiya, polinom formula. Nyutondıń bınamial formulası qáliplestirilip, bınamial koefficiyentler haqqındaǵı teorem qáliplestirilip, tastıyıqlandi. Bınamial koefficiyentlerdiń tiykarǵı identifikaciyaları da názerde tutıladı. Mashqalalardi sheshiwde kombinatorial formulalardan paydalanıwdı kórsetiwshi mısallar da berilgen. Maǵlıwmat 1. Ivanov, B. N. Diskret matematika [Tekst]: A sabaqlıq / B. N. Ivanov. - M.: Tiykarǵı bilimler laboratoriyası, 2002.- 288 s.: 2. vilenkin, N. Ya. Kombinatorika [Tekst] / N. Y. vilenkin.- M.: Nauka, 1969.- 328 s. 3. Graham, R. Beton matematika [Tekst] / R. Graham, D. Knuth, A. Patashnik.- M.: «Mir», 1998.- 703 s. 4. Riordan, J. Kombinat shaxsı [Tekst] / J. Riordan.- M.: Nauka, 1982- jıl. Download 33.43 Kb. Do'stlaringiz bilan baham: 
|