logo
  1. Главная страница
  2. Дипломные работы
  3. Общий
  4. Kombinatorika KURS ISHI

Kombinatorika KURS ISHI

Загружено в:

23.11.2024

Скачано:

0

Размер:

942.5 KB
Скачать
Kirish Mavzuning dolzarbligi, Ehtimollar nazariyasi va matematik statistika – bir-birga uzviy bog’liq matematik fanlar hisoblanadi. Hozirgi paytda bu sohalar bo’yicha olingan bilimlar turli kasb mutaxassislariga juda ham ham zurur. O’z faoliyatini maqsadini aniqlay olish va unga erishish uchun shaxdam qadamlar qo’yish – kompetentli, raqobatbardosh qobiliyatli mutaxassisning xarakterli xususiyati, ehtimollar nazariyasi va matematik statistika esa har qanday fanga qaraganda ko’proq shaxsning ijobiy o’zgarishlari uchun yordam beradi. Ommaviy tasodifiy jarayonlar qonuniyatlarini (ehtimollar nazariyasi fani) va kuzatishlar natijalarini qayta ishlash muhim usul va yo’llarini (matematik statistika o’rganadigan) bilish har bir kasbdagi mutaxassis uchun amaliy masalalarni yechishda qo’l keladi. Ehtimollar nazariyasi va matematik statistikani o’rganishni esa avvalo kombinatorika asoslari bilan tanishmasdan mumkin bo’lmaydi. «Kombinatorika» atamasi matematikaga Leybnits tomonidan kiritilgan bo’lib, uni 1666 yilda chop etilgan «Kombinatorika san’ati to’g’risida mulohazalar» nomli kitobida birinchi marta qo’llagan edi. Kombinatorik masalalar nafaqat matematika go’zalligini ko’rsatishga, balki amaliy matematik masalarni yechishda yangi kompyuter texnoogiyalarining imkoniyatlarini ko’rsatishga imkon beradi. Diskret matematikaning masalalaridan hisoblangan kombinatorik masalalar ko’pincha ob’ektlarning turli kombinatorik konfiguratsiyalarini tanlashga va ular orasidan u yoki bu masala shartigav nuqtai nazaridan eng yaxshisini tanlashga olib kelinadi. Shuning uchun keng tarqalgan kombinatorik konfiguratsiyalarni hosil qilish algoritmlarini bilish masalani butunlay muvaffaqiyatli yechishning zarur sharti hisoblanadi. Ushbu kurs ishida matematika o’qitishda kombinatorika elementlarini o’rganish samaradorligini oshirish maqsadida kombinatorika fanining asosiy 5 tushunchalari, kombinatorikani o’rganish xususiyatlari, o’qitish jarayonida kombinatorika elementlarini o’rgatish bilan birga o’quvchilarning ijodiy faolligini oshirish bo’yicha uslubiy tavsiyalar bayon etilgan. Reja: 1. Kombinatorika haqida umumiy tushuncha. 2. Bo’laklash kombinatorikasi. 3. Ferrers diagrammasi. 4. Bo’lakashlarning xossalari. Kombinatorika asoslari Kombinatorik masalalar va tartiblangan to’plamlar. Kombinatorika predmeti va paydo bo’lish tarixi. Matematikaning kombinatorik tahlil, kombinatorik matematika, birlashmalar nazariyasi, qisqacha, kombinatorika deb ataluvchi bo’limida chekli yoki muayyan ma’noda cheklilik shartini qanoatlantiruvchi to’plamni (bu to’plamning elementlari qanday bo’lishining ahamiyati yo’q: harflar, sonlar, hodisalar, qandaydir predmetlar va boshqalar) qismlarga ajratish, ularni o’rinlash va o’zaro joylash ya’ni, kombinatsiyalar, kombinatorik tuzilmalar bilan bog’liq masalalar o’rganiladi. Hozirgi davrda kombinatorikaga oid ma’lumotlar inson faoliyatining turli sohalarida qo’llanilmoqda. Jumladan, matematika, kimyo, fizika, biologiya, lingvistika, axborot texnologiyalari va boshqa sohalar bilan ish ko’ruvchi mutaxassislar kombinatorikaning xilma-xil masalalariga duch keladilar. To’plamlar nazariyasi iboralari bilan aytganda, 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’rganish hamda 7 bu usullarni biror parametr bo’yicha takomillashtirish kombinatorikaning asosiy masalalari hisoblanadi. Kombinatorikaning ba’zi elementlari eramizdan oldingi II asrda hindistonliklarga ma’lum edi. Ular hozirgi vaqtda gruppalashlar deb ataluvchi kombinatorik tushunchadan foydalanishgan. Eramizning XII asrida Bxaskara Acharya o’zining ilmiy tadqiqotlarida gruppalash va o’rin almashtirishlarni qo’llagan. Tarixiy ma’lumotlarga ko’ra, hindistonlik olimlar kombinatorika elementlaridan, jumladan, birlashmalardan foydalanib, she’riy asarlar tarkibiy tuzilishining mukammalligini tahlil qilishga uringanlar. Umuman olganda, kombinatorikaning dastlabki rivoji qimor o’yinlarini tahlil qilish bilan bog’liq. Ba’zi atoqli matematiklar, masalan, fransuz matematigi B.Paskal (1623- 1662), sveytasriyalik matematik Ya.Bernulli (1654- 1705), L.Eyler (1707-1783), rus matematigi P.L.Chebishev (1821-1894) turli o’yinlarda (tanga tashlash, soqqa tashlash, qarta o’yinlari va shu kabilarda) ilmiy jihatdan asoslangan qarorlar qabul qilishda kombinatorikani qo’llashgan. XVII asrda kombinatorika matematikaning alohida bir ilmiy yo’nalishi sifatida shakllana boshladi. Blez Paskal o’zining “Arifmetik uchburchak haqida traktat” va “Sonli tartiblar haqida traktat” (1665 y.) nomli asarlarida hozirgi vaqtda binomial koeffitsientlar deb ataluvchi sonlar haqidagi ma’lumotlarni keltirgan. Fransuz matematigi P.Ferma (1601-1665) esa figurali sonlar bilan birlashmalar nazariyasi orasida bog’lanish borligini bilgan. Figurali sonlar quyidagicha aniqlanadi. Birinchi tartibli figurali sonlar: 1, 2, 3, 4, 5, … (ya’ni, natural sonlar); ikkinchi tartibli figurali sonlar: 1-si 1ga 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, …); uchinchi tartibli figurali sonlar: 1-si 1ga teng, 2-si birinchi ikkita ikkinchi tartibli figurali sonlarlar yig’indisi (4), 3-si birinchi uchta ikkinchi tartibli figurali sonlarlar yig’indisi (10) va hokazo (1, 4, 10, 20, 35, …); va hokazo. 1-misol. 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 sonlarni tashkil qiladi. Bu tuzilmadan foydalanib, ikkinchi tartibli figurali sonlarni 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 nemis matematigi G.Leybnis (1646- 1716) ning “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. Kombinatorik masalalar va ularni yechishda qo’llaniladigan qoidalar. Ko’plab kombinatorik masalalarni yechishda qo’shish va ko’paytirish qoidalari qo’l keladi: a) qo’shish qoidasi: agar X to’plam m elementli, Y to’plam esa n elementli bo’lsa va ular o’zaro kesishmasa, X UY to’plamning elementlari soni n  m ga teng, ya’ni agar X  Y   bo’lsa, n(X UY)  n(X)  n(Y) bo’ladi. Umuman ixtiyoriy ikki X va Y to’plamlar uchun n(X UY)  n(X)  n(Y)  n(X  Y) o’rinli bo’ladi. 2-misol. A shahardan B shaharga uchta yo’l, B dan C ga esa 2 ta yo’l olib boradi. A shahardan C shaharga necha xil usul bilan borish mumkin? Yechish. A dan B ga 1-, 2- va 3-yo’llar olib boradi. B shahardan C shaharga a va b yo’llar olib boradi. U holda A dan C ga qo’yiladigan usullar bilan borish mumkin: (1,a), (1,b), (2,a), (2,b), (3,a), (3,b). Buni boshqacha usul bilan ham hal qilsa bo’ladi. A va B gacha boradigan yo’llarki, tanlash usuli 3 ta, B dan C gacha boradigan yo’llarni tanlash usuli esa 2 ta. Bunda ko’paytma qoidasiga ko’ra, yo’llarning tartiblangan juftliklarini 3  2=6 usul bilan tanlash mumkinligi ko’rinib turibdi. Quyida kombinatorik masalalardan o’rin almashtirishlar, takrorlanmaydigan o’rin almashtirishlar, takrorlanmaydigan o’rinlashtirishlar va guruhlashlarni ko’rib chiqamiz. Takrorsiz o’rin almashtirishlar. Agar chekli X to’plamning elementlari qandaydir yo’l bilan raqamlangan bo’lsa, uni tartiblangan to’plam deymiz: { , ,..., }. 1 2 n X  . Kortej tushunchasidan farqli o’laroq tartiblangan to’plam elemetlari orasida o’zaro tenglari bo’lmaydi. Masalan, (2,3,2,4,5) kortej tartiblangan to’plam emas, (2,3,4,5) esa tartiblangan to’plam bo’ladi. Bitta to’plamni turlicha tartiblash mumkin. m elementli X to’plamni necha xil usul bilan tartiblash mumkin degan masalani qaraymiz. Har bir tartiblash quyidagicha amalga oshiriladi. To’plamning qaysi bir elementini 1-nomer bilan, qaysi birini 2-nomer bilan va hokazo qaysi bir elementini m nomer bilan belgilaymiz. Agar birinchi element tanlangan bo’lsa, ikkinchi elementni tanlash (m–1) ta elementning ichidan olinadi. Demak, birinchi element m usul bilan, ikkinchisi esa (m–1) usul bilan tanlanadi. Uchinchi element (m–2) usul bilan va hokazo oxirgi element m-o’rinni egallaydi. Masalan, {5,6,7} elementli to’plam quyidagicha tartiblanadi 567, 657, 756 – birinchi element 3 usul bilan olindi. 657, 756 – ikkinchi element 2 usul bilan tanlandi. Oxirgi tartiblash 765 bo’ladi. Umumiy holda ko’paytirish qoidasiga asosan tartiblash usulining umumiy soni =m (m-1)...1 m! ga teng bo’ladi. Bunday tartiblash m elementdan takrorlanmaydigan o’rin almashtirish deyiladi. Bunda har bir tartiblangan to’plamning elementlari turlicha bo’ladi. Takrorsiz o’rinlashtirishlar. Endi m elementli X to’plam elementlaridan nechta k elementli tartiblangan to’plamlar tuzish mumkin degan masalani qaraymiz. Bu masalaning yuqoridagi masaladan farqi shundaki, bu yerda k elementli tartiblangan to’plamni tuzish k ta elementni olish bilan tugallanadi. Bunday tartiblangan to’plamlarning sonini topish uchun k ta m, m–1, m–2, …, m–k+1 sonlarni ko’paytirish yetarli (chunki {m, m–1, m–2,…,m–k+1} to’plamda k ta element mavjud). Shunday qilib, X to’plamdagi k elementli tartiblangan to’plamlar soni  m(m  1)(m  2)...(m  k  1) n m ga teng bo’ladi. Bunday tartiblangan to’plamlarni m elementdan k tadan takrorlanmaydigan o’rinlashtirishlar deyiladi. ning ifodasini 1  2...(m  k) ga ko’paytirib va bo’lib, uning ko’rinishini o’zgartirish mumkin: Bunda   m! bo’ladi, bu yerda 0!=1 deb olinadi. Takrorsiz guruhlashlar. Endi biz kombinatorikaning quyidagi masalasini qaraymiz: m elementli X elementlaridan nechta har biri k elementli qism to’plamlar tuzish mumkin? Bunday qism to’plamlar m elementdan k tadan takrorlanmaydigan guruhlashlar deyiladi. Ularning soni bilan belgilanadi. Ko’rsatish mumkinki, bo’ladi. Bo’laklashlar ta’rifi. Kombinatorikada o’rin almashtirishlar, o’rinlashtirishlar va gruppalashlar tushunchalari yordamida yechiladigan masalalar bilan bir qatorda bo’laklashlar ga doir masalalar ham qaraladi. Bunday masalalar turli vaziyatlarda paydo bo’lishlari mumkin. Masalan, qutiga predmetlarni joylashda, axborotni uzatishda, pulni maydalashda, ko’phad formulasidan foydalanish uchun daraja ko’rsatkichini bo’laklashda va hokazo. Bo’laklashlarga doir masalalar orasida natural sonlarni natural yoki manfiymas butun qo’shiluvchilar yig’indisi sifatida tasvirlash masalasi alohida o’rin tutadi. Bu masalaning mohiyati quyidagidan iborat. Berilgan natural sonni natural s onlar yig’indisi ko’rinishda ifodalash imkoniyatlari qancha? Bu masala turli shartlarda qaralishi mumkin. Masalan: - qo’shiluvchilar tartibi e’tiborga olinishi yoki olinmasligi mumkin; - bo’laklashlarda faqat juft yoki toq sondagi qo’shiluvchilar qatnashish sharti qo’yilishi mumkin; - qo’shiluvchilar bir-biridan farqli yoki ixtiyoriy deb hisoblanishi mumkin va hokazo. Tabiiyki, bo’laklashlarga doir kombinatorik masalalarni yechishda, bo’laklanayotgan son o’rniga undan kichikroq son(lar)ni bo’laklash yoki qaralayotgan bo’laklashni kamroq sondagi qo’shiluvchilari bo’lgan bo’laklashga keltirish usuli qo’llanilishi maqsadga muvofiqdir. Natural sonni ixtiyoriy ta ( – natural son, ) natural sonlar yig’indisi, ya’ni ko’rinishda tasvirlashga sonni ta qo’shiluvchilarga bo’laklash (qisqacha, bo’laklash ) deb ataladi. Yuqorida ta’kidlaganimizdek, bo’laklash masalasini ikki vaziyatda, ya’ni qo’shiluvchilar tartibi e’tiborga olingan yoki olinmagan hollarda qarash mumkin. Kombinatorik nuqtai nazardan olganda ikkala hol ham qiziqarlidir. Bo’laklash masalasini, avvalo, qo’shiluvchilar tartibi e’tiborga olingan holda qaraymiz. Bu holda natural sonning ta qo’shiluvchilarga bo’laklanishlari sonini bilan va shu sonning barcha bo’laklanishlari sonini bilan belgilasak, ravshanki, tenglik o’rinli bo’ladi. 1- m i s o l . Faqat bir yo’nalishda harakatlanganda besh pog’onali zinapoyani hatlab o’tish imkoniyatlari sonini aniqlash talab etilgan bo’lsin. Tabiiyki, har bir qadamda faqat bittadan pog’onani bosib o’tib, zinapoyani 5 qadamda hatlab o’tish mumkin. Bu harakatni 5 sonning ko’rinishda bo’laklanishi kabi ifodalab, ekanligini qayd etamiz. Zinapoyani 4 qadamda ham hatlab o’tish mumkin, bu ishning imkoniyati bor: , , va . Shu usulda davom etib, 3 qadam uchun ta – , , , , , hamda 2 qadam uchun ta – , , , tengliklarni yozamiz. Endi barcha pog’onalarni bir qadamda hatlab o’tishga imkoniyat va tenglik mos kelishini e’tiborga olsak, mumkin bo’lgan barcha imkoniyatlarni bayon qilgan bo’lamiz. Shunday qilib, faqat bir yo’nalishda harakatlanganda besh pog’onali zinapoyani hatlab o’tish imkoniyatlari soni bo’ladi. ■ Endi va miqdorlarni hisoblash formulalarini topish bilan shug’ullanamiz. Dastlab bolgan holni qaraymiz. Tabiiyki, birni natural sonlar yig’indisi qilib bo’laklash haqida gap bo’lishi mumkin emas. Shunday bo’lishiga qaramasdan, birni faqat bitta qo’shiluvchidan iborat deb qarab, yuqorida berilgan ta’rifga mos keluvchi ta bo’laklashga ega bo’lamiz. Jami bo’laklashlar soni bo’ladi 1 . bo’lgan holda qo’shiluvchili ta ( ) va qo’shiluvchili ta ( ) bo’laklashlarga ega bo’lamiz. Bu hol uchun jami bo’laklashlar soni . Agar bo’lsa, u holda qo’shiluvchili ta ( ), qo’shiluvchili ta ( ) va 1 . qo’shiluvchili ta ( ) bo’laklashlar bor. Bu holda jami bo’laklashlar soni uchun tenglik o’rinlidir. Shunday davom etib, “istalgan natural sonning ta qo’shiluvchilarga bo’laklanishlari soni ( ) ta elementdan ( ) talab gruppalashlar soniga teng, ya’ni ” degan farazga kelish mumkin. Agar bu faraz tasdiqlansa , binomial koeffitsientlarning yig’indisi haqidagi xossasiga ko’ra, bo’ladi. 1- t e o r e m a . Qo’shiluvchilar tartibini e’tiborga olgan holda istalgan natural sonning ta qo’shiluvchilarga bo’laklanishlari soni ( ) ta elementdan ( ) talab gruppalashlar soniga teng, ya’ni . I s b o t i o’quvchiga havola qilinadi. Yuqorida bayon etilgan mulohazalar yordamida va 1- teoremaga tayangan holda isbotlash osonligini ta’kidlab, quyidagi teoremani boshqa usul bilan isbotlaymiz. 2- t e o r e m a . Qo’shiluvchilar tartibini e’tiborga olgan holda ixtiyoriy natural sonning barcha bo’laklanishlari soni ga teng, ya’ni . I s b o t i . Natural sonning barcha bo’laklanishlari to’plamini deb, shu sonning birinchi qo’shiluvchisi ga ( ) teng bo’lgan bo’laklanishlari to’plamini esa bilan belgilaymiz. Tushunarliki, bo’ladi. Agar to’plam elementlari sonini deb belgilasak, yuqoridagi tenglikka asosan bo’ladi. Endi ( ) va tengliklarni hisobga olib, tenglikka ega bo’lamiz. Bu tenglik ixtiyoriy natural son uchun to’g’ri. Shuning uchun, bu tenglikdagi ni ( )ga almashtirib, , ya’ni ( ) ko’rinishdagi rekurrent munosabatni hosil qilamiz. Bu rekurrent munosabat ketma-ket qo’llanilsa, kelib chiqadi. ■ 2- m i s o l . To’qqiz qavatli binoning birinchi qavatidan sakkiz kishi liftda yuqoriga ko’tarilayotgan bo’lsin. Agar to’qqizinchi qavatga liftdagi kishilarning faqat bittasi chiqishi shart bo’lsa, lift yo’lovchilarining bino qavatlariga chiqish imkoniyatlari sonini aniqlang. Masalaning shartiga binoan, liftdagi sakkiz kishidan faqat bir kishi to’qqizinchi qavatga chiqishi shart bo’lgani uchun, qolgan yetti kishining ikkinchi qavatdan sakkizinchi qavatgacha chiqishining ko’p imkoniyatlari bor. Bu imkoniyatlar soni liftning birinchi va to’qqizinchi qavatlar orasidagi to’xtashlar sonidan bog’liq bo’lib, yettining barcha bo’laklanishlari yordamida ifodalanishi mumkin. Masalan, lift binoning ikkinchi qavatidan sakkizinchi qavatigacha faqat bir marta to’xtab, liftdagi yetti kishi tushib qolgan bo’lsa, u holda bu hodisa ko’rinishdagi bo’laklash vositasida ifodalanadi; agar to’qqizinchi qavatgacha lift ikki marta to’xtab, oldin uch kishi, keyin to’rt kishi tushib qolgan bo’lsa, bu holatga ko’rinishdagi bo’laklash mos keladi va hokazo. 2- teoremadan foydalanib, yettining barcha bo’laklanishlari soni ekanligini topamiz. Demak, agar to’qqizinchi qavatga faqat bir kishi chiqishi shart bo’lsa, u holda lift yo’lovchilarining bino qavatlariga chiqish imkoniyatlari soni 64ga tengdir. Agar hal qilingan masalada to’qqizinchi qavatga faqat bir kishining chiqishi sharti bo’lmasa edi, u holda sakkizning barcha bo’laklanishlari sonini topishga to’g’ri kelar edi. ■ Endi natural sonlarni qo’shiluvchilar tartibi e’tiborga olinmagan vaziyatda bo’laklash masalasi bilan shug’ullanamiz. Odatda, natural sonning ixtiyoriy ta ( – natural son, ) qo’shiluvchilarga bo’laklanishini qandaydir shartlarga, masalan, yoki tengsizliklarga bo’ysunadigan qilib olish qulay bo’ladi. Qo’shiluvchilar tartibi e’tiborga olinmagan holda natural sonning ta qo’shiluvchilarga bo’laklanishlari sonini bilan, uning barcha bo’laklanishlari sonini esa bilan belgilaymiz. Bundan keyin, bo’laklash deganda qo’shiluvchilar tartibi e’tiborga olinmagan holdagi bo’laklashni nazarda tutamiz. Tabiiyki, quyidagi tenglik o’rinlidir: . Osonlik bilan ko’rish mumkinki, , , , , , , . 3- m i s o l . 8 uchun barcha bo’laklashlar 1- jadvalda ifodalangan. Jadvaldan ko’rinib turibdiki, 8 uchun, hammasi bo’lib, 22 bo’laklash imkoniyati bor: . Albatta, yuqorida keltirilgan formula yordamida ixtiyory natural uchun uning barcha bo’laklanishlari sonini aniqlash mumkin. Lekin yetarlicha katta qiymatga ega bo’lganda bu formuladan foydalanish juda ko’p hisoblashlar bajarishni taqozo qiladi. 11- ma’ruzada ning qiymatini hisoblash uchun boshqacha yo’l borligi ko’rsatilgan. 1- jadval Qo’ shi- luvchilar soni Bo’laklanishlar Bo’lakla nishlar soni 1 8=8 2 8=7+1=6+2=5+3=4+4 3 8=6+1+1=5+2+1=4+3+1=4+2+2=3+3+2 4 8=5+1+1+1=4+2+1+1=3+3+1+1=3+2+2+1 =2+2+2+2 5 8=4+1+1+1+1=3+2+1+1+1=2+2+2+1+1 6 8=3+1+1+1+1+1=2+2+1+1+1+1 7 8=2+1+1+1+1+1+1 8 8=1+1+1+1+1+1+1+1 Ferrers 2 diagrammasi. Natural sonni ta natural qo’shiluvchilarnung yig’indisi qilib bo’laklashga mos Ferrers diagrammasi ta qatordan tashkil topgan bo’lib, uning (yuqoridan nastga qarab hisoblaganda) - qatorida ta nuqta mavjud bo’ladi. Ferrers diagrammasi tushunchasiga asoslangan diagrammali usul deb ataluvchi usul sonlarni qo’shiluvchilar yig’indisi qilib bo’laklash masalalarini tahlil qilishda keng qo’llaniladi. Bo’laklashda qo’shiluvchilar tartibi e’tiborga olinmaganligi sababli Ferrers diagrammasini tuzishda, odatda, uning qatorlaridagi nuqtalar soni yuqoridan pastga qarab o’shmaydigan, ya’ni shart bajariladigan (yoki, kamaymaydigan ya’ni shart bajariladigan ) tartibga rioya qilinadi. Bundan tashqari, qatorlardagi nuqtalar diagrammaning vertikal ustunlarini tashkil etadigan qilib tuziladi. Shunday tartibda tuzilgan diagramma normal Ferrers diagrammasi deb ataladi. 4- m i s o l . 14=5+3+2+2+1+1 bo’laklashga 1- shaklda tasvirlangan Ferrers diagrammasi mos keladi. Bu diagramma normal Ferrers diagrammasidir. ■ Ixtiyoriy bo’laklashga mos keluvchi normal Ferrers diagrammasining qatorlarini ustun, ustunlarini esa qator qilib o’zgartirilsa (ya’ni diagramma trasponirlansa), tabiiyki, yana normal Ferrers diagrammasi hosil bo’ladi. Bu hosil bo’lgan diagrammaga 2 Ferrers (Norman Makleod, 1829 – taxminan 1894 yildan so‘ng vafot etgan) – ingliyz matematigi. 1- shakl 2 - shakl 2- расмdastlabki diagrammaning transpozitsiyasi (yoki ikkilanma diagrammasi) deb ataladi. Normal Ferrers diagrammasining transpozitsiyasi natijasida hosil bo’lgan ikkilanma diagramma transponirlansa dastlabki diagramma hosil bo’lisi ravshandir. Demak, istalgan son uchun tuzilgan barcha diagrammalarni o’zaro ikkilanma bo’lgan diagrammalar juftlariga ajratish mumkin. Shuni e’tiborga olish kerakki, ba’zi diagrammalar o’z-o’ziga ikkilanma bo’ladi, shuning uchun ular ikkita bir xil diagrammalar juftini tashkil etadi deb hisoblash mumkin. Ikkilanma diagrammalarni qo’shma diagrammalar deb, ularga mos keluvchi bo’laklashlarni esa qo’shma bo’laklashlar deb ham ataydilar. 5- m i s o l . 4- misolda qaralgan 14=5+3+2+2+1+1 bo’laklashga mos Ferrers diagrammasiga qo’shma diagrammani 2- shakldagidek tasvirlash mumkin. Mos qo’shma bo’laklash esa: 14=6+4+2+1+1. ■ Bo’laklashlarning xossalari. Quyidagi uchta 3–5- teoremalar bo’laklashlarning ba’zi xossalarini ifodalaydi. 3- t e o r e m a . Ixtiyoriy natural sonning har xil natural qo’shiluvchilarga bo’laklanishlari soni shu sonning toq qo’shiluvchlarga bo’laklanishlari soniga teng. I s b o t i . natural sonning toq qo’shiluvchilarga bo’laklanishlaridan ixtiyoriy birini qaraymiz: , bu yerda har bir ( ) qo’shiluvchi bo’laklanishda ( ) marta qatnashadi. sonning ikkilik sanoq sistemasidagi tasvirlanishini yozamiz, bunda qandaydir ( ta) butun sonlar . Qaralayotgan sonning yuqoridagi bo’laklanishida ta qo’shiluvchilarni bir-biridan farqli qo’shiluvchilarga almashtiramiz. Tabiiyki, bunday almashtirish ta qo’shiluvchilar yig’indisining qiymatini o’zgartirmaydi. Shu jarayonni barcha qiymatlar uchun takrorlab va qo’shiluvchilarning mos qiymatlarini yozib, sonning har xil qo’shiluvchilarga bo’laklanishlaridan birini hosil qilamiz, chunki , sonlarning toqligi tufayli bo’ladi. Shunday qilib, sonning toq qo’shiluvchilarga bo’laklanishlaridan har biriga shu sonning har xil qo’shiluvchilarga bo’laklanishlaridan biri mos kelishi isbotlandi. Bu tasdiqning teskarisini ham isbotlash mumkin. ■ 6- m i s o l . 3- misolda 8ning barcha bo’laklashlari keltirilgan va bu bo’laklashlar soni 22ga tengligi ko’rsatilgan edi. 22ta bo’laklashlardan oltitasi har xil qo’shiluvchilardan tuzilgan. Xuddi shuncha toq qo’shiluvchili bo’laklashlar mavjud. 3- teoremaning isbotidagidek mulohaza yuritib 8ning har xil qo’shiluvchili va toq qo’shiluvchili barcha bo’laklanishlari orasidagi bir qiymatli moslikni ko’rsatish mumkin. Haqiqatdan ham, , , , . ■ Diagrammali usul yordamida bo’laklashlarning turli xossalarini osonlik bilan isbotlash mumkin. Quyida shunday xossalardan ikkitasini ifodalovchi 4- va 5- teoremalarni keltiramiz. 4- t e o r e m a . Ixtiyoriy natural sonni ta natural qo’shiluvchilarga bo’laklashlar soni shu sonning eng katta qo’shiluvchisi ga teng bo’lgan bo’laklanishlari soniga teng. I s b o t i . Ferrers diagrammasining transpozitsiyasi tushunchasi yordamida natural sonning ta natural qo’shiluvchilarga bo’laklanishlari va shu sonining eng katta qo’shiluvchisi ga teng bo’lgan bo’laklanishlari orasida bir qiymatli moslik o’rnatish mumkin. Bu bir qiymatli moslikka ko’ra teoremaning nasdig’i to’g’ridir. ■ 7- m i s o l . 3- misoldan ma’lumki, 8 uchun uchta qo’shiluvchili beshta bo’laklash mavjud, bu son uchun qo’shiluvchilarning eng kattasi uchga teng bo’lgan bo’laklashlar ham beshtadir. 2- jadvalda bu bo’laklashlar bir-biriga mos ravishda ikki ustun qilib keltirilgan. 5- t e o r e m a . Ixtiyoriy natural sonning hech bir qo’shiluvchisi dan oshmaydigan bo’laklanishlari soni ( ) sonining ta qo’shiluvchilarga bo’laklanishlar soniga teng. 2- jadval 8 sonining 3ta qo‘shiluvchili bo‘laklanishlari 8 sonining eng katta qo‘shiluvchisi 3ga teng bo‘laklanishlari 6+1+1 3+1+1+1+1+1 5+2+1 3+2+1+1+1 4+3+1 3+2+2+1 4+2+2 3+3+1+1 3+3+2 3+3+2 I s b o t i . Birinchidan, shuni ta’kidlash lozimki, Ferrers diagrammasining transpozitsiyasi sonning hech bir qo’shiluvchisi dan oshmaydigan bo’laklanishlari bilan shu sonning tadan oshmaydigan qo’shiluvchilarga bo’laklanishlari orasida o’zaro bir qiymatli moslik o’rnatadi. Bu bir qiymatli moslik asosida sonning hech bir qo’shiluvchisi dan oshmaydigan barcha bo’laklanishlari soni shu sonning tadan oshmaydigan qo’shiluvchilarga bo’laklanishlari soniga teng deb xulosa qilish mumkin. Ikkinchi tomondan, sonning tadan oshmaydigan qo’shiluvchilarga bo’laklanishiga mos Ferrers diagrammasi ta nuqtadan tashkil topgan bo’lib, ular tadan oshmaydigan qatorlarda joylashgan bo’ladi. Bunday diagrammalarning har biriga ta nuqtadan tuzilgan ustunni chap tomondan joylashtirsak, ta qatorga va ( )ta nuqtali diagrammaga ega bo’lamiz. Aksincha, ( )ta nuqtali har bir Ferrers diagrammasidan ta qatorga ega birinchi ustunni olib tashlasak, ta nuqtadan tashkil topgan va qatorlari soni tadan ko’p bo’lmagan diagrammani hosil qilamiz. Ko’rsatilgan bu ikki turdagi diagrammalar orasidagi o’zaro bir qiymatli moslik sonni qo’shiluvchilari tadan oshmaydigan bo’laklashlar soni ifodaga tengligini tasdiqlaydi. Xulosa Xulosa qilib shuni aytish mumkinki, Kombinatorik masalalar nafaqat matematika go’zalligini ko’rsatishga, balki amaliy matematik masalarni yechishda yangi kompyuter texnoogiyalarining imkoniyatlarini ko’rsatishga imkon beradi. Diskret matematikaning masalalaridan hisoblangan kombinatorik masalalar ko’pincha ob’ektlarning turli kombinatorik konfiguratsiyalarini tanlashga va ular orasidan u yoki bu masala shartigav nuqtai nazaridan eng yaxshisini tanlashga olib kelinadi. Shuning uchun keng tarqalgan kombinatorik konfiguratsiyalarni hosil qilish algoritmlarini bilish masalani butunlay muvaffaqiyatli yechishning zarur sharti hisoblanadi. Foydalanilgan adabiyotlar va elektron saytlar: 1. Kombinatorika elementlari (uslubiy qo’llanma) Samarqand-2020 Xalikulov S.I., Quljonov O’., Ostonov Q. Kombinatorika elemementlari. Uslubiy qo’llanma. - Samarqand: SamDU nashri, 2020. - 78 bet 2. https://uz.wikipediya.org sayti Kombinatorika haqida 3. https://fayllar.org sayti Bo’laklashlar kombinatorikasi

