REJA: 1.Kirish 2.Nyuton binomi haqida ma’lumot 3.Binomial koeffitsientlar 4.Xulosa 5.Foydalanilgan adabiyotlar KIRISH Diskret matematika - matematikaning bir qismi b o iib , meloddan aw al IV asrda yaratila boshlangan. Diskret matematika matematikaning takomillashgan sonlar nazariyasi, algebra, matematik mantiq qismlaridar. tashqari XX asr o ‘rtalaridagi fan-texnika taraqqiyoti tufayli jadal rivojla- nayotgan funksional sistemalar nazariyasi, graf va to'rlar nazariyasi, kodlashtirish nazariyasi, kombinator analiz kabi bo‘limlami ham o‘z ichiga oladi. Dastlab faqat matematik mantiq, algebra, matematik analiz, matematika asoslari, ehtimollar nazariyasi, geometriya, topologiya, sonlar nazariyasi, modellar nazariyasi kabi matematik fanlarda tatbiq etib kelingan diskret matematika XX asming 40- yillaridan boshlab hisoblash matematikasi, kibemetika, axborot texnologiyalari, iqtisodiyot, psixologiya, matematik lingvistika, tibbiyot fanlari va diskret texnikada ham keng qo‘llanilmoqda. Diskret matematika elektr sxemalami loyihalashda va tekshirishda, avtomatik hisoblash mushinalarini loyihalash va dasturlashtirishda, diskret avtomatlarni mantiqiy loyihalashda, EHM elementlari va qismlarini loyihalashda, har xil texnik sistemalar, qurilmalar va avtomatik mashinalami tahlil va sintez qilishda keng miqyosda tatbiq etiladi. Matematik mantiq fani elektron hisoblash mashinalarining vujudga kelishiga va uni mukammalashtirishga katta hissa qo‘shdi. Diskret matematika informatikaning poydevori bo‘lishi bilan birga, hozirgi zamon matematik ta’limning muhim bo‘g ‘ini ham hisoblanadi. Mantiq - muhokama yuritishning qonun-qoidalari, usullari va formalari (shakliari) haqidagi fan bo'lib, uning asoschisi qadimgi yunon mutafakkiri Aristotel (miloddan avvalgi 384-322 y.) hisoblanadi. U birinchi bo'lib deduksiya nazariyasini, ya’ni mantiqiy xulosa chiqarish nazariyasini yaratib, mantiqiy xulosa chiqarishning formal xarakterga ega ekanligini ko'rsatdi. Aristotelning mantiqiy ta’limoti formal mantiqning (logikaning) asosini tashkil qiladi. Formal mantiq fikrlashning formalari va qonunlarini tekshiradi. Shunday qilib, Aristotel mantiqiy fikrlashning asosiy qonunlarini ochdi.Aristotel asos solgan mantiq ko'p asrlar davomida turli mutafakkirlar, faylasuflar va butun falsafiy maktablar tomonidan to'ldirildi, o'zgartirildi va takomillashtirildi. Shu jumladan, Abu Nasr Farobiy, Abu Ali Ibn Sino, Abu Rayxon Beruniy, Muhammad al-Xorazmiy, Umar Xayyom,Alisher Navoiy, Mirzo Bedil kabi Sharqning buyuk mutafakkirlari ham o'zlarining katta hissalarini qo'shdilar. Nyuton binomi - ikki qoʻshiluvchi yigʻindisining ixtiyoriy butun musbat darajasini qoʻshiluvchilar darajalari yigʻindisi koʻrinishda ifodalovchi formula. Binomial koeffitsiyentlari arifmetik uchburchak tashkil qiladi. Nyuton binomi formulasi I. Nyutondan ancha avval ham maʼlum boʻlgan. Masalan, Umar Xayyom (11 — 12-asrlar), Jamshid Koshiy (14—15-asrlar) binomial koeffitsiyentlarni hisoblash qoidasini bilganlar. I. Nyuton esa binom yoyilmasini ixtiyoriy koʻrsatkich uchun umumlashtirgan. Nyuton binomi matematik analiz, sonlar nazariyasi, ehtimollar nazariyasi va boshqa sohalarda muhim ahamiyatga ega. O’rta maktab matematikasida quyidagi ikkita qisqa ko’paytirish formulalarini eslasak: Yig’indining navbatdagi ikkita ,yani 4-va5-darajalarini hisoblaymiz: (a + b)4 = (a + b)(a + b)3 = (a + b)(a3 + 3a2b + 3ab2 + b3 ) = = a4 + 4a3b + 6a2b2 + 4ab3 + b4 , (a + b)5 = (a + b)(a + b)4 =( = a5 + 5a4b + 10a3b2 + 10a2b3 + 5ab4 + b5 Shunday qilib, yig‘indining bikvadrati (ya’ni to‘rtinchi darajasi) (a + b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4 va yig‘indining beshinchi darajasi (a + b)5 = a5 + 5a4b + 10a3b2 + 10a2b3 + 5ab4 + b5 formulalariga ega bo‘lamiz. Yuqorida keltirilgan yig‘indining kvadrati, kubi, bikvadrati va beshinchi darajasi formulalari o‘ng tomonlaridagi ko‘phad koeffitsientlari Paskal uchburchagining mos nqatorlaridagi Cm ( n = 2,3,4,5 ) sonlar ekanligini payqash qiyin emas. 1-t e o r e m a . Barcha haqiqiy a va b hamda natural n sonlar uchun formula o‘rinlidir. I s b o t i . Matematik induksiya usulini qo‘llaymiz. Baza: n=1 bo’lganda formula to’g’ri: Induksion o‘tish: isbotlanishi kerak bo‘lgan formula n=k uchun to’g’ri bo’lsin, Ya’ni Formula n=k+1 bo’lganda ham to’g’ri ekamligini isbotlaymiz.Haqiqatdan ham = formuladan foydalanib ,quyidagilarni hosil qilamiz: Ixtiyoriy a va b haqiqiy sonlar hamda n natural son uchun Ifodaning ko’phad shaklidagi yoyilmasi Nyuton binomi deb ataladi . sonlarini Binomial koeffitsientlar deb atashadi. Bunday ta’rif bu koeffitsietlarning Nyuton binomi formulasida tutgan o’rniga qarab berilgan bo’lib, son Yoyilmadagi ifodning koeffitsientidir. 2-t e o r e m a . Barcha haqiqiy a va b hamda natural n sonlar uchun Formula o’rinlidir. I s b o t i . Nyuton binomi formulasida b ni (-b)ga almashtirsak kerakli formulani hosil qilamiz. 1-m i s o l . Oxirgi formuladan xususiy holda quyidagi qisqa ko‘paytirish formulalari kelib chiqadi: n=2 bo‘lganda ayirmaning kvadrati formulasi n=3 bo’lganda ayirmaning kubi formulasi Nyuton binomi formulasini kombinatorik amallar yordamida ham hosil qilish mumkin.Haqiqatdan ham , ixtiyoriy ,.., sonlar uchun ) ifodani ) Ko’rinishda yozish mumkin.Bu tenglikdan o’ng tomonda joylashgan oldidagi koeffitsient birga teng. Birinchi qavslar ichidagi qo‘shiluvchilar Soni n ga ) tengligi yaqqol n n ko‘rinibturibdi. Ikkinchiqavslar ichidagiqo‘shiluvchilar b1, b2 ,..., bn (n ta)elementlardan nikkitadan ko‘paytmalar (soni C2 ga teng gruppalashlar) ekanligini ham payqash qiyin emas. Uchinchi qavslar ichidagi qo‘shiluvchilar esa o‘sha n ta elementlardan uchtadan ko‘paytmalar nbo‘lib, ularning soni C3ga teng va hokazo. Oxirgi qo‘shiluvchi oldidagi koeffitsient birga ( n1 = Cn ) teng. Yuqoridagi tenglikda hosil qilamiz. b1 = b2 = ... = bn = b deb olsak, Nyuton binomi formulasini Binomial koeffitsientlarning xossalari=Binomial koeffitsientlarning ba’zi xossalarini keltiramiz. Bu xossalar bevosita gruppalashlarga oid bo‘lib, tabiiyki, ular Paskal uchburchagining xossalarini ham ifodalaydi. xossa . m+1 CC n m n n - m m +1 ( m = 0,1,2,...,n - 1) tenglik o‘rinlidir. Haqiqatdan ham, Cm+1 n = Cm n! (m +1)!(n - m -1)! = n! m!(n - m)! = (m +1)!(n -m -1)! n m!(n -m)! = m!(n - m - 1)!(n - m) = n - m . ■ m!(m +1)(n - m - 1)! m + 1 Bu xossa binomial koeffitsientlar qatoridagi istalgan ketma-ket ikki elementning biri ma’lum bo‘lsa, boshqasini osonlik bilan hisoblash mumkinligini ko‘rsatadi: Cm+1 = n - m Cm , Cm = m + 1 Cm+1 , bu yerda m = 0,1,2,...,n -1 . n m + 1 n n n - m n xossa . Ixtiyoriy natural n son uchun barcha m ( m =0,n ) binomial koeffitsientlarnC yig‘indisi 2n ga teng, ya’ni C0 +C1 +C2+ ... +Cn-1+ Cn =2n . n n n n n Bu tenglik Nyuton binomi formulasida a = b =1 deb olganda hosil bo‘ladi. ■ xossa . Toq o‘rinlarda turgan binomial koeffitsientlar yig‘indisi juft o‘rinlarda turgan binomial koeffitsientlar yig‘indisiga teng.Haqiqatdan ham, Nyuton binomi formulasida a =1va b =-1 deb olganda 0 =C0 -C1 +C2- C3+ ... +(-1)n Cn n n n n n tenglikni hosil qilamiz. Bu tenglikdan xossadagi tasdiqning to‘g‘riligi kelib chiqadi. ■ 2-va 3-xossalar asosida quyidagi xossani hosil qilamiz. xossa . n natural sondan oshmaydigan eng katta toq m son uchunC1 +C3 +... + Cm =2n-1tenglik hamda n sondan oshmaydigan eng katta juft m son uchun n n n C0 +C2 +... + Cm =2n-1tenglik o‘rinlidir. n n n xossa . Toq n son uchunC0< C1< ... < C n-1 2 n-1 +1 = C 2 , n-1 +1 C 2 n-1 +2 C 2 > ... > Cn , n n juft n son uchun esa n n n n n n n n +1 C0< C1< ... < C 2 , C 2 >C 2 > ... > Cn , n n munosabatlar o‘rinlidir. n n n n Haqiqatdan ham, m < n - 1 2 shartni qanoatlantiruvchi ixtiyoriy natural n va m sonlar uchun n - m > 1 m +1 tengsizlik o‘rinlidir, m > n - 1 2 bo‘lganda esa n - m < 1 m +1 tengsizlikka ega bo‘lamiz. Bu yerda Cm+1 = n - m Cm formulani (1-xossaga qarang) qo‘llab, xossadagi barcha n m + 1 n tengsizliklarni hosil qilamiz. Agar n toq son bo‘lsa, m = n - 1 butun son bo‘lib, n - m = n - n - 1 2 = 2n - n + 1 = n + 1 = 1 2 n - m m +1 n - 1 + 1 2 Cn - 1 n - 1+ 2 n + 1 n-1 +1 n-1 nmunosabat o‘rinlidir. Demak, tenglik kelib chiqadi. ■ Cm+1 = m +1 m formuladan m = n2 bo‘lganda Cn 2 = Cn 2 Binomial koeffitsientlarning 5-xossasi Paskal uchburchagining yuqorida keltirilgan nné n ù xossalari tasdig‘i bo‘lib, unga ko‘ra binomial koeffitsientlar oldin C0= 1dan C êë 2 úû gacha11 no‘sadi, keyin esa Cn =1gacha kamayadi hamda n toq bo‘lganda binomial koeffitsientlar qatorining o‘rtasidagi ikkita hadi tengdir va n juft bo‘lganda uning o‘rtadasigi hadi eng katta va yagonadir. Quyidagi 6–8-xossalar o‘rinlidir. xossa . Cn +Cn + ... +Cn = Cn+1 . n n+1 n+k n+k +1 7-xossa . (C0 )2 + (C1 )2 + ... + (Cn )2 = Cn . n n n 2n 8-xossa . C0Ck +C1Ck-1+... +CkC0= Ck . n m n m n m n+m Oxirgi tenglik Koshi12 ayniyati deb aytiladi. Endi bu uchta xossalarni isbotlaymiz. Dastlab 6-xossaning isbotini keltiramiz. Birinchidan, s =(1 + x)n + (1 + x)n+1+ ... +(1 + x)n+k ko‘phad uchun Nyuton binomi formulasini qo‘llab, quyidagi tenglikni hosil qilamiz: n n+1 n+ k s =åCmxm +åCm xm + ... + åCm xm . n m=0 m=0 n+1 m=0 n+k Bu yerdan, s ko‘phaddagi xn ifodaning koeffitsienti Cn + Cn +... + Cn n yig‘indiga tengligini aniqlash mumkin. n+1 n+k Ikkinchidan, s = (1+x)n (1+(1+x) +... + (1+x)k ) ifodani geometrik progressiya hadlari yig‘indisi formulasiga binoan quyidagicha ham yozish mumkin: s =(1+ n (1+ x)k+1 -1 = 1 ( x) n+k +1 - (1+ x)n ). (1x)1+ x -1 x CBu yerda ham Nyuton binomi formulasini qo‘llab, hosil bo‘lgan ko‘phadning xn daraja qatnashgan hadi koeffitsienti n+1 n+k +1 ekanligini ko‘rish mumkin. Keltirilgan bu mulohazalar asosida 6-xossadagi tenglikka ega bo‘lamiz. ■ Ravshanki, Cm =Cn-m formula e’tiborga olinsa, 7-xossa 8-xossadan m = k = n bo‘lganda n n xususiy hol sifatida kelib chiqadi. Shuning uchun faqat 8-xossaning isbotini keltirish bilan chegaralanamiz. Birinchidan, Nyuton binomi formulasiga ko‘ra 11 [a] yozuv a sonning butun qismini anglatadi. 12Koshi (Cauchy Ogyusten Lui, 1789-1857) –fransuz matematigi. (1 + x)n = nås=0 Cs xs , (1 + x)m= åt=0 Ct xt, n+m (1+ x) = åCxn+m p p n+m p=0 mn m n+m tengliklarga, bulardan esa (1+x)n (1+x)m = (1+x)n+m bo‘lgani uchun åCs xs åCt xt = åC p x p n s=0 m t =0 p=0 n+m tenglikka ega bo‘lamiz. Oxirgi tenglikning ikkala tomonidagi xk ( k = 0,1,..., min(m, n) ) daraja koeffitsientlarini bir-biriga tenglashtirsak, isbotlanishi kerak bo‘lgan formulani hosil qilamiz. ■ Albatta, yuqoridagu uchta xossalar boshqa usullar bilan ham isbotlanishi mumkin. Quyida 8-xossaning kombinatorik tahlilga asoslangan isboti keltirilgan. 2-m i s o l . Koshi ayniyatini kombinatorik tahlilga asoslangan holda isbotlaymiz. n nafar o‘g‘il va m nafar qiz bolalardan tashkil topgan talabalar guruhidan k ( k = 0,1,..., min(m, n) n+m) nafar talaba tanlash zarur bo‘lsin. n + m nafar talabalardan k nafar talabani Ck xil usul bilan tanlash mumkinligi ravshan. Boshqa tomondan olib qaraganda, n + m nafar talabalardan iborat to‘plamdan Ctanlanadigan barcha k elementli qism to‘plamlarni ularning tarkibidagi o‘g‘il bolalar soniga qarab sinflarga ajratishning quyidagicha imkoniyati bor. Tarkibida s ( 0 £ s £ k ) nafar o‘g‘il Cbola bo‘lgan k elementli qism to‘plamni oldin s xil usul bilan tanlab, keyin (k - s) nafar qiz nbolalarni k -s m xil usullardan birortasi yordamida tanlash mumkin. Demak, tarkibida s nafar o‘g‘il bola bo‘lgan k nafar talabadan iborat qism to‘plamlar soni, ko‘paytirish qoidasiga asosan, CsCk -s songa tengdir. Noldan k gacha bo‘lgan barcha butun s sonlar uchun barcha n m kombinatsiyalarni hosil qilib va bu kombinatsiyalarga mos ko‘paytmalarni yig‘ib, Koshi ayniyatining chap tomonini hosil qilamiz. ■ Binomial koeffitsientlarning yuqorida keltirilgan xossalarini tahlil qilish natijasida ularning turli sohalardagi tadbiqlari doirasining kengligini payqash mumkin. Misol sifatida to‘plamlamlar nazariyasiga tadbiqini qaraymiz. 3-m i s o l . ChekliA to‘plam2A buleanining elementlari va bu elementlar soni bilan binomial koeffitsientlarning uzviy bog‘lanishi bor. Bu bog‘lanish quyidagicha ifodalashi mumkin. Chekli A to‘plam 2A buleani tarkibidagi elementlar A to‘plamning qism nto‘plamlaridan iborat bo‘lgani uchun, shu qism to‘plamlarni quvvatlari bo‘yicha ( | A | +1)ta guruhlarga ajratish mumkin. Tushunarliki, bu yerda k raqamli guruh ( k = 0,| A | ) quvvati k ga teng bo‘lgan barcha qism to‘plamlardan tashkil topadi va undagi qism to‘plamlar soni teng. ■ Ck g XULOSA Diskret matematika matematikaning takomillashgan sonlar nazariyasi, algebra, matematik mantiq qismlaridar. Tashqari XX asr o ‘rtalaridagi fan-texnika taraqqiyoti tufayli jadal rivojla- nayotgan funksional sistemalar nazariyasi, graf va to'rlar nazariyasi, kodlashtirish nazariyasi, kombinator analiz kabi bo‘limlami ham o‘z ichiga oladi. Dastlab faqat matematik mantiq, algebra, matematik analiz, matematika asoslari, ehtimollar nazariyasi, geometriya, topologiya, sonlar nazariyasi, modellar nazariyasi kabi matematik fanlarda tatbiq etib kelingan diskret matematika XX asming 40- yillaridan boshlab hisoblash matematikasi, kibemetika, axborot texnologiyalari, iqtisodiyot, psixologiya, matematik lingvistika, tibbiyot fanlari va diskret texnikada ham keng qo‘llanilmoqda FOYDALANILGAN ADABIYOTLAR 1.MATEMATIK MANTIQ VA DISKRET MATEMATIKA kitobi (XOTAM TO’RAYEV) 2. https://uz.wikipedia.org/wiki/Nyuton_binomi 3. https://uztext.com/51939-text.html