Kombinatorika asoslari fanidan kurs ishi - Алгебра - Курсовые работы

Информация о документе

Цена	9000UZS
Размер	498.2KB
Покупки	0
Дата загрузки	12 Март 2024
Расширение	docx
Раздел	Курсовые работы
Предмет	Алгебра

Kombinatorika asoslari fanidan kurs ishi

Купить

O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA MAXSUS TA’LIM VAZIRLIGI ANDIJON DAVLAT UNIVERSITETI FIZIKA VA MATEMATIKA FAKULTETI MATEMATIKA Kafedrasi KOMBINATORIKA ASOSLARI Fanidan KURS ISHI MAVZU: Bo’laklashlar kombinatorikasi Bajardi: _______________ Andijon

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. Eht

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 sohal

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 u

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 qism

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 chiq

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 usuli

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 C mk 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

Natural n sonni ixtiyoriy k ta ( k – natural son, k≤n ) a1,a2,...,ak natural sonlar yig’indisi, ya’ni n= a1+a2+...+ak ko’rinishda tasvirlashga n sonni k 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 n sonning k ta qo’shiluvchilarga bo’laklanishlari sonini B(n,k) bilan va shu sonning barcha bo’laklanishlari sonini B(n) bilan belgilasak, ravshanki, B(n)=∑k=1 n B(n,k) tenglik o’rinli bo’ladi. 1- m i s o l . Faqat bir yo’nalishda harakatlanganda besh

bo’ladi. ■ Endi B(n,k) va B(n) miqdorlarni hisoblash formulalarini topish bilan shug’ullanamiz. Dastlab n=1 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 B(1,1 )=1=C00=C1−10 =Cn−1 0 ta bo’laklashga ega bo’lamiz. Jami bo’laklashlar soni B(1)=B(1,1 )=Cn−10 =2n−1 bo’ladi 1 . n=2 bo’lgan holda k=1 qo’shiluvchili B(2,1 )=1=C10=C2−10 =Cn−10 ta ( 2=2 ) va k=2 qo’shiluvchili B(2,2 )=1=C11=C2−11 =Cn−1 1 ta ( 2=1+1 ) bo’laklashlarga ega bo’lamiz. Bu hol uchun jami bo’laklashlar soni B(2)=B(2,1 )+B(2,2 )=Cn−10 +Cn−1 1 =2n−1 . Agar n=3 bo’lsa, u holda k=1 qo’shiluvchili B(3,1 )=1=C20=C3−10 =Cn−10 ta ( 3=3 ), k=2

1- t e o r e m a . Qo’shiluvchilar tartibini e’tiborga olgan holda istalgan n natural sonning k ta qo’shiluvchilarga bo’laklanishlari soni ( n−1 ) ta elementdan ( k−1 ) talab gruppalashlar soniga teng, ya’ni B(n,k)=Cn−1k−1 . 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 n natural sonning barcha bo’laklanishlari soni 2n−1 ga teng, ya’ni B(n)=2n−1 . I s b o t i . Natural n sonning barcha bo’laklanishlari to’plamini S(n) deb, shu n sonning birinchi qo’shiluvchisi i ga ( i=1,2, ...,n ) teng bo’lgan bo’laklanishlari to’plamini esa Si(n) bilan belgilaymiz. Tushunarliki,

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 hodisa7=7 ko’rinishdagi bo’laklash vositasida ifodalanadi; agar to’qqizinchi qavatgacha lift ikki marta to’xtab, oldin uch kishi, keyin to’rt

Tabiiyki, quyidagi tenglik o’rinlidir:R(n)=∑k=1 n R(n,k) . Osonlik bilan ko’rish mumkinki, R(1)=1 , R(2)=2 , R(3)=3 , R(4)=5 , R(5)=7 , R(6)=11 , R(7)=15 . 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: R(8)= ∑k=1 8 R(8,k)=1+4+5+5+3+2+1+1=22 . Albatta, yuqorida keltirilgan formula yordamida ixtiyory natural n uchun uning barcha bo’laklanishlari sonini aniqlash mumkin. Lekin n yetarlicha katta qiymatga ega bo’lganda bu formuladan foydalanish juda ko’p hisoblashlar bajarishni taqozo qiladi. 11- ma’ruzada R(n) 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 R(8,1)=1 2 8=7+1=6+2=5+3=4+4 R(8,2

Natural n sonni k ta a1,a2,...,ak natural qo’shiluvchilarnung yig’indisi qilib bo’laklashga mos Ferrers diagrammasi k ta qatordan tashkil topgan bo’lib, uning (yuqoridan nastga qarab hisoblaganda) i - qatorida ai 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 a1≥a2≥...≥ak shart bajariladigan (yoki, kamaymaydigan ya’ni a1≤a2≤...≤ak shart bajariladigan ) tartibga rioya qilinadi. Bundan tashqari, qatorlardagi nuqtalar diagrammaning vertikal ustunlarini

2- shakl 2- расм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 n 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 . n natural sonning b1,b2,...,bp toq qo’shiluvchilarga bo’laklanishlaridan ixtiyoriy birini qaraymiz: n= b1+b1+...+b1 ⏟ r1 +b 2 +b 2 +...+b 2 ⏟ r 2 +...+b p +b p +...+b p ⏟ r p

Shunday qilib, n 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, 8 = 7 + 1 = 7 ⋅ 1 + 1 ⋅ 1 = 7 ⋅ 2 0 + 1 ⋅ 2 0 = 7 + 1 , 8= 5+3= 5⋅1+3⋅1= 5⋅20+3⋅20= 5+3 , 8=5+1+1+1=5⋅1+1⋅3=5⋅20+1⋅(21+20)= ¿5⋅20+1⋅21+1⋅20=5+2+1, 8= 3

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 n natural sonning hech bir qo’shiluvchisi k dan oshmaydigan bo’laklanishlari soni ( n+k ) sonining k ta qo’shiluvchilarga bo’laklanishlar soniga teng. I s b o t i . Birinchidan, shuni ta’kidlash lozimki, Ferrers diagrammasining transpozitsiyasi n sonning hech bir qo’shiluvchisi k dan oshmaydigan bo’laklanishlari bilan shu sonning k tadan oshmaydigan qo’shiluvchilarga bo’laklanishlari orasida o’zaro bir qiymatli moslik o’rnatadi. Bu bir qiymatli moslik asosida n sonning hech bir qo’shiluvchisi k dan

birinchi ustunni olib tashlasak, n ta nuqtadan tashkil topgan va qatorlari soni k tadan ko’p bo’lmagan diagrammani hosil qilamiz. Ko’rsatilgan bu ikki turdagi diagrammalar orasidagi o’zaro bir qiymatli moslik n sonni qo’shiluvchilari k tadan oshmaydigan bo’laklashlar soni R(n+k,k) 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

Купить