Kirish Mavzuning dolzarbligi, Ehtimollar nazariyasi va matematik statistika – bir-birga uzviy bog’liq matematik fanlar hisoblanadi. Hozirgi paytda bu sohalar bo’yicha olingan bilimlar turli kasb mutaxassislariga juda ham ham zurur. O’z faoliyatini maqsadini aniqlay olish va unga erishish uchun shaxdam qadamlar qo’yish – kompetentli, raqobatbardosh qobiliyatli mutaxassisning xarakterli xususiyati, ehtimollar nazariyasi va matematik statistika esa har qanday fanga qaraganda ko’proq shaxsning ijobiy o’zgarishlari uchun yordam beradi. Ommaviy tasodifiy jarayonlar qonuniyatlarini (ehtimollar nazariyasi fani) va kuzatishlar natijalarini qayta ishlash muhim usul va yo’llarini (matematik statistika o’rganadigan) bilish har bir kasbdagi mutaxassis uchun amaliy masalalarni yechishda qo’l keladi. Ehtimollar nazariyasi va matematik statistikani o’rganishni esa avvalo kombinatorika asoslari bilan tanishmasdan mumkin bo’lmaydi. «Kombinatorika» atamasi matematikaga Leybnits tomonidan kiritilgan bo’lib, uni 1666 yilda chop etilgan «Kombinatorika san’ati to’g’risida mulohazalar» nomli kitobida birinchi marta qo’llagan edi. Kombinatorik masalalar nafaqat matematika go’zalligini ko’rsatishga, balki amaliy matematik masalarni yechishda yangi kompyuter texnoogiyalarining imkoniyatlarini ko’rsatishga imkon beradi. Diskret matematikaning masalalaridan hisoblangan kombinatorik masalalar ko’pincha ob’ektlarning turli kombinatorik konfiguratsiyalarini tanlashga va ular orasidan u yoki bu masala shartigav nuqtai nazaridan eng yaxshisini tanlashga olib kelinadi. Shuning uchun keng tarqalgan kombinatorik konfiguratsiyalarni hosil qilish algoritmlarini bilish masalani butunlay muvaffaqiyatli yechishning zarur sharti hisoblanadi. Ushbu kurs ishida matematika o’qitishda kombinatorika elementlarini o’rganish samaradorligini oshirish maqsadida kombinatorika fanining asosiy 5 tushunchalari, kombinatorikani o’rganish xususiyatlari, o’qitish jarayonida kombinatorika elementlarini o’rgatish bilan birga o’quvchilarning ijodiy faolligini oshirish bo’yicha uslubiy tavsiyalar bayon etilgan.

