Diskret tuzilmalar fanidan tayyorlagan iv-mustaqil ish

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI QARSHI FILIALI

“ TT va KT ” FAKULTETI II - BOSQICH

AX-12-20 GURUH TALABASINING
DISKRET TUZILMALAR
FANIDAN TAYYORLAGAN
IV-MUSTAQIL ISH

Mavzu: Nyuton binomi. Binomial koeffietsientlarning hossalari. Hosil qiluvchi funktsiyalar va ularning kombinatorika masalalarini yechishga tatbiqi.
Bajardi: Murodullayev.J.
Qabul qildi: Hayitov.B.
QARSHI – 2021
MAVZU: Nyuton binomi. Binomial koeffietsientlarning hossalari. Hosil qiluvchi funktsiyalar va ularning kombinatorika masalalarini yechishga tatbiqi.


Kom binatorika haqida umumiy tushunchalar
Kombinatorika predmefi va paydo ho‘lish tarixi. Matematikaning kombinatorik tali I i 1. kombinatorik matematika, birlashmalar nazariyasi, qisqacha, kom binatorika deb ataluvchi bo'limida chekli yoki muayyan m a ’noda cheklilik shart ini qanoatlantiruvchi to'plamni (bu to 'p ­ lamning elementlari qanday bo'lishming aliamiyati yo'q: harflar, sonlar, hodisalar, qandaydir predmetlar va boshqalar) qismlarga ajratish, ulami o'rinlash va o'zaro joylash y a ’ni, komhinalsiyalar, kom binatorik tuzilm alar bilan bog'liq masalalar o'rganiladi. Hozirgi davrda kombinatorikaga oid m a’lumotlar inson laoliyalining turli sohalarida qo'llanilmoqda. Jumladan, matematika, kimyo. lizika, biologiya. lingvistika, axborot texnologiyalari va boshqa solialar bilan ish ko'ruvchi mutaxassislar kombinatorikaning xilma-xil masalalariga duch keladilar. To'plamlar nazariyasi iboralari bilan avtganda, kombinatorikada kortejlar va to'plamlar, ularning birlashmalari va kesishmalari hamda kortejlar va qism to'plamlarni turli usullar bilan tartiblash masalalari qaraladi. To'plam yoki kortej elementlarining berilgan xossaga ega konfiguratsiyasi bor yoki yo'qligini tekshirish, bor bo'lsa, ularni tuzish va sonini topish usullarini o'rgamsh hamda bu usullami biror parametr Bu so ‘z iotincha “combinatio" so'zidan yasalgan bo'lib, birikma. birlashma, tuzilma. tutashma ma'nolarini anglatadi. bo'yicha takomillashtirish kombinatorikaning asosiy masalalari hisoblanadi. Kombinatorikaning b a’zi elementlari eramizdan oldingi 11 asrda hindistonliklarga m a ’lum edi. Ular hozirgi vaqtda gruppalashlar deb ataluvchi kombinatorik tushunchadan foydaianishgan. Eramizning XII asrida Bxaskara A charya1 o'zining ilmiy tadqiqotlarida gruppalash va o'rin almashtirishlarni qo'Ilagan. Tarixiy m a’lumotlarga ko'ra, hindistoniik olimlar kombinatorika elementlaridan, jumladan, birlashmalardan foydalanib, she’riy asarlar tarkibiy tuzilishining mukammalligini tahlil qilishga uringanlar.
Masalalar: Figurali sonlar quyidagicha aniqianadi. Birinchi tartibli figurali sonlar: I, 2, 3. 4, 5, ... (ya’ni, natural sonlar); ikkinchi tartibli figurali sonlar: I-si Iga teng, 2-si dastlabki ikkita natural sonlar yig'indisi (3), 3-si dastlabki uchta natural sonlar yig'indisi (6) va hokazo (1. 3, 6, 10, 15, ...); uchincln larlibli llgurali sonlar: 1 -si lga teng, 2-si birinchi ikkita ikkinchi tartibii llgurali sonlarlar yig'indisi (4), 3-si birinchi uchta ikkinchi tartibii llgurali sonlar yig'indisi (10) va hokazo (1. 4, 10,20,35. ...). 1- m i s о 1. Tekislikda radiuslari o'zaro teng bo'lgan aylanalar bir-biriga uringan holda yuqoridan 1- qatorda bitta, 2- qatorda ikkita, 3- qatorda uchta va hokazo, joylashtirilgan bo'lsin. Masalan, aylanalar bunday joylashuvining dastlabki to'rt qatori 1- shaklda tasvirlangan. Bu yerda qatorlardagi aylanalar sonlari ketma-ketligi birinchi tartibli figurali sonlami tashkil qiladi. Bu tuzilmadan foydalanib ikkinchi tartibli figurali sonlami quyidagicha hosil qilish mumkin. Dastlab 1- qatordagi aylanalar soni (1), keyin dastlabki ikkita qatordagi aylanalar soni (3), undan keyin dastlabki uchta qatordagi aylanalar soni (6), va hokazo. Ш
“Kombinatorika” iborasi G. Leybnisning1 "Kombinatorik san’at haqidagi mulohazalar" nomli asarida birinchi bor 1665- yilda keltirilgan. Bu asarda birlashmalar nazariyasi ilmiy jihatdan ilk bor asoslangan. O'rinlashtirishlarni o'rganish bilan birinchi bo'lib Yakob Bernulli shug'ullangan va bu haqdagi ma'lumotlarni 1713- yilda bosilib chiqqan “Ars conjectandi" (Bashorat qilish san'ati) nomli kitobining ikkinchi qismida bayon qilgan. Hozirgi vaqtda kombinatorikada qo'llanilayotgan belgilashlar XIX asrga kelib shakllandi. Kombinatsiva - bu kombinatorikaning GotfHJ Levbnis asosiy tushunchasidir. Bu tushuncha yordamida ixtiyoriy to'plamning qandaydir sondagi elementlaridan tashkil topgan tuzilmalar ifodalanadi. Kombinatorikada bunday tuzilmalaming o'rin alm ashtirishlar. o'rinlashtirishlar va gruppalashlar deb ataluvchi asosiy ko'rinishlari o'rganiladi. 2.1.2. Kom binatorikada k o p qo'llaniladigan usul va qoirialar. Kombinatorika va graflar nazariyasida tasdiqlarni isbotlashning samarali usullaridan biri bo'lgan m atem atik induksiya usuli1 ko'p qo'llaniladi. Bu usulning ketma-ket bajariladigan ikkita qismi bo'lib, ular quyidagi umumiy g ‘oyaga asoslanadi. Faraz qilaylik, isbotlanishi kerak bo'lgan tasdiq birorta xususiy n = » i( qiymat (masalan, n0 = 1) uchun to ‘g ‘ri b o‘lsin (usulning bu qismi baza yoki asos deb ataladi). Agar bu tasdiqning istalgan n = к > na uchun to ‘g ‘riligidan uning n = k + \ uchun to'g'riligi kelib chiqsa, u holda tasdiq istalgan natural n > n{] son uchun to'g'ri bo'ladi (induksion o'tish yoki induktiv o'tish).
. Asosiy kombinatsiyalar
0 ‘rin alm ashtirishlar. Elementlari ах,а г,а %,...,а п bo'lgan to'plamni qaraymiz. Bu to'plam elementlarini har xil tartibda joylashtirib (yozib). tuzilmalar (kombinatsiyalar) hosil qilish mumkin, masalan, ux , a2, a}..... an ; a: . a ]. a ....... an : a 2, a , , a , .......an. Bu tuzilmalarning har birida berilgan to'plamning barcha elementlari ishtirok etgan holda ular bir-biridan faqat elementlarining joylashish o ‘rmlari bilan farq qiladilar. 1- t a ’rif. Shu usul yordamida hosil qilingan kombinatsiya laming har biri berilgan {a^a^ ,a .,...7an} to'plam elementlarining o'rin almashtirishi deb ataladi. Aslida “o'rin almashtirish” iborasi to'plam elementlarining o'rinlarini o'zgartirish harakatini anglatsada, bu yerda uni shu harakat natijasida hosil bo'lgan tuzilma sifatida qo'llaymiz. Bu iboradan uning asl m a ’nosida ham foydalanamiz. O'rin almashtirishni ifodalashda uning elementlarini ajratuvchi belgi sifatida yuqorida “,” (vergul) belgisidan foydalanildi. Ammo bu muhim emas, bu yerda boshqa belgidan ham foydalanish, hattoki, yozuvning ixchamligi maqsadida, elementlar orasidagi ajratuvchi belgilarni tushirib qoldirish ham mumkin. Bu eslatma bundan keyin bayon etiladigan boshqa kombinatorik tuzilmalar uchun ham o'rinlidir. Mustaqil ishlash uchun savollar S8 To'plam tushunchasiga asoslanib. bu yerda qaralayotgan o'rin almashtirishlar tarkibida elementlaming takrorlanmasligini eslatib o'tamiz. Shu sababli bunday o'rin almashtirishlarni betakror (takrorli emas) o'rin alm ashtirishlar deb ham atash mumkin. Ushbu bobning 4- paragrafida takrorli o'rin almashtirishlar ko'riladi. Berilgan n ta elementli to'plam uchun barcha o'rin almashtirishlar sonini Pn bilan belgilash qabul qilingan1. Bitta elementli {a} to'plam uchun faqat bitta a ko'rinishdagi o'rin almashtirish borligi ravshandir: Ikkita elementli {a,b} to'plam elementlaridan o'rin almashtirishlarni bitta elementli {a} to'plam uchun a o'rin almashtirishidan foydalanib quyidagicha tashkil qilamiz: b element a elementdan keyin yozilsa, ab o'rin almashtirishga, oldin yozilsa esa ba o'rin almashtirishga ega bo'lamiz. Demak, ko'paytirish qoidasiga (ushbu bobning 1- paragrafiga qarang) binoan ikkita o'rin almashtirish bor: !\ = 2 = 1-2. Uchta elementli {a ,b ,c } to'plam uchun o'rin almashtirishlar tashkil qilishda ikkita elementli {a,b} to'plam uchun tuzilgan ab va ha o'rin almashtirishlardan foydalanish mumkin. Berilgan to'plamning с elementini ah va ba o'rin alinashlirishning har biriga uch xil usul bilan joylashtirish mumkin: ularning elementlaridan keyin, elcmentlarining orasiga va elementlaridan oldin. Ko'paytirish qoidasini qo'llasak, uchta elementli \a ,b ,c\ to'plam uchun oltita ( P, = 6 = 1 • 2 3 ) har xil o'rin almashtirishlar hosil bo'lishini aniqlaymiz. Ular quyidagilardir: abc. ach, cab, hac. bca, cb a.