Diskret tuzilmalar” fanidan 1-mustaqil ish Mavzu

|
Diskret tuzilmalar” fanidan 1-mustaqil ish Mavzu
|
bet | 1/2 | Sana | 15.05.2024 | Hajmi | 32,71 Kb. | | #233949 |
Bog'liq Shoxrux
O’ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYAL
VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT
TEXNOLOGIYALARI UNIVERSITETI
“Diskret tuzilmalar” fanidan
1-mustaqil ish
Mavzu: Nyuton binomi koeffisientlarini hiosblash formulalari
Bajardi: Mamatqulov Shoxrux
Tekshirdi: Yusupov Muxtorbek
Toshkent 2024
NYUTON BINOMI. BINOMIAL KOEFFITSIENTLAR
Reja:
1. Paskal uchburchagi haqida umumiy ma’lumotlar
2. Nyuton binomi haqida umumiy ma’lumotlar
3. Binomial koeffitsientlarning xossalari
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
1. Paskal uchburchagi haqida umumiy ma’lumotlar Berilgan n ta elementdan m tadan gruppalashlar soni m Cn uchun bir necha qatorlarni 1- jadvaldagidek yozamiz: 1-jadval n Gruppalashlar soni m Cn ( m 0,n ) 1 1 0 C1 , 1 1 C1 2 1 0 C2 , 2 1 C2 , 1 2 C2 3 1 0 C3 , 3 1 C3 , 3 2 C3 , 1 3 C3 4 1 0 C4 , 4 1 C4 , 6 2 C4 , 4 3 C4 , 1 4 C4 5 1 0 C5 , 5 1 C5 , 10 2 C5 , 10 3 C5 , 5 4 C5 , 1 4 C4 … …………………………………………………………. Bu jadvalda gruppalashlar sonining quyidagi xossalarini kuzatish mumkin: – har bir qatorning chetlarida birlar joylashgan (bu tasdiq 1 0 n Cn Cn formula bilan ifodalanadi); – har bir qatordagi m Cn sonlar qatorning teng o‘rtasiga nisbatan simmetrik joylashgan, ya’ni qatorning boshidan va oxiridan baravar uzoqlikda turgan sonlar o‘zaro teng ( n m n m Cn C ); – ikkinchi qatordan boshlab har bir qatordagi birlardan tashqari ixtiyoriy son bu qatordan yuqorida joylashgan qatordagi biri shu son ustida, ikkinchisi esa undan chapda joylashgan ikkita gruppalashlar sonining yig‘indisiga teng ( 1 1 1 m n m n m Cn C C ); – har bir qatordagi m Cn sonlar shu qator teng o‘rtasigacha o‘sib, so‘ng kamayadi. Ta’rif sifatida 1 0 C0 deb qabul qilinsa va bu son yuqoridagi jadvalning n 1 raqamli qatoridan oldin n 0 raqamli qatori sifatida joylashtirilsa, uchburchak figurasiga o‘xshash 1-shakldagi sonlar jadvalini hosil qilish mumkin. 1-shakldagi sonlar jadvali Paskal uchburchagi deb ataladi. Bu jadval arifmetik uchburchak nomi bilan ham yuritiladi. Uning Paskal nomi bilan atalishiga qaramasdan, bunday sonlar jadvali juda qadimdan dunyoning turli mintaqalarida, jumladan, sharq mamlakatlarida ham ma’lum bo‘lgan. Masalan, Erondagi Tus shahrida (hozirgi Mashhadda) 1 7 21 35 35 21 7 1 1 6 15 20 15 6 1 1 5 10 10 5 1 1 4 6 4 1 1 3 3 1 1 2 1 1 1 1 1- shakl 2 yashab ijod qilgan Nosir at-Tusiy1 XIII asrda bu jadvaldan foydalanib, berilgan ikkita son yig‘indisining natural darajasini hisoblash usulini o‘zining ilmiy ishlarida keltirgan bo‘lsa, g‘arbda Al-Kashi nomi bilan mashhur Samarqandlik olim Ali Qushchi2 butun sonning istalgan natural ko‘rsatkichli arifmetik ildizi qiymatini taqribiy hisoblashda bu jadvaldan foydalana bilganligi haqida ma’lumotlar bor. Keyinchalik G‘arbiy Yevropada bu sonlar uchburchagi haqida M. Shtifel3 arifmetika bo‘yicha qo‘llanmalarida yozgan va u ham butun sondan istalgan natural ko‘rsatkichli arifmetik ildizning taqribiy qiymatini hisoblashda bu uchburchakdan foydalana bilgan. 1556 yilda bu sonlar jadvali bilan N. Tartalya4 , keyinroq logarifmik lineyka ijodkori U. Otred5 (1631 yil) ham shug‘ullanganlar. 1654 yilga kelib B. Paskal o‘zining “Arifmetik uchburchak haqidagi traktat” nomli asarida bu sonlar jadvali haqidagi ma’lumotlarni e’lon qildi. Paskal uchburchagidagi qatorlar istalgancha davom ettirilishi mumkin. Shunisi qiziqki, Paskal uchburchagi yordamida istalgan n ta elementdan m tadan gruppalashlar sonini faqat qo‘shish amali yordamida hosil qilish mumkin ( m Cn sonni hisoblash !( )! ! m n m n C m n , 1 2 ...( ) ( 1)...( 1) n m n n m C m n va m n n n m C m n 1 2 ... ( 1)...( 1) formulalariga qarang). Bu amal m n m n m Cn C C 1 1 1 formulaga asoslanadi. Paskal uchburchagi ko‘plab ajoyib xossalarga ega. B. Paskal yuqorida zikr etilgan traktatda: “Bu xossalarning haqiqatdan ham bitmas-tuganmasligi naqadar ajoyibdir” deb yozgan edi. 2. Nyuton binomi haqida umumiy ma’lumotlar O‘rta maktab matematikasi kursidan quyidagi ikkita qisqa ko‘paytirish formulalarini eslaylik: 2 2 2 (a b) a 2ab b – yig‘indining kvadrati; 3 3 2 2 3 (a b) a 3a b 3ab b – yig‘indining kubi. Yig‘indining navbatdagi ikkita, ya’ni 4-va 5-darajalarini hisoblaymiz: ( ) ( )( ) ( )( 3 3 ) 4 3 3 2 2 3 a b a b a b a b a a b ab b 4 3 2 2 3 4 a 4a b 6a b 4ab b , 5 4 (a b) (a b)(a b) 5 4 3 2 2 3 4 5 a 5a b 10a b 10a b 5ab b . Shunday qilib, yig‘indining bikvadrati (ya’ni to‘rtinchi darajasi) 4 4 3 2 2 3 4 (a b) a 4a b 6a b 4ab b va yig‘indining beshinchi darajasi 1 At-Tusiy (Nosir ad-Din-Muhammad ibn Muhammad ibn-al-Hasan, 1201-1274) – Eron astronomi va matematigi. 2 Ali Qushchi (Jamshid ibn Ma’sud, tug‘ilgan yili noma’lum–taxminan 1436 yoki 1437 yilda vafot etgan) – o‘zbek matematigi va astronomi, 1420-30 yillarda Samarqandda Mirzo Ulug‘bek observatoriyasida ishlagan. 3 Shtifel Mixel (Michel, 1487-1567) – olmon matematigi. 4 Tartalya Nikkolo (Tartalia Nic-colo, 1499 yil atrofida tug‘ilgan-1557) – italyan matematigi va mexanigi. 5 Otred Uilyam (Outred William, 1574-1660) – ingliz matematigi. 3 5 5 4 3 2 2 3 4 5 (a b) a 5a b 10a b 10a b 5ab b formulalariga ega bo‘lamiz. Yuqorida keltirilgan yig‘indining kvadrati, kubi, bikvadrati va beshinchi darajasi formulalari o‘ng tomonlaridagi ko‘phad koeffitsientlari Paskal uchburchagining mos qatorlaridagi m Cn ( 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 n n n n n n n n n n a b a C a b C a b C ab b 1 1 2 2 2 1 1 ( ) ... formula o‘rinlidir. I s bo t i . Matematik induksiya usulini qo‘llaymiz. Baza: n 1 bo‘lganda formula to‘g‘ri: a b a b 1 ( ) . Induksion o‘tish: isbotlanishi kerak bo‘lgan formula n k uchun to‘g‘ri bo‘lsin, ya’ni k k k k k k k k k k a b a C a b C a b C ab b 1 1 2 2 2 1 1 ( ) ... . Formula n k 1 bo‘lganda ham to‘g‘ri ekanligini isbotlaymiz. Haqiqatdan ham, 1 1 1 m n m n m Cn C C formuladan foydalanib, quyidagilarni hosil qilamiz: k k (a b) (a b)(a b) 1 ( )( ... ) 1 1 2 2 2 k 1 k 1 k k k k k k k a b a C a b C a b C ab b k k k k k k k k a C a b C a b ... C ab 1 1 2 1 2 0 1 1 2 1 1 ... k k k k k k k Ck a b C a b C ab b ( ) ( ) ... 1 0 1 1 2 1 2 a C C a b C C a b k k k k k k k 1 1 ... ( ) k k k k k Ck C ab b 1 1 2 1 2 1 1 1 1 ... k k k k k k k k k a C a b C a b C ab b . ■ Ixtiyoriy a va b haqiqiy sonlar hamda n natural son uchun n (a b) ifodaning ko‘phad shaklidagi yoyilmasi (tasvirlanishi) Nyuton6 binomi deb ataladi. Umuman olganda, “Nyuton binomi” iborasiga tanqidiy nuqtai nazardan yondoshilsa, undagi ikkala so‘zga nisbatan ham shubha tug‘iladi: birinchidan, n (a b) ifoda birdan katta natural n sonlar uchun binom (ya’ni ikkihad) emas; ikkinchidan, natural sonlar uchun bu ifodaning yoyilmasi Nyutongacha ma’lum edi7 . Greklar n (a b) ifodaning qatorga yoyilmasini n ning faqat n 2 bo‘lgan holida (ya’ni, yig‘indi kvadratining formulasini) bilar edilar. Umar Hayyom8 va Ali Qushchi n (a b) ifodani n 2 bo‘lgan natural sonlar uchun ham qatorga yoya bilganlar. Nyuton esa 1767 yilda yoyilma formulasini isbotsiz manfiy va kasr n sonlar uchun ham qo‘llagan. L. Eyler 1774 yilda Nyuton binomi formulasini kasr n sonlar uchun isbotladi, K. Makloren9 esa bu formulani darajaning ratsional ko‘rsatkichlari uchun qo‘lladi. Nihoyat, 1825 yilda N. Abel10 daraja ko‘rsatkichining istalgan kompleks qiymatlari uchun binom haqidagi teoremani isbotladi. 6 Isaak Nyuton (Newton, 1643-1727) – ingliz fizigi, mexanigi va matematigi. 7 Ushbu paragrafning 3.1 bandidagi xronologik ma’lumotlarga qarang. 8 Umar Hayyom G‘iyosiddin Abul-Fatx ibn Ibrohim (خیام عمر, 1048 yil atrofida tug‘ilgan-1122 yildan so‘ng vafot etgan) – fors va tojik shoiri, matematigi va faylasufi. 9 Makloren Kolin (Maclaurin Colin, 1698-1746) – Shotlandiya matematigi. 10 Abel Nils Xenrik (Niels Henric, 1802-1829) – Norvegiya matematigi. 4 m Cn sonlarni binomial koeffitsientlar deb ham atashadi. Bunday ta’rif bu koefitsientlarning Nyuton binomi formulasida tutgan o‘rniga qarab berilgan bo‘lib, m Cn son n m m n m m n n a b C a b 0 ( ) yoyilmadagi n m m a b ifodaning koeffitsientidir. 2-t e o r e m a . Barcha haqiqiy a va b hamda natural n sonlar uchun n m m n m m n n m a b C a b 0 ( ) ( 1) 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 2 2 2 (a b) a 2ab b ; n 3 bo‘lganda ayirmaning kubi formulasi 3 3 2 2 3 (a b) a 3a b 3ab b . ■ Nyuton binomi formulasini kombinatorik amallar yordamida ham hosil qilish mumkin. Haqiqatdan ham, ixtiyoriy a b b bn , , ,..., 1 2 sonlar uchun ( )( )...( ) a b1 a b2 a bn ifodani ( )( )...( ) ( ... ) 1 2 1 1 2 n n n a b a b a bn a a b b b ( ... ) 1 2 1 3 1 2 n n n a bb bb b b n n n n n a (b1b2b3 ... b 2b 1b ) ... b1b2 ...b 3 . ko‘rinishda yozish mumkin. Bu tenglikning o‘ng tomonida joylashgan n a oldidagi koeffitsient birga ( 0 1 Cn ) teng. Birinchi qavslar ichidagi qo‘shiluvchilar soni n ga ( 1 n Cn ) tengligi yaqqol ko‘rinib turibdi. Ikkinchi qavslar ichidagi qo‘shiluvchilar b b bn , ,..., 1 2 ( n ta) elementlardan ikkitadan ko‘paytmalar (soni 2 Cn ga teng gruppalashlar) ekanligini ham payqash qiyin emas. Uchinchi qavslar ichidagi qo‘shiluvchilar esa o‘sha n ta elementlardan uchtadan ko‘paytmalar bo‘lib, ularning soni 3 Cn ga teng va hokazo. Oxirgi qo‘shiluvchi oldidagi koeffitsient birga ( n 1 Cn ) teng. Yuqoridagi tenglikda b1 b2 ... bn b deb olsak, Nyuton binomi formulasini hosil qilamiz. 3. Binomial koeffitsientlarning xossalari Binomial koeffitsientlarning ba’zi xossalarini keltiramiz. Bu xossalar bevosita gruppalashlarga oid bo‘lib, tabiiyki, ular Paskal uchburchagining xossalarini ham ifodalaydi. 1-xossa . 1 1 m n m C C m n m n ( m 0,1,2,..., n 1 ) tenglik o‘rinlidir. Haqiqatdan ham, 5 ( 1)!( 1)! !( )! !( )! ! ( 1)!( 1)! ! 1 m n m m n m m n m n m n m n C C m n m n !( 1)( 1)! 1 !( 1)!( ) m n m m m n m m n m n m . ■ Bu xossa binomial koeffitsientlar qatoridagi istalgan ketma-ket ikki elementning biri ma’lum bo‘lsa, boshqasini osonlik bilan hisoblash mumkinligini ko‘rsatadi: m n m n C m n m C 1 1 , 1 1 m n m n C n m m C , bu yerda m 0,1,2,..., n 1. 2-xossa . Ixtiyoriy natural n son uchun barcha m Cn ( m 0,n ) binomial koeffitsientlar yig‘indisi n 2 ga teng, ya’ni n n n n Cn Cn Cn ... Cn C 2 0 1 2 1 . Bu tenglik Nyuton binomi formulasida a b 1 deb olganda hosil bo‘ladi. ■ 3-xossa . Toq o‘rinlarda turgan binomial koeffitsientlar yig‘indisi juft o‘rinlarda turgan binomial koeffitsientlar yig‘indisiga teng. Haqiqatdan ham, Nyuton binomi formulasida a 1 va b 1 deb olganda n n n 0 Cn Cn Cn Cn ... ( 1) C 0 1 2 3 tenglikni hosil qilamiz. Bu tenglikdan xossadagi tasdiqning to‘g‘riligi kelib chiqadi. ■ 2-va 3-xossalar asosida quyidagi xossani hosil qilamiz. 4-xossa . n natural sondan oshmaydigan eng katta toq m son uchun 1 3 1 ... 2 m n Cn Cn Cn tenglik hamda n sondan oshmaydigan eng katta juft m son uchun 0 2 1 ... 2 m n Cn Cn Cn tenglik o‘rinlidir. 5-xossa . Toq n son uchun 1 2 1 2 1 0 1 ... n n n Cn Cn Cn C , n n n n n Cn C C ... 2 2 1 1 2 1 , juft n son uchun esa 0 1 2 ... n Cn Cn Cn , n n n n n Cn C C ... 1 2 2 , munosabatlar o‘rinlidir. Haqiqatdan ham, 2 1 n m shartni qanoatlantiruvchi ixtiyoriy natural n va m sonlar uchun 1 1 m n m tengsizlik o‘rinlidir, 2 1 n m bo‘lganda esa 1 1 m n m tengsizlikka ega bo‘lamiz. Bu yerda m n m n C m n m C 1 1 formulani (1-xossaga qarang) qo‘llab, xossadagi barcha tengsizliklarni hosil qilamiz. 6 Agar n toq son bo‘lsa, 2 1 n m butun son bo‘lib, 1 1 1 1 2 2 1 1 2 1 2 1 1 n n n n n n n n m n m munosabat o‘rinlidir. Demak, m n m n C m n m C 1 1 formuladan 2 1 n m bo‘lganda 2 1 1 2 1 n n n Cn C tenglik kelib chiqadi. ■ Binomial koeffitsientlarning 5-xossasi Paskal uchburchagining yuqorida keltirilgan xossalari tasdig‘i bo‘lib, unga ko‘ra binomial koeffitsientlar oldin 1 0 Cn dan 2 n Cn gacha11 o‘sadi, keyin esa 1 n Cn gacha 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. 6-xossa . 1 1 1 ... n n k n n k n n n Cn C C C . 7-xossa . n n n Cn Cn Cn C2 2 2 1 2 0 ... . 8-xossa . k m n m k n k n m k CnCm C C C C C 0 1 1 0 ... . Oxirgi tenglik Koshi12 ayniyati deb aytiladi. Endi bu uchta xossalarni isbotlaymiz. Dastlab 6-xossaning isbotini keltiramiz. Birinchidan, n n n k s x x x (1 ) (1 ) ... (1 ) 1 ko‘phad uchun Nyuton binomi formulasini qo‘llab, quyidagi tenglikni hosil qilamiz: n k m m m n k n m m m n n m m m n s C x C x C x 0 1 0 1 0 ... . Bu yerdan, s ko‘phaddagi n x ifodaning koeffitsienti n n k n n n Cn C C ... 1 yig‘indiga tengligini aniqlash mumkin. Ikkinchidan, (1 ) (1 (1 ) ... (1 ) ) n k s x x x ifodani geometrik progressiya hadlari yig‘indisi formulasiga binoan quyidagicha ham yozish mumkin: n k n k n x x x x x s x (1 ) (1 ) 1 1 1 (1 ) 1 (1 ) 1 1 . Bu yerda ham Nyuton binomi formulasini qo‘llab, hosil bo‘lgan ko‘phadning n x daraja qatnashgan hadi koeffitsienti 1 1 n Cn k ekanligini ko‘rish mumkin. Keltirilgan bu mulohazalar asosida 6-xossadagi tenglikka ega bo‘lamiz. ■ Ravshanki, n m n m Cn C formula e’tiborga olinsa, 7-xossa 8-xossadan m k n bo‘lganda 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. 12 Koshi (Cauchy Ogyusten Lui, 1789-1857) –fransuz matematigi. 7 n s s s n n x C x 0 (1 ) , m t t t m m x C x 0 (1 ) , n m p p p n m n m x C x 0 (1 ) tengliklarga, bulardan esa n m n m x x x (1 ) (1 ) (1 ) bo‘lgani uchun n m p p p n m m t t t m n s s s n C x C x C x 0 0 0 tenglikka ega bo‘lamiz. Oxirgi tenglikning ikkala tomonidagi k x ( 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) ) nafar talaba tanlash zarur bo‘lsin. n m nafar talabalardan k nafar talabani k Cnm xil usul bilan tanlash mumkinligi ravshan. Boshqa tomondan olib qaraganda, n m nafar talabalardan iborat to‘plamdan tanlanadigan 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 bola bo‘lgan k elementli qism to‘plamni oldin s Cn xil usul bilan tanlab, keyin (k s) nafar qiz bolalarni k s Cm 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, k s m s CnC songa tengdir. Noldan k gacha bo‘lgan barcha butun s sonlar uchun barcha 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.
|
| |