Reja: 1. Kombinatorika haqida umumiy tushuncha. 2. Bo’laklash kombinatorikasi. 3. Ferrers diagrammasi. 4. Bo’lakashlarning xossalari.

Kombinatorika asoslari Kombinatorik masalalar va tartiblangan to’plamlar. Kombinatorika predmeti va paydo bo’lish tarixi. Matematikaning kombinatorik tahlil, kombinatorik matematika, birlashmalar nazariyasi, qisqacha, kombinatorika deb ataluvchi bo’limida chekli yoki muayyan ma’noda cheklilik shartini qanoatlantiruvchi to’plamni (bu to’plamning elementlari qanday bo’lishining ahamiyati yo’q: harflar, sonlar, hodisalar, qandaydir predmetlar va boshqalar) qismlarga ajratish, ularni o’rinlash va o’zaro joylash ya’ni, kombinatsiyalar, kombinatorik tuzilmalar bilan bog’liq masalalar o’rganiladi. Hozirgi davrda kombinatorikaga oid ma’lumotlar inson faoliyatining turli sohalarida qo’llanilmoqda. Jumladan, matematika, kimyo, fizika, biologiya, lingvistika, axborot texnologiyalari va boshqa sohalar bilan ish ko’ruvchi mutaxassislar kombinatorikaning xilma-xil masalalariga duch keladilar. To’plamlar nazariyasi iboralari bilan aytganda, 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’rganish hamda 7 bu usullarni biror parametr bo’yicha takomillashtirish kombinatorikaning asosiy masalalari hisoblanadi. Kombinatorikaning ba’zi elementlari eramizdan oldingi II asrda hindistonliklarga ma’lum edi. Ular hozirgi vaqtda gruppalashlar deb ataluvchi kombinatorik tushunchadan foydalanishgan. Eramizning XII asrida Bxaskara Acharya o’zining ilmiy tadqiqotlarida gruppalash va o’rin almashtirishlarni qo’llagan. Tarixiy ma’lumotlarga ko’ra, hindistonlik olimlar kombinatorika elementlaridan, jumladan, birlashmalardan foydalanib, she’riy asarlar tarkibiy tuzilishining mukammalligini tahlil qilishga uringanlar. Umuman olganda, kombinatorikaning dastlabki rivoji qimor o’yinlarini tahlil qilish bilan bog’liq. Ba’zi atoqli matematiklar, masalan, fransuz matematigi B.Paskal (1623-

1662), sveytasriyalik matematik Ya.Bernulli (1654- 1705), L.Eyler (1707-1783), rus matematigi P.L.Chebishev (1821-1894) turli o’yinlarda (tanga tashlash, soqqa tashlash, qarta o’yinlari va shu kabilarda) ilmiy jihatdan asoslangan qarorlar qabul qilishda kombinatorikani qo’llashgan. XVII asrda kombinatorika matematikaning alohida bir ilmiy yo’nalishi sifatida shakllana boshladi. Blez Paskal o’zining “Arifmetik uchburchak haqida traktat” va “Sonli tartiblar haqida traktat” (1665 y.) nomli asarlarida hozirgi vaqtda binomial koeffitsientlar deb ataluvchi sonlar haqidagi ma’lumotlarni keltirgan. Fransuz matematigi P.Ferma (1601-1665) esa figurali sonlar bilan birlashmalar nazariyasi orasida bog’lanish borligini bilgan. Figurali sonlar quyidagicha aniqlanadi. Birinchi tartibli figurali sonlar: 1, 2, 3, 4, 5, … (ya’ni, natural sonlar); ikkinchi tartibli figurali sonlar: 1-si 1ga 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, …); uchinchi tartibli figurali sonlar: 1-si 1ga teng, 2-si birinchi ikkita ikkinchi tartibli figurali sonlarlar yig’indisi (4), 3-si birinchi uchta ikkinchi tartibli figurali sonlarlar yig’indisi (10) va hokazo (1, 4, 10, 20, 35, …); va hokazo. 1-misol. 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 sonlarni tashkil qiladi. Bu tuzilmadan foydalanib, ikkinchi tartibli figurali sonlarni 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 nemis matematigi G.Leybnis (1646- 1716) ning “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. Kombinatorik masalalar va ularni yechishda qo’llaniladigan qoidalar. Ko’plab kombinatorik masalalarni yechishda qo’shish va ko’paytirish qoidalari qo’l keladi: a) qo’shish qoidasi: agar X to’plam m elementli, Y to’plam esa n elementli bo’lsa va ular o’zaro kesishmasa, X UY to’plamning elementlari soni n  m ga teng, ya’ni agar X  Y   bo’lsa, n(X UY)  n(X)  n(Y) bo’ladi. Umuman ixtiyoriy ikki X va Y to’plamlar uchun n(X UY)  n(X)  n(Y)  n(X  Y) o’rinli bo’ladi.

Похожие

M. Qaddafiy haqida kurs ishi
Kundalik yangiliklar va jurnallar kurs ishi
kurs ishi Genrix II Plantaganet davrida Angliya
Kombinatorika va kiriptografiya masalalari
Kombinatorika va kriptografiya masalalari