logo
  1. Bosh sahifa
  2. Diplom ishlar
  3. Umumiy
  4. KOMBINATORIKA MASALALARINING EHTIMOLLAR NAZARIYASI MASALALARINI YECHISHGA TADBIG‘I

KOMBINATORIKA MASALALARINING EHTIMOLLAR NAZARIYASI MASALALARINI YECHISHGA TADBIG‘I

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

96.0703125 KB
Ko'chirib olish
KOMBINATORIKA MASALALARINING EHTIMOLLAR NAZARIYASI MASALALARINI YECHISHGA TADBIG‘I ANNOTATSIYA Mazkur magistrlik dissertatsiyasida M arkov zanjirlari va ularning turli sohalarda masalan o‘yinlar nazariyasi, ommaviy xizmat ko‘rsatish nazariyasida qo‘llanishi ning nazariy asoslari va usullari qarab chiqiladi. Markov zanjirlari va ularning xossalarining amaliy masalalarini yechishga tadbiqiga oid misol va masalalar tahlil qilingan . ANNOTATION This master's work deals with the theoretical foundations and methods of Markov chains and their application in various fields, such as game theory, queuing theory. Examples and problems related to the use of Markov chains and their properties for solving practical problems are analyzed. Ilmiy rahbar do t s. H. Qurbonov Magistrant N. Mirsanov MUNDARIJA Kirish ………………………………………………………………… 3 I BOB. KOMBINATORIKA ELEMENTLARI VA HODISALAR YIG‘INDISINING EHTIMOLI 1.1-§ . Kombinatorikaning asosiy elementlari……………………………. 5 1.2- § . Hodisalar yig ‘ indisining ehtimoli………………………………… 13 1.3- § . Berilgan hodisalardan ma’lum sondagisining ro ‘y berish 1 ehtimoli………………………………………………. …………. 18 II BOB. KARRALI, MURAKKAB VA TANLANMA MOS TUSHISHLAR 2.1-§ . Karrali mos tushish hodisalari haqidagi masala…………………. 21 2.2- § . Murakkab mos tushishlar ………………………………………. 25 2.3- § . Karrali murakkab mos tushishlar ………………………………. 28 2.4- § . Karrali tanlanma mos tushishlar……………………………….... 31 III BOB. MOS TUSHISHLAR SONLARINING KO‘P O‘LCHOVLI TAQSIMOTI 3.1- § . Ehtimollar yig ‘indisi ehtimoli formulasining ba’zi umumlashmalari..35 3.2- § . Karrali mos tushishlar sonining birgalikdagi taqsimoti…….……. 39 Xulosa …………………………………………………………………… 44 Foydalanilgan adabiyotlar …...…………………………………………. 46 KIRISH 1. Mavzuning dolzarbligi. Kombinatorika matematikaning eng muhim bo ‘ limlaridan biri bo ‘ lib, ehtimollar nazariyasi, sonlar nazariyasi, guruhlar nazariyasi, matematik statistika, o ‘ yinlar nazariyasi va shunga o ‘ xshash ko ‘ plab sohalarga tegishli zamonaviy muomolarni hal qilishda katta ro ‘ l o ‘ ynaydi. Shuningdek, kombinatorika elementlari jadvallar tuzish ishlarida, transport masalalarini hal qilishda, ishlab chiqarishni rejalashtirishda keng qo ‘ llaniladi. 2 Kombinatorika masalalari bilan birinchilardan bo ‘ lib XVI asrda Italyan matematigi Tartaliya shug ‘ ullangan bo ‘ lib, u hal qilgan muommolar qimor o ‘ yinlari bilan bog ‘ liq edi. Chunki bu davrda yuqori tabaqalar hayotida qimor o ‘ yinlari katta o ‘ rin tutgan. Kombinatorikaning keyingi rivoji XVII asr matematiklari-fransuz olimlari Paskal va Ferma nomlari bilan bog ‘ liq. Keyinchalik esa bu sohada M.Bernulli, Leybnik va Eyler kabi olimlar ham tadqiqot ishlarini olib borishgan. Oxirgi yillarda kombinatorika tez suratlar bilan rivojlana boshladiki, bu hozirgi paytda deskrit matematika, matematik statistika va ehtimollar nazariyasining deyarli barcha sohalariga tadbiq etilishning kuchayishi bilan izohlanishi mumkin. Biroq shunga qaramasdan oliy matematika dasturlarisiz kombinatorikaga yetarlicha o ‘ rin ajratilmagan, o ‘ zbek tilida adabiyotlar deyarli yo’q. Rus tilida ham sanoqli, aksariyat adabiyotlar horijiy olimlar kitoblarining tarjimasidan iborat. Shu sababli kambinatorika elementlarining ehtimollar nazariyasi masalalarini yechishga tadbiqini tahlil qilish zaruriyati tug ‘ uldi. Ushbu magistrlik desertatsiyasida kombinatorika elementlari va ularning matematikaning boshqa sohalariga tadbiqi xususan shvet matematigi Mokmort tomonidan qo ‘ yilgan ‘‘ Mos tushushlar haqidagi masala’’ning qator variantlarining yechimlari o ‘ z aksini topgan. 2. Masalaning qo ‘ yilishi 1) Kombinatorika elementlari va ularga doir ayniyatlarni tahlil etish. 2) Mos tushushlar sonining ko ‘ p o ‘ lchovli taqsimotlarini aniqlash, ularning asimtotik holatlarini tahlil qilish. 3) Olingan natijalarni ommaviy xizmat ko ‘ rsatish nazariyasi masalalarini yechishga tadbiq etish. 3. Tadqiqot obyekti va predmeti. Tadqiqot obyekti kombinatorikaning asosiy elementlari va uning tadbiqlari, tadqiqot predmeti esa mos tushushlar 3 haqidagi masalaning asosiy variantlari va uning yechimlarini asimtotik tahlil qilish hisoblanadi. 4. Tadqiqot maqsadi va vazifalari. Tadqiqot maqsadi kombinatorika elementlarini ehtimollar nazariyasi masalalarini yechishga tadbiq etish bo ‘ lib, shu maqsadda quyidagi ishlarni amalga oshirish vazifasi belgilandi; 1) Kombinatorikaning asosiy elementlarini tahlil qilish, 2) Karrali mos tushushlar sonining taqsimotini aniqlash, 3) Murakkab mos tushushlar sonining taqsimotini aniqlash, 4) Karrali va murakkab mos tushushlar haqidagi masalani umumlashtirish, 5) Tanlanma mos tushushlar haqidagi masalani yechish. 5. Umumiy yangilik. Ko ‘ p o ‘ lchovli karrali murakkab mos tushushlar sonining taqsimoti topildi. Shunungdek ko ‘ p karrali tanlanma mos tushushlar sonining taqsimoti aniqlandi. 6. Tadqiqot natijalarining ilmiy axamiyati. Ishda olingan natijalar malum natijalarning ko ‘ p o ‘ lchovli xili uchun umumlashmalari bo ‘ lib, taqsimotlarning asimtotik xolatlari birinchi marta taxlil qilinmoqda. Ushbu natijalar mos tushushlar haqidagi masalalarning nisbatan murakkab variantlarini o ‘ rganish uchun mo ‘ ljal bo ‘ lib xizmat qiladi. 7. Ishning amaliy axamiyati. Ushbu ishda qaralgan masala sxematik xarakterga ega bo ‘ lib, ko ‘ plab real masalalarni (ommaviy xizmat ko ‘ rsatish sistemalari, mayda zarrachalar fizikasi, sof ko ‘ payish jarayonlari va boshqalar) shu sxemaga keltirish yoki yaqinlashtirish mumkin. 8. Ilmiy tadqiqot metodlari. Ushbu ishda kombinatorika va ehtimollar nazariyasining umumiy tadqiqot metodlari bilan bir qatorda matematik induksiya, elementar hodisa ehtimolini qo ‘ shish va ajratib olish metodlaridan keng foydalanildi. 4 9. Ishning tuzilishi. Ish kirish qismi va uchta bobga birlashtirilgan oltita paragraf, xulosa va foydalanilgan adabiyotlar qismlaridan iborat. Bibliografiyada 1 ta monagrafiya, 4 ta darslik, 5 ta ilmiy maqolalar jami 10 ta adabiyot ro ‘ yxati keltirilgan. Ish 52 betdan iborat. 10. Ishning qisqacha mazmuni. I- bob ikkita paragrifdan iborat bo ‘ lib, kombinatorika oid va ishda bevosita qo ‘ llanilgan malumotlar, xodisalar yig ‘ indisining extimoli va uning umumlashmalari berilgan. II-bobga karrali, murakkab va murakkab karrali mos tushushlar bo ‘ yicha olingan natijalar keltiriladi. III − ¿ bob ehtimollarni qo‘shish teoremasining umumlashmasi, mos tushishlar sonlarining ko‘p o‘lchovli taqsimoti, mos tushishlar sonining sonli harakteristikalarini hisoblash, murakkab karrali mos tushishlar soni taqsimot qonunining parametrlarining ( N − ¿ yacheyka yoki qutilar soni, K − ¿ zarracha yoki sharchalar partiyalari soni, n−¿ har bir partiyadagi zarrachalar to‘plami soni) turli o‘zgarishlardagi asimptotik holatlari qaralgan. Xulosa qismida dissertatsiya ishida qaralgan masalalarning ahamiyati, tadbiq sohalari, olingan asosiy natijalar va qo‘llanilgan tadqiqot metodlari, shuningdek, ishni davom ettirish yo‘nalishlari haqida ma’lumotlar berilgan. I BOB. KOMBINATORIKA ELEMENTLARI VA HODISALAR YIG‘INDISINING EHTIMOLI 1.1 - § . Kombinatorikaning asosiy elementlari 5 Chekli sondagi va teng imkoniyatli elementar natijalardan tashkil topgan hodisalarning ehtimolligini hisoblashda biz odatda ehtimollikning klassik ta’rifidan, ya’ni qaralayotgan hodisaga qulaylik tug‘diruvchi elementar hodisalar sonining barcha elementar hodisalar soniga nisbati ko‘rinishida beriladigan ehtimollikdan foydalanamiz. Bu ko‘pchilik hollarda texnik qiyinchiliklar bilan bog‘liq bo‘lib, mumkin bo‘lgan holatlarni sanab chiqish amaliy jihatdan mumkin bo‘lmaydi. Bunday hollarda kombinatorika elementlaridan foydalanishga to‘g‘ri keladi. Masalan, quyidagi savollarga javob berish so‘ralayotgan bo‘lsin: 1) 1,2,3,7,8,9 raqamlar ishtirok etadigan nechta uch xonali sonlar bor. 2) 20 ta futbol komandalaridan har biri qolganlari bilan bir martadan o‘yin o‘tkazadigan bo‘lsa, jami nechta o‘yin o‘tkaziladi. 3) 10 ta kitobni kitob javoniga necha xil usul bilan terib qo‘yish mumkin. 4) Chapdan o‘ngga va o‘ngdan chapga qarab bir xil o‘qiladigan nechta yetti xonali son mavjud. 5) Korxona ishlab chiqargan 100 dona mahsulotdan 12 donasi sifatsiz mahsulot bo‘lsin. Agar tekshirish uchun tasodifan 10 ta mahsulot olinadigan bo‘lsa, shundan 4 tasi sifatsiz bo‘ladigan holatlar nechta? Ushbu hollarda barcha variantlarni hisoblab chiqish uzoq vaqt talab qiladi. Lekin kombinatorika elementlaridan foydalanib masalani oson hal etish mumkin. Quyidagi kombinatorik analizning asosiy elementlarini keltirib o‘tamiz. 1. Juftliklar Bizga A=(a1,a2,… ,an) va B=(b1,b2,… ,bm) to‘plamlar berilgan bo‘lsin. Har bir to‘plamdan bittadan elementni olib, ( a , b ) ko‘rinishdagi 6 tanlanma to‘plamni n∙m usulda tuzish mumkin. Bu yerda a Aϵ va b Bϵ . Haqiqatdan ham agar A to‘plamdan ai(i=1. n) element olingan bo‘lsa, B to‘plam elementlari hisobidan m ta, ya’ni (a¿¿i,b1),(a¿¿i,b2),… ,(a¿¿i,bm)¿¿¿ tanlanma to‘plamlarni tuzish mumkin. A to‘plam elementlari soni n ga teng bo‘lganligi uchun mumkin bo‘lgan barcha variantlar soni n∙m bo‘ladi. 2.Kortejlar (kombinatsiyalar) Bizga k ta A1= (a1,a2,… ,an1),A2=(b1,b2,… ,bn2),… ,Ak=(c1,c2,… ,cnk) to‘plamlar berilgan bo‘lsin. Har bir to‘plamdan bittadan element olib, ( a , b , … , c ) ko‘rinishdagi tanlanma to‘plamni n1∙n2∙… ∙nk= n usulda tuzish mumkin. Bu yerda a ϵ A 1 , b ϵ A 2 , … , c ϵ A k ( a , b , … , c ) tanlanma to‘plam k ta to‘plamdan bittadan element olib tuzilgan kortej deyiladi. Ma’lumki, ( a , b , … , c ) tanlanma to‘plam A 1 , … , A k to‘plamlar Dekart ko‘paytmasining, ya’ni A = A 1 × A 2 × … × A k to‘plamning elementi bo‘ladi. n = n 1 ∙ n 2 ∙ … ∙ n k tenglik o‘rinli bo‘lishini matematik induksiya metodidan foydalanib oson ko‘rsatish mumkin. 1-misol. 6 nafar ingliz tilini, 7 nafar nemis tilini va 4 nafar fransuz tilini biladigan talabalar bor. Olimpiadada ishtirok etish uchun 3 kishidan iborat (bitta ingliz tilini, bitta nemis tilini, bitta fransuz tilini biladigan) komanda tuziladi. Ushbu ishni necha xil usulda bajarish mumkin? Agar har bir tilni biladigan talabalarni to‘plam deb qarasak, mumkin bo‘lgan kortejlar (komandalar) soni n = 6 ∙ 7 ∙ 4 = 168 bo‘ladi. 3. O‘rinlashtirishlar A0=(a1,a2,… ,an) to‘plam elementlaridan m tasini olib, ( a i 1 , a i 2 , … , a i m ) ko‘rinishdagi tanlanma to‘plamni tuzamiz. Har biri 7 boshqalaridan kamida bitta elementi yoki elementlarni tanlash tartibi bilan farq qiladigan ushbu tanlanma to‘plamlar tartiblangan tanlanmalar yoki o‘rinlashtirishlar deyiladi. Mumkin bo‘lgan barcha o‘rinlashtirishlar soniPnm=n(n−1)… (n− m+1).(1.1 .1) formula bilan hisoblanadi. Haqiqatdan ham a i 1 element a1,a2,… ,an elementlardan ixtiyoriy biri bo‘lishi mumkin, ya’ni A0 to‘plamning ixtiyoriy elementi. ai1 tanlangan bo‘lsin. U holda ai2 elementni qolgan n − 1 ta elementdan iborat bo‘lgan A 1 = ( a 1 , … a i 1 − 1 , a i 1 − 2 , … , a n ) to‘plamdan tanlaymiz va h.k aim elementni A 0 ning a i 1 , … , a i m − 1 elementlar qatnashmaydigan, n− m+1 ta elementdan iborat bo‘lgan qism to‘plami Am−1 dan olamiz. U holda kortejlar sonini hisoblash formulasiga ko‘ra o‘rinlashtirishlar soni n ( n − 1 ) … ( n − m + 1 ) ga teng bo‘ladi. 2-misol. 1,2,3,4,5,6,7 raqamlarni faqat bir marta ishlatib nechta to‘rt xonali son yasash mumkin? Ma’lumki, raqamlar o‘rnini, ya’ni tanlash tartibini almashtirsak, boshqa son hosil bo‘ladi. (1.1.1) formulaga ko‘ra to‘rt xonali sonlar miqdori P 74 = 7 ∙ 6 ∙ 5 ∙ 4 = 840 ga teng bo‘ladi. P nm − n ta elementdan m tadan olib tuzilgan o‘rinlashtirishlar soni deyiladi. 4. O‘rin almashtirishlar A 0 = ( a 1 , a 2 , … , a n ) to‘plam berilgan bo‘lib, bittadan ketma-ket hamma elementlarni olaylik. U holda n ta elementdan olib tuzilgan o‘rinlashtirishlarga ega bo‘lamiz. Bunda har bir tanlanma boshqalaridan faqat elementlarni tanlash tartibi bilan farq qiladi va o‘rin almashtirishlar deyiladi. 8 (1.1.1) formulaga ko‘ra barcha mumkin bo‘lgan o‘rin almashtirishlar sonin!= Pnn=n(n−1)(n−2)… 2∙1(1.1 .2) 3-misol. 10 ta kitobni kitob javoniga necha xil usulda terib qo‘yish mumkin? (1.1.2) formulaga ko‘ra 10 ta kitobni javonga 10 !=1∙2∙3∙4∙5∙6∙7∙8∙9∙10 =3628800 usulda terish mumkin. 4-misol. ,,Raketa” so‘zida harflar o‘rni almashtirilsa, nechta “so‘z” hosil bo‘lishi mumkin? Yechish. Hosil bo‘ladigan ,,so‘z”larda harflar faqat bir martadan qatnashsa, ya’ni takrorlanmasa, buning uchun, masalan, ikkala “a” ikkita alohida olingan element deb qabul qilinsa, takrorsiz o‘rin almashtirishlarga ega bo‘lamiz. U holda ularning soni P6=6!=1∙2∙3∙4∙5∙6= 720 ta bo‘ladi. 5-misol. Shaxmat bo‘yicha musobaqada har birining tarkibida to‘rt nafar o‘yinchi bo‘lgan ikkita komanda ishtirok etmoqda. Har bir komanda rahbariga to‘rtta shaxmat taxtasida o‘yinlar o‘tkazish uchun o‘yinchilarni ixtiyoriy ravishda tartiblash imkoniyati berilgan. Musobaqa qatnashchilarining shaxmat taxtalarini egallash imkoniyatlari (variantlari) sonini toping. Yechish. H ar bir komanda a’zolari uchun shaxmat taxtalarini egallash imkoniyatlarini P n = n ! formula yordamida hisoblash mumkin: P4= 4!= 24 . Komandalardagi o‘yinchilarni ixtiyoriy ravishda tartiblash mumkin bo‘lganligidan, ko‘paytirish qoidasiga ko‘ra, musobaqa qatnashchilarining shaxmat taxtalarini egallash imkoniyatlari (variantlari) soni 24 ∙24 =576 bo‘ladi . 5. Guruhlashtirishlar A0=(a1,a2,… ,an) to‘plam elementlaridan m tasini olib, ( a i 1 , a 2 i 2 , … , a m ) tanlanma to‘plamni tuzaylik. Har biri boshqalaridan kamida bitta elementi 9 bilan farq qiladigan bunday tanlanmalar n ta elementdan m tadan olib tuzilgan guruhlashtirishlar deyiladi. Mumkin bo‘lgan barcha guruhlashtirishlar soni ushbu formula bilan hisoblanadi: C nm = n ! m ! ( n − m ) ! . ( 1.1 .3 ) Haqiqatdan ham guruhlashtirishlar o‘rinlashtirishlardan shu bilan farq qiladiki, bunda elementlarni tanlash tartibi e’tiborga olinmaydi, ya’ni o‘rinlashtirishlarda m ta elementdan faqat tanlash tartibi bilan farq qiladigan m ! ta tanlanma bitta tanlanma hisoblanadi, ya’ni tanlanmalar boshqalaridan farq qilishi uchun kamida bitta elementi boshqa bo‘lishi kerak. Shunday qilib, m hajmli guruhlashtirishlar shu hajmli o‘rinlashtirishlardan m! marta kam bo‘ladi. Unda (1.1.1) formulaga ko‘ra C nm = P nm m ! = n ( n − 1 ) … ( n − m + 1 ) m ! . ( 1.1 .4 ) Bundan kasrning surati va maxrajini ( n − m ) ! ga ko‘paytirib, (1.1.3) formulaga ega bo‘lamiz. Bu yerda 0 ! = 1 , C n0 = 1 deb qabul qilinadi. Quyidagi munosabat o‘rinli: Cnm=Cnn−m 6-misol. 20 nafar shaxmatchilar mavjud bo‘lib, musobaqada ishtirok etish uchun 5 kishidan iborat komanda tashkil etish lozim. Komandani necha xil usulda tashkil etish mumkin? Ravshanki, ushbu misolda shaxmatchilarni tanlash tartibi ahamiyatli emas, ya’ni (1.1.3) yoki (1.1.4) formuladan foydalanish mumkin, ya’ni komandani C 205 = 20 ∙ 19 ∙ 18 ∙ 17 ∙ 16 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 = 5814 usulda tashkil etish mumkin. 7-misol. Qurilish tashkilotining duradgorlar bo‘limida 15 nafar ishchi bor. Ko‘p qavatli uyning eshiklarini ta’mirlash uchun 3 nafar duradgorni tanlash 10 zarur. Agar bo‘limdagi har bir duradgor bu topshiriqni bajarishga layoqatli bo‘lsa, bunday tanlash imkoniyatlari (variantlari) qancha? Yechish . Bo‘limdagi har bir duradgor ta’mirlash ishini bajarishga layoqatli bo‘lgani uchun, bu masalani hal qilishda gruppalashlar sonini topish formulasidan foydalanish mumkin. Bu yerda n = 15 , m = 3 va C 153 = 15 ∙ 14 ∙ 13 1 ∙ 2 ∙ 3 = 455 . Demak, 15 nafar duradgorlar orasidan 3 nafarini tanlash imkoniyatlari soni 455 ekan. 6. Takroriy tanlanmalar (joylashtirishlar) A0=(a1,a2,… ,an) to‘plamdan bitta element olib, element raqamini qayd etamiz va to‘plamga qaytarib qo‘yamiz. Shu jarayonni m marta takrorlab, ( a i 1 , a 2 i 2 , … , a i m ) tanlanmani hosil qilaylik. Bu yerda tanlanmaning bir nechta yoki hamma elementi bir-biriga teng bo‘lishi mumkin. Bunday tanlanma takroriy tanlanmalar yoki joylashtirishlar deyiladi va ularning soni Anm= nm(1.1 .5) ga teng. Haqiqatdan ham, ushbu tanlanmani hammasi A 0 ga teng bo‘lgan m ta to‘plamdan bittadan element olib tuziladigan kortej deb hisoblash mumkin. U holda kortejlar sonini hisoblash formulasiga ko‘ra A nm = n ∙ n ∙ … ∙ n = n m bo‘ladi. 8-misol. Guru h 25 nafar talabadan tashkil topgan bo‘lsin. Bu guruhda guruh sardori, guruh sardorining yordamchisi va kasaba uyushmasining guruh bo‘yicha vakilini saylash zarur. Har bir talaba bu vazifalardan faqat bittasini bajaradi deb hisoblansa, saylov natijalari uchun qancha imkoniyat mavjud? Yechish. Bu yerda 25 ta elementli talabalar to‘plamining tartiblangan uchta elementli (guruh sardori, guruh sardorining yordamchisi va kasaba uyushmasining guruh bo‘yicha vakili) qism to‘plamlari sonini aniqlash zarur. 11 Bu esa 25 ta elementdan uchtadan o‘rinlashtirishlar soni A 253 = 25 ∙ 24 ∙ 23 = 13800 ekanligini aniqlaymiz. Demak, guruhdagi saylov natijalari uchun 13800 ta imkoniyat mavjud. 9-misol. 10 ta qutilarga 5 ta soqqani necha xil usulda joylash mumkin? Ushbu misolda qutilarni to‘plam elementlari va soqqa joylashadigan qutini tanlashni tanlanma elementi deb qarash mumkin, ya’ni birinchi soqqani joylash uchun 10 ta qutidan biri, ikkinchi soqqani joylash uchun yana shu 10 ta qutidan biri tanlanadi va h.k. Soqqalar 5 ta bo‘lganligi sababli qutilarni tanlash ham 5 marta takrorlanadi. U holda (1.1.5) formulaga ko‘ra 5 ta soqqani 10 ta qutiga A 105 = 10 5 = 100000 usulda joylash mumkin. 10-misol. 1,2,3,4,5,6,7,8,9 raqamlaridan nechta uch xonali son tuzish mumkin? Yechish. Demak barcha uch xonali sonlarni quyidagicha topamiz. T = { 1,2,3,4,5,6,7,8,9 } to‘plam elementlari qatnashadigan va komponentalari takrorlanmaydigan uch xonali sonlar jami A93= 9! 6!∙3!=84 ta tuzish mumkin. 1.2 - § . Hodisalar yig ‘ indisining ehtimoli Ehtimollarning xossalaridan bilamizki, ixtiyoriy ikkita A 1 va A 2 hodisalar yig‘indisining ehtimoli ushbu formula bilan aniqlanadi. P(A1+A2)= P(A1)+P(A2)− P(A1∙A2).(1.2 .1) 12 Bu tenglikni N ta A1,A2,… ,AN hodisalar uchun umumlashtiramiz. Buning uchun alohida olingan hodisalarninggina emas, balki ularning mumkin bo‘lgan barcha kesishmalarining ham ehtimollarini ham bilish kerak bo‘ladi. Soddalik uchun quyidagi belgilashlarni kiritamiz: P i = P ( A i ) , P ij = P ( A i ∙ A j ) , P ijk = P ( A i ∙ A j ∙ A k ) , … , ( 1.2 .2 ) bu yerda indekslarni o‘sish tartibida joylashtiramiz va har bir ehtimollikdagi indekslar mos tushmaydi. Mumkin bo‘lgan barcha ehtimolliklar yig‘indisini quydagicha belgilaymiz: S 1 = ∑ i P i , S 2 = ∑ i < j P ij , S 3 = ∑ i < j < k P ijk , … , ( 1.2 .3 ) bu yerda 1 ≤ i < j < k … ≤ N , ya’ni yig‘indilardagi ehtimolliklar faqat bir marta qatnashadi va Sr yig‘indi C Nr ta qo‘shiluvchiga ega. N =2 da (1.2.1) ga ko‘ra P ( A 1 + A 2 ) = S 1 − S 2 . ( 1.2 .4 ) tenglik hosil bo‘ladi. Ushbu formulani N ta ( N ≥ 2 ) hodisa uchun umumlashtirib, quyidagi tenglikni olamiz: Teorema. A 1 , A 2 , … , A N hodisalardan kamida bittasining ro‘y berish ehtimoli ushbu formula bilan hisoblanadi: P1= P(A1+… +AN)= S1−S2+S3− S4+… +(−1)N−1SN.(1.2 .5) Teoremani ikki xil usulda isbotlash mumkin. 1-isbot. ,,Qo‘shish va ajratib yozish metodi”. Ma’lumki, har qanday hodisaning ehtimoli uni tashkil etuvchi elementar hodisalar ehtimollarining yig‘indisiga teng, ya’ni (5) formuladagi S 1 , S 2 , … larni elementar hodisalar ehtimollari bo‘yicha yoysak, B= A1+A2+… +AN hodisani tashkil etuvchi ixtiyoriy ω∈B elementar hodisaning ehtimoli (1.2.5) ning o‘ng tomonida birga teng koefisienti bilan qatnashadi. Faraz qilaylik, biror ω∈B elementar hodisa A1,… ,AN hodisalardan n tasining tarkibiga kirishi. U holda ω elementar hodisa ehtimoli S1 yig‘indida n ga teng koefisient bilan, S 2 yig‘indida Cn2 ga teng 13 koefisient bilan va h.k Sn ning tarkibida C nn ga teng koeffisient bilan qatnashadi. i>n da P ( ω ) ehtimollik Si ning tarkibida mavjud bo‘lmaydi. Demak, agar ω∈B elementar hodisa A 1 , … , A N hodisalardan n tasining tarkibida mavjud bo‘lsa, P ( ω ) ehtimollik (1.2.5) ning o‘ng tomonida n−Cn2+Cn3−… +(−1)n−1Cnn . (1.2.6) koefisient bilan qatnashadi. Endi teoremani isbotlash uchun (1.2.6) yig‘indining birga tengligini ko‘rsatish yetarli. Haqiqatdan ham n−Cn2+Cn3−… +(−1)n−1Cnn=1−(1− n+Cn2−… ±Cnn)=¿ ¿1−(Cn0−Cn1+Cn2−… ±Cnn)=1−(1−1)n=1. 2-isbot. “Matematik induksiya metodi”. (1.2.1) tenglikga ko‘ra (1.2.5) formula N =2 uchun o‘rinli. Faraz qilaylik, (1.2.5) formula N −1 ta A1,… ,AN−1 hodisalar uchun o‘rinli bo‘lsin. Quyidagi belgilashni kiritaylik: B= A1+… +AN−1. U holda (1.2.1) ga ko‘ra ushbu tenglikga ega bo‘lamiz P1= P(A1+… +AN)= P(B+AN)= P(B)+P(AN)− P(BAN).(1.2 .7) Shartga ko‘ra (1.2.5) formula A1,… ,AN−1 , hodisalar uchun o‘rinli, ya’ni P(B)= S1'−S2'+S3'−… ±SN−1 ' ,(1.2 .8) bu yerda S i' lar S i' lardan faqat AN hodisa qatnashmasligi bilan farq qiladi. P(BA )= P(A1AN+… +AN−1AN), ya’ni B A N ham N − 1 ta hodisa yig‘indisiga teng va farazga ko‘ra (1.2.5) formula A1AN+… +AN−1AN hodisalar uchun o‘rinli: P ( B A N ) = S 1' ' − S 2' ' + S 3' ' − … ± S N − 1' ' , ( 1.2 .9 ) bu yerda S i' ' yig‘indi Si+1 ning AN hodisa qatnashadigan qo‘shiluvchilardan iborat. 14 (1.2.8) va (1.2.9) ifodalarni (1.2.7) ga qo‘ysak, S 1' ' P(AN) larning yig‘indisi S1 ni, S 2' ' va S 1' ' larning yig‘indisi S2 ni , S 3' va S 2' ' larni yig‘indisi S 3 beradi va h.k. Shunday qilib, (1.2.5) formula N ta hodisa uchun o‘rinli ekanligi kelib chiqadi. Misol. Mos tushishlar (Monmort masalasi) N ta qartalardan iborat ikkita qartalar dastasining har biri yaxshilab aralashtiriladi va ikkala dastadagi qartalarning joylashish tartibi solishtiriladi. Biror o‘rinda bir xil qarta joylashgan bo‘lsa , shu joyda mos tushish hodisasi ro‘y berdi deyiladi. Kamida bitta mos tushish hodisasining ro‘y berish ehtimolini topish talab qilinsin. Yechish. i − ¿ inchi ( 1 ≤ i ≤ N ) o‘rinda mos tushish hodisalarining ro‘y berishini Ai orqali ifodalaylik. U holda (1.2.5) formulaga ko‘ra P(A1+… +AN)=∑i P(Ai)−∑i<j P(AiAj)+… +(−1)P(A1A2… AN)(1.2 .10 ) Masalaning qo‘yilishiga ko‘ra hamma A 1 , … , A N hodisalar teng imkoniyatli. Shu sababli P(A1)=… = P(AN),P(A1A2)=… = P(AN−1AN),… . Demak , (1.2.10) formuladagi yig‘indilarda bitta qo‘shiluvchini, aytaylik, P(A1),P(A1A2),… larni olib, qo‘shiluvchilar soniga ko‘paytirish yetarli. (1.2.10) ga asosan hosil qilamiz: P1= P(A1+… +AN)= NP (A1)−CN2P(A1A2)+… (−1)NP(A1… AN)(1.2 .11 ) P ( A 1 ) ni hisoblaylik. Ehtimolning klassik ta’rifiga ko‘ra P ( A 1 ) = m ( A 1 ) n . Birinchi dastadagi qartalar biror tartibda joylashgan bo‘lsin. Unda ikkinchi dastadagi qartalarni birinchi dastaga solishtirish uchun n = N ! usulda tartiblash mumkin. Endi A1 hodisa ro‘y beradigan hollarni hisoblaymiz. Birinchi o‘rinda mos tushish hodisasi ro‘y bergan bo‘lsin. U holda ikkinchi 15 dastadan N −1 ta qartani ( N − 1 ) ! usulda tartiblash mumkinligini e’tiborga olsak, m ( A 1 ) = ( N − 1 ) ! bo‘ladi. Demak, P ( A 1 ) = ( N − 1 ) ! N = 1 N Endi, faraz qilaylik, A1∙A2 hodisa ro‘y bergan bo‘lsin. U holda ikkinchi dastadagi N −2 ta qartani ( N − 2 ) ! usulda tartiblash mumkin va P ( A 1 A 2 ) = m ( A 1 A 2 ) n = ( N − 2 ) ! N = 1 N ( N − 1 ) = 1 P N2 bo‘ladi. Huddi shuningdek, P ( A 1 A 2 A 3 ) = m ( A 1 A 2 A 3 ) n = ( N − 3 ) ! N = 1 N ( N − 1 ) ( N − 2 ) = 1 P N3 . va h.k ehtimolliklarni hisoblaymiz. Bularga asosan (1.2.11) dan P 1 = N 1 N − C N2 1 P N2 + C N3 1 P N3 − … ( − 1 ) N C NN 1 P NN . ( 1.2 .12 ) tenglikka ega bo‘lamiz. Agar C Nm = P Nm m ! tenglikni e’tiborga olsak, P 1 = 1 − 1 2 ! + 1 3 ! − … + ( − 1 ) N 1 N ! . munosabatni hosil qilamiz. Bundan ko‘rinadiki, 1− P1 ehtimol e − 1 = 1 − 1 + 1 2 ! − 1 3 ! + … yoyilmaning birinchi N + 1 ta hadi yig‘indisiga teng. Demak, lim N → ∞ ( 1 − P 1 ) = e − 1 . Shunday qilib, quyidagi munosabat o‘rinli bo‘ladi: P1≈1−e−1=0.63212 … 16 Bundan quyidagi xulosani chiqarish mumkin: N ning yetarlicha katta qiymatlarida kamida bitta mos tushish hodisasining ro‘y berish ehtimoli amaliy jihatdan N ga bog‘liq emas va 1 − e − 1 ga teng. 1.3 - § . Berilgan hodisalardan ma’lum sondagisining ro ‘y berish ehtimoli 1-teorema. A 1 , A 2 … A N hodisalardan rosa m tasining ( 1 ≤ m ≤ N ) ro‘y berish ehtimoli P[m] ushbu formula bilan aniqlanadi: P[m]= ∑r=0 N−m (−1)rCm+r m Sm+1.(1.3 .1) 17 Izoh. Oldingi paragrafdagi natijaga ko‘ra birorta ham hodisaning ro‘y berish ehtimoli quydagiga teng. P[ 0] = 1 − P 1 = 1 − S 1 + S 2 − S 3 + … ± S N . Demak , agar biz S0=1 deb qabul qilsak, (1.3.1) formula m=0 uchun ham o‘rinli bo‘ladi. Teoremaning isboti: Faraz qilaylik, P [ 0] = P ( B ) bo‘lsin va biror ω B ϵ elementar hodisa A1,A2… AN hodisalardan n tasining tarkibiga kirsin. U holda ω Bϵ hodisa (1.3.1) tenglikning o‘ng tomoniga faqat n= m bo‘lgandagina kiradi. Shuni qayd etib o‘tamizki, agar ω A 1 , A 2 … A N hodisalardan n tasining tarkibiga kirsa, u holda P ( ω ) ehtimol (1.3.1) tenglikdagi S m , S m + 1 , … S n yig‘indilar tarkibiga kiradi va S n + 1 , … , S N yig‘indilar tarkibiga kirmaydi. Demak, n<m da P ( ω ) ehtimol (1.3.1) tenglikning o‘ng tomonida qatnashmaydi, ya’ni agar tenglikning o‘ng tomonini elementar hodisalar ehtimoli bo‘yicha yoysak, P ( ω ) lar o‘zaro qisqarib ketadi. Haqiqatdan ham P ( ω ) ehtimol n > m da Sk(m<k≤n) yig‘indiga Cnk koefitsient bilan kiradi. Shunday qilib, P ( ω ) ehtimol (1.3.1) tenglikning o‘ng tomoniga C nk − C m + 1m C nm + 1 + C m + 2m C nm + 2 − … ± C n − mm C nn − m ( 1.3 .2 ) koefitsient bilan kiradi. C m + km ∙ C nm + k = ( m + k ) ! m ! k ! ∙ n ! ( m + k ) !( n − k − m ) ! = ¿ ¿ n ! m ! ( n − m ) ! ∙ ( n − m ) ! k ! ( n − m − k ) ! = C nm C n − mk tenglikka ko‘ra (1.3.2) ifoda ushbu ko‘rinishga keladi: Cnm(Cn−m 0 −Cn−m 1 +Cn−m2 −… ±Cn−mn−m)(1.3 .3) Bu yerda qavs ichidagi ifoda (1−1)n−m ning binomial yoyilmasi ekanligi e’tiborga olinsa, (1.3.3) ifoda nolga tengligi kelib chiqadi. 18 Misol. Misol sifatida mos tushishlar haqidagi masalalarni qaraymiz. Odingi paragrafda biz S = 1 k ! tenglikni topgan edik. Ushbu ifodani (1.3.1) formulaga qo‘yib, rosa m ta mos tushish hodisalari ro‘y berish ehtimolini hisoblaymiz. m = 0 , m = 1 , … , m = N da quyidagi tengliklarga ega bo‘lamiz: P[0]=1−1+ 1 2!− 1 3!+… ± 1 (N−1)!± 1 N !, P [ 1] = 1 − 1 + 1 2 ! − 1 3 ! + … ± 1 ( N − 2 ) ! ± 1 ( N − 1 ) ! , P[2]= 1 2!(1−1+ 1 2!− 1 3!+… ± 1 (N− 3)!± 1 (N− 2)!), P [ 3] = 1 3 ! ( 1 − 1 + 1 2 ! − 1 3 ! + … ± 1 ( N − 3 ) !) , ( 1.3 .4 ) −−−−−−−−−… , P[N−2]= 1 (N −2)!(1−1+ 1 2!), P [ N − 1 ] = 1 ( N − 1 ) ! ( 1 − 1 ) = 0 , P[N]= 1 (N )!. Bu yerda P[N−1]=0 tenglik shuni ko‘rsatadiki, rosa N − 1 ta mos tushish hodisasi ro‘y berishi mumkin emas. Haqiqatdan ham, agar N − 1 ta mos tushish hodisasi ro‘y bergan bo‘lsa, N −¿ o‘rinda ham o‘z- o‘zidan mos tushish ro‘y beradi. (1.3.4) tengliklardan ko‘rinadiki, P [ m] ehtimollikdagi qavs ichidagi ifoda e−1 ning qatorga yoyilmasidagi birinchi N −m ta hadining yig‘indisini beradi. Shu sababli ushbu munosabat bajariladi: lim N → ∞ P [ m] = 1 m ! e − 1 , 19 ya’ni cheksiz sondagi qartalardan iborat ikkita qartalar dastasi solishtirilsa, mos tushishlar soni parametri birga teng bo‘lgan Puasson taqsimotiga ega bo‘ladi. 2-teorema. A1,A2,… ,AN hodisalardan kamida m tasining ro‘y berish ehtimoli ushbu formula bilan hisoblanadi: Pm=Sm−Cmm−1Sm+1+Cm+1 m−1Sm+2−… ±CN−1 m−1SN.(1.3 .5) Teoremani isbotlash uchun (1.3.1) tenglikdan foydalaniladi. Ehtimolning xossasiga ko‘ra P m = P [ m] + P [ m + 1 ] + … + P N . ( 1.3 .6 ) Bu tenglikka P [ k] larning ( m ≤ k ≤ N ) qiymatlarini qo‘yib, qator soddalashtirishlardan keyin (1.3.6) tenglikni hosil qilish mumkin. II BOB. KARRALI, MURAKKAB VA TANLANMA MOS TUSHISHLAR 2.1-§. Karrali mos tushish hodisalari haqidagi masala N ta raqamlangan qutilar va har biri raqamlangan N ta soqqalardan iborat k ta bir xil soqqalar to‘plami berilgan bo‘lsin. Avval birinchi to‘plam, keyin ikkinchi to‘plam va h.k. k−¿ to‘plam soqqalarini qutilarga bittadan 20 joylashtiramiz. Har bir qutida k tadan soqqa bo‘ladi. Agar biror qutida quti va hamisha soqqalarning raqami bir xil bo‘lsa, shu o‘rinda k karrali mos tushish hodisasi ro‘y berdi deyiladi. Teorema. m o‘rinda ( 0 ≤ m ≤ N ) k karrali mos tushish hodisasining ro‘y berish ehtimoli U mk quyidagi formula bilan hisoblanadi: U mk = 1 m ! ( N ! ) k − 1 ∑ r = 0N − m ( − 1 ) r[( N − m − r ) !] k − 1 r ! . ( 2.1 .1 ) Hech bo‘lmaganda m o‘rinda k karrali mos tushish hodisasining ro‘y berish ehtimoli U mk¿ quyidagicha aniqlanadi. U mk¿ = 1 ( m − 1 ) ! ( N ! ) k − 1 ∑ r = mN ( − 1 ) r − m [( N − r ) !] k − 1 r ∙ ( r − m ) ! . ( 2.1 .2 ) Isbot. i−¿ o‘rinda k karrali mos tushish hodisasining ro‘y berishini Aik orqali belgilaylik. Quyidagi belgilashni kiritamiz: Ai,j,…,t k = Aik∩ Ajk∩… ∩ Atk(i≠ j≠… ≠t).(2.1 .3) (.) formulaga asosan U mk= ∑r=0 N−m (−1)rCm+r r Sm+r,(2.1 .4) bu yerda S m + r = ∑ i < j < … < t P ( A i , j , … , tk ) . ( 2.1 .5 ) Teoremani isbotlash uchun S m + r yig‘indini aniqlash yetarli. Ai,j,…,t k hodisalar teng imkoniyatli bo‘lganligi sababli, yig‘indida C Nm + r ta qo‘shiluvchi borligi e’tiborga olinsa, (2.1.5) tenglik ushbu ko‘rinishga keladi: S m + r = C Nm + r P ( A 1 , … , m + rk ) . ( 2.1 .6 ) P(A1,…,m+r k ) ehtimolning klassik ta’rifiga ko‘ra hisoblaymiz: P ( A 1 , … , m + rk ) = n ' n . ( 2.1 .7 ) 21 Kombinatorika elementlariga asosan har bir to‘plamdagi soqqalarni qutilarga bittadan N ! usulda joylash mumkin. U holda k ta to‘plam soqqalarini qutilarga joylashtirishlarning umumiy soni n= N !∙N !∙… ∙N ! ⏟ kta = (N !)k bo‘ladi. Endi n ' ni hisoblaylik. m+r o‘rinda k karrali mos tushish hodisasi ro‘y bergan bo‘lsin. Qolgan N −m− r o‘rinda har bir to‘plamda qolgan soqqalarni ( N − m − r ) ! Usulda joylash mumkin. Demak, n ' = [( N − m − r ) !] k va (2.1.7) ushbu ko‘rinishga keladi: P ( A 1 , … , m + rk ) = [( N − m − r ) !] k ( N ! ) k . Bu ehtimolni (2.1.5) ga qo‘yib, quyidagi tenglikni hosil qilamiz: Sm+r=CNm+r[(N− m−r)!]k (N !)k . Bunga ko‘ra U mk ushbu ko‘rinishga keladi: U mk = ∑ r = 0N − m ( − 1 ) r C m + rr C Nm + r [( N − m − r ) !] k ( N ! ) k . ( 2.1 .8 ) Agar Cm+r r CNm+r= N ! r!m!(N− m−r)! tenglikni e’tiborga olsak, (2.1.8) dan (2.1.1) formula kelib chiqadi. Teoremaning ikkinchi qismini isbot qilamiz. Ma’lumki, U mk¿=∑i=m N U ik. Bunga ko‘ra (2.1.1) formulaga asosan 22 U mk¿=∑i=m N 1 i!(N !)k−1∑r=1 N (−1)r−i[(N− r)!]k−1 (r−i)! .(2.1 .9)tenglikka ega bo‘lamiz. (2.1.9) da yig‘indilar tartibini almashtiramiz, ya’ni m ≤ i ≤ N , i ≤ r ≤ N o‘rniga m ≤ r ≤ N , m ≤ i ≤ r ni qo‘yamiz. U holda (2.1.9) ushbu ko‘rinishga keladi: U mk¿=∑r=m N [(N −r)!]k−1 (N !)k−1 ∑i=m r (−1)r−i 1 i!(r−i)!. Agar ( − 1 ) r − i = ( − 1 ) r − m ∙ ( − 1 ) m − i tenglikni e’tiborga olsak, U m1k¿ = ∑r=m N (−1)r−m[(N −r)!]k−1 (N !)k−1 ∑i=m r (−1)m−i 1 i!(r−i)!(2.1 .10 ) munosabatga ega bo‘lamiz. Ikkinchi yig‘indini hisoblaylik: ∑i=m r (−1)m−i 1 i!(r−i)!= 1 r!∑i=m r (−1)m−i r! i!(r− i)!= 1 r!∑i=m r (−1)i−mCri(2.1 .11 ) Kombinatorik ayniyatlarga ko‘ra [ 3 ] quyidagi tengliklar o‘rinli: C−1k= (−1)k,∑i=0 k Cak−i∙Cbi=Ca+bk . Ushbu ayniyatlarga muvofiq (2.1.11) ushbu ko‘rinishga keladi. ∑ i = mr ( − 1 ) m − i 1 i ! ( r − i ) ! = 1 r ! C r − 1m − 1 = 1 r ( m − 1 ) !( r − m ) ! Bunga asosan (2.1.10) tenglikdan (2.1.2) formula kelib chiqadi. 23 2.2-§ . Murakkab mos tushishlar N ta raqamlangan qutilar va har biri N ta raqamlangan soqqalardan iborat n ta bir xil soqqalar guruhi berilgan bo‘lsin. Jami nN ta soqqalarni aralashtirib, tavakkaliga N tasini olamiz va qutilarga bittadan joylashtiramiz. Agar biror qutida quti soqqa raqami bir xil bo‘lsa , shu joyda murakkab mos tushish xodisasi ro‘y berdi deymiz. Ma’lumki nN ta soqqadan iborat guruhda bir xil raqamga ega bo‘lgan n ta soqqa mavjud bo‘ladi. Agar i−¿ nchi qutida mos tushish xodisasi ro‘y bergan bo‘lsa, bu qutiga raqami i bo‘lgan soqqalardan biri tushgan bo‘ladi. Teorema: Rosa m ta qutida murakkab mos tushish xodisasining ro‘y berish ehtimoli ushbu formula bilan aniqlanadi: P n , mN = 1 m ! ( nN ) ! ∑ r = mN ( − 1 ) r − m A Nr n r ( nN − r ) ! ( r − m ) ! , ( 2.2 .1 ) bu yerda ANr= N (N −1)… (N −r+1). 24 Isbot. Ai orqali i−¿ nchi qutida mos tushish hodisasi ro‘y berishni belgilaylik. U holda Pn,mN = P(¿i1<… <im¿N (Ai1∙Ai2∙… ∙Aim)).(2.2 .2) Agar Sr= ∑ i1<…<ir=1 N P(Ai1∙Ai2∙… ∙Air)(2.2 .3) belgilashni kiritsak, u holda (2.2.1) formulaga asosan P n , mN = ∑ r = mN ( − 1 ) r − m C rm S r ( 2.2 .4 ) bo‘ladi. Teoremani isbotlash uchun S r ni topish yetarli. Agar barcha ( A i 1 ∙ A i 2 ∙ … ∙ A i r ) hodisalar teng imkoniyatli ekanligi e’tiborga olinsa, ( 2.2 . 3) tenglik ushbu ko‘rinishga keladi: Sr=CNrP(A1∙A2∙… ∙Ar).(2.2 .5) Ehtimolning klassik ta’rifiga ko‘ra P(A1∙A2∙… ∙Ar)= n'' n',(2.2 .6) bu yerda n' barcha mumkin bo‘lgan va n'' hodisani ro‘yobga chiqaruvchi holatlar soni. nN soqqadan iborat guruhdan N ta soqqani C nN N usulda olish va ularni qutilarga N ! usulda joylash mumkin. Demak, mumkin bo‘lgan natijalar soni n!= CnNN ∙N !=nN (nN −1)… (nN − N +1)= AnNN (2.2 .7) bo‘ladi. Endi n'' ni topamiz. Aytaylik, A 1 ∙ A 2 ∙ … ∙ A r hodisa ro‘y bergan bo‘lsin, ya’ni birinchi r ta qutiga ularning raqamlariga mos soqqalar tushsin. U holda qolgan N −r ta qutiga guruhning qolgan nN − r ta soqqalaridan tasodifan tanlangan N −r tasi joylashadi. Agar har bir raqamli soqqa n nusxada mavjudligi e’tiborga olinsa, 25 n ' ' = n r ∙ C nN − rN − r ∙( N − r ) ! = n r A nN − rN − r . ( 2.2 . 8 ) ( 2.2 . 7) va ( 2.2 . 8) munosabatlarga ko‘ra ( 2.2 . 6) dan P(A1∙A2∙… ∙Ar)= nrAnN−r N−r AnNN tenglikka va bu tenglikka asosan ( 2.2 . 5) dan S r = C Nr ∙ n r A nN − rN − r A nNN tenglikka ega bo‘lamiz. Ushbu munosabatga ko‘ra ( 2.2 . 4) dan P n , mN = ∑ r = mN ( − 1 ) r − m C rm C Nr ∙ n r A nN − rN − r A nNN tenglikni hosil qilamiz. Bu tenglikdan ayrim soddalashtirishlardan keyin ( 2.2 . 1) formula kelib chiqadi. 26 2.3-§. Karrali murakkab mos tushishlar Faraz qilaylik, bir xil k ta to‘plam berilgan bo‘lib, har bir to‘plam bir xil n ta to‘plamostilaridan va har bir to‘plamosti bir xil 1 , … , N gacha raqamlangan soqqalardan tashkil topgan bo‘lsin, ya’ni Ai=(B1,… ,Bn),i=1,k, B j = ( a 1 , … , a N ) , j = 1 , n Shunday qilib, har bir to‘plamda nN ta soqqa mavjud bo‘lib, har bir ai(i=1,n) soqqa n ta nusxada bo‘ladi. Aytaylik, N ta 1 dan N gacha raqamlangan qutilar berilgan, Ai to‘plamlarning har biridan tasodifan N ta, jami kN ta soqqa olib qutilarga k tadan tavakkaliga joylaymiz. Agar i -qutiga joylangan barcha soqqalar i raqamli bo‘lsa, shu joyda k karrali murakkab mos tushish hodisasi ro‘y bergan deyiladi. ξN(k,n)−k karrali murakkab mos tushish hodisalari soni bo‘lsin. Ma’lumki, 0≤ξN(k,n)≤N . Quyidagi belgilashni kiritaylik. P N ( k , n , m ) = P [ ξ N ( k , n ) = m ] , m = 0,1 , … , N Teorema. Hamma m = 0 , N lar uchun quyidagi formula o‘rinli: P N ( k , n , m ) = 1 m ! [( nN ) !] k ∑ j = mN ( − 1 ) j − m P N j ∙ n jk [( nN − j ) !] k ( j − m ) ! , ( 2.3 .1 ) bu yerda P N j = N ( N − 1 ) … ( N − j + 1 ) , 1 ≤ n < ∞ , 1 ≤ k > ∞ 27 Izoh: 1.[2] ishda (k=1,n=1 da oddiy) k=2,n=1 bo‘lganida karrali va k = 1 , n = 2 da murakkab mos tushish hodisalari o‘rganilgan. (2.3.1) formuladan k va n ning tegishlicha qiymatlarida [2] ishdagi natijalar kelib chiqadi. P N ( 1,1 , m ) = 1 m ! N ! ∑ j = mN ( − 1 ) j − m P N j ( N − j ) ! ( j − m ) ! P N ( 2,1 , m ) = 1 m ! ( N ! ) 2 ∑ j = mN ( − 1 ) j − m P N j [( N − j ) !] 2 ( j − m ) ! ( 2.3 .2 ) PN(1,2 ,m)= 1 m!2N !∑j=m N (−1)j−mPNj∙2j∙(N − j)! (j−m)! .(2.3 .3) Isbot: Aii=1,N i−¿ qutida k−¿ karrali murakkab mos tushish hodisasining ro‘y berishi bo‘lsin. U holda PN(k,n,m)= P(¿i1<m<im¿N (Ai1∩ Ai2∩… ∩ Aim)).(2.3 .4) [ 2 ] (124-bet) ishdagi (3.1) formulaga va ehtimollarni qo‘shish formulasiga asosan (4) munosabat ushbu ko‘rinishga keladi. PN(k,n,m)= ∑j=m N (−1)j−mC jmCNj ∑i1<m<ij N (Ai1∩ Ai2∩ … ∩ Aij).(2.3 .5) Agar A i 1 ∙ … ∙ A i j ( i j = 1 , N ) hodisalar teng imkoniyatli ekanligini e’tiborga olsak, ( 2.3 . 5) munosabat quyidagi ko‘rinishga ega bo‘ladi: P N ( k , n , m ) = ∑ j = mN ( − 1 ) j − m C jm C N j P ( A 1 … A j ) . ( 2.3 .6 ) Ehtimolning klassik ta’rifiga ko‘ra P(A1… Aj)= n'' n'(2.3 .7) bu yerda n' mumkin bo‘lgan barcha joylashtirishlar va n''(A1… Aj) hodisa ro‘y beradigan joylashtirishlar soni. k ta to‘plamning har biridan N ta soqqani C nN N usulda olish va uni N ta qutiga N ! usulda joylash mumkin. Demak, 28 n ' =( C nNN ∙ N ! ) k = ( ( nN ) ! ( nN − N ) !) k = [ nN ( nN − 1 ) … ( N + 1 )] k . ( 2.3 .8 ) (A1… Aj) hodisa ro‘y berdi deb hisoblaylik, ya’ni 1,… ,j−¿ qutilarga k tadan tegishli raqamli soqqalar tushgan bo‘lsin. U holda qolgan N − j ta qutiga nN − j soqqadan iborat bo‘lgan to‘plamlardan N − j tadan olingan elementlar joylashtiriladi. Agar har bir element n nusxadan iboratligi va to‘plamlar k−¿ taligi e’tiborga olinsa n ' ' = [ n j ( nN − j ) … ( N − j + 1 )] k ( 2.3 .9 ) hosil bo‘ladi. ( 2.3 . 8) va ( 2.3 . 9) tengliklarga asosan ( 2.3 . 7) dan P ( A 1 … A j ) = n jk [( nN − j ) !] k [( nN ) !] k tenglik kelib chiqadi. Bunga ko‘ra ( 2.3 . 6) dan ( 2.3 . 1) hosil bo‘ladi. 29 2.4-§. Karrali tanlanma mos tushishlar Quyidagi masala qaralayotgan bo‘lsin. Har biri o‘zida N tadan elementni saqlagan k+1 ta bir xil to‘plamlar berilgan bo‘lsin. Avval birinchi to‘plamdan r ta elementni olib, elementlarning olinish tartibini qayd etamiz. Keyin qolgan k ta to‘plamning har biridan r tadan element olib, ularning olinish tartibini birinchi to‘plamdan olingan tanlanma elementlarning tartibi bilan solishtiramiz. Agar biror element barcha tanlanmalarda mavjud va bir xil vaziyatni egallagan bo‘lsa, shu element bilan k karrali tanlanma mos tushish hodisasi ro‘y berdi deymiz. 1-teorema: m o‘rinda k karrali tanlanma mos tushish hodisasining ro‘y berish ehtimoli ushbu formula bilan aniqlanadi: Pmk(r)= r! m!(ANr)k∑i=0 r−m (−1)i[(N− m−1)!] i!(r− m−1)!,(2.4 .1) bu yerda A Nr = N ∙ ( N − 1 ) ∙ … ∙ ( N − r + 1 ) . Isbot. i−¿ o‘rinda k karrali mos tushish hodisasi ro‘y berishini A i k deb belgilaylik, bu yerda 0≤i≤r . Quyidagi belgilashni kiritamiz: A i 1 , … , i mk = A i 1k ∩ … ∩ A i mk ( i 1 < i 2 < … < i m ) . U holda [2] ishdan ( 2.4 . 1) formulaga asosan P mk ( r) = ∑ i = 0r − m ( − 1 ) i C m + 1i S m + 1 , ( 2.4 .2 ) bu yerda Sm+1= ∑i1<…<im N P(Ai1,…,im+1 k ). ∆ i 1 , … , i m + 1 hodisalar teng imkoniyatli bo‘lishini e’tiborga olsak, 30 S m + 1 = C rm + 1 P ( A 1,2 , … , m + 1k ) tenglikka ega bo‘lamiz. Bunga asosan (2) P mk( r) = ∑ i = 0r − m ( − 1 ) i C m + 1i C rm + 1 P ( A 1,2 , … , m + 1k ) ( 2.4 .3 ) ko‘rinishga keladi. Ehtimolning klassik ta’rifiga ko‘ra P ( A 1,2 , … , m + 1k ) = n ' n , bu yerda n−¿ mumkin bo‘lgan barcha imkoniyatlar soni va n'−(A1,2,…,m+1 k ) hodisani tashkil etuvchi imkoniyatlar soni. N ta elementdan r tasini C Nr usulda tanlash va birinchi to‘plamdan olingan r ta element bilan r! usulda solishtirish mumkin. To‘plamlar k taligini e’tiborga olsak, n ' = ( C Nr ∙ r ! ) k = ( A Nr ) k bo‘ladi. Endi n' ni topamiz. m+1 o‘rinda mos tushish hodisasi ro‘y bergan bo‘lsin. U holda ( r − m − 1 ) ta elementni (N −m−1) ta elementdan AN−m−1 r−m−1 usulda tanlash mumkin. To‘plamlar k taligini e’tiborga olsak, n ' = ( A N − m − 1r − m − 1 ) k bo‘ladi. Demak, ( 2.4 . 4) ga ko‘ra ( 2.4 . 3) ushbu ko‘rinishga keladi: Sm+1=Crm+1(AN−m−1 r−m−1)k(ANr)−k. Bu ifodani ( 2.4 . 2) ga qo‘yib, yig‘indi ostidagi ifodani soddalashtirsak, ( 2.4 . 1) formula hosil bo‘ladi. Xususiy holda, r = N da [ 10 ] ishda olingan natijaga ega bo‘lamiz. 2-teorema: r= N da kamida m ta o‘rinda k karrali mos tushish hodisasining ro‘y berish ehtimoli quydagiga teng: P mk( N ) = 1 ( m − 1 ) !( N ! ) k − 1 ∑ j = mN ( − 1 ) j − m [( N − j ) !] k − 1 j ! ( j − m ) ! . ( 2.4 .5 ) Isbot. ( 2.4 . 1) dan r= N da quyidagi tenglikni hosil qilamiz: 31 P mk( N ) = 1( m ) !( N ! ) k − 1 ∑ i = 0N − m ( − 1 ) i[( N − m − 1 ) !] k − 1 i ! . ( 2.4 .6 ) Ehtimolning xossalariga ko‘ra Pmk(N)=∑i=m N Pik(N), yoki ( 2.4 . 6) ga asosan P mk( N ) = ∑ i = mN 1 ( i) !( N ! ) k − 1 ∑ j = 1N ( − 1 ) j − i [( N − j ) !] k − 1 j ! ( j − i ) ! ( 2.4 .7 ) tenglikka ega bo‘lamiz. Bu yerda yig‘indilar tartibini quydagicha o‘zgartiramiz: m≤i≤N va i ≤ j ≤ N o‘rniga m≤ j≤N va m ≤ i ≤ j ni qo‘yamiz. Bunga asosan ( 2.4 . 7) dan Pmk(N)= ∑j=m N [(N− j)!]k−1 (N !)k−1 ∑i=m j (−1)j−i 1 i!(j−i)!. Agar ( − 1 ) j − i = ( − 1 ) j − m ∙ ( − 1 ) m − i tenglikni e’tiborga olsak, P mk( N ) = ∑ j = mN ( − 1 ) j − m [( N − j ) !] k − 1 ( N ! ) k − 1 ∑ i = mj ( − 1 ) i − m 1 i ! ( j − i ) ! ( 2.4 .8 ) munosabatga ega bo‘lamiz. Endi ikkinchi yig‘indini hisoblaymiz: ∑ i = mj ( − 1 ) m − i 1 i ! ( j − i ) ! = 1 j ! ∑ i = mj ( − 1 ) i − m j ! i ! ( j − i ) ! = 1 j ! ∑ i = mj ( − 1 ) i − m C ji ( 2.4 .9 ) Kombinatorikaning [3] C − 1m = ( − 1 ) m va ∑ i = 0k C ak − i C bi = ( a + b k ) ayniyatlariga asosan ( 2.4 . 9) dan ∑i=m j (−1)m−i 1 i!(j−i)!= 1 j!C j−1m−1 tenglikka ega bo‘lamiz. Bunga asosan ( 2.4 . 8) munosabatdan ( 2.4 . 5) formula kelib chiqadi. 32 (2.4 . 5) ga o‘xshash formulani ixtiyoriy 1≤r≤N uchun ham hosil qilish mumkin. Bunda nisbatan murakkabroq hisoblashlar talab qilinadi. III BOB. MOS TUSHISHLAR SONLARINING KO‘P O‘LCHOVLI TAQSIMOTI 3.1- § . Ehtimollar yig ‘indisi ehtimoli formulasining ba’zi umumlashmalari Quyidagi hodisalar sistemasini qaraymiz. ¿ Faraz qilaylik, biror tajribada ushbu hodisalardan ko‘pi bilan N tasi ro‘y berishi mumkin bo‘lsin, agar ξi(i=1,k−1) ro‘y bergan ( 1 ( i ) ) tipdagi hodisalar soni bo‘lsa, ushbu shartlar bajarilsin: 33 { 0≤ξi≤N ,i=1,k−1 0≤ξ1+ξ2+… +ξk−1≤NTeorema. Tajribada m1 ta ( 1 ' ) tipdagi, m 2 ta ( 1 ' ' ) tipdagi va h.k. m k − 1 ta ( 1(k−1) ) tipdagi hodisalarning ro‘y berish ehtimoli quyidagi formula bilan aniqlanadi: P N ( m 1 , … , m k − 1 ) = ∑ r = 0m k ( − 1 ) r ∑ i 1 = 0r ∑ i 2 = 0r − i 1 … ∑ i k − 2r − i 1 − m − i k − 3 S r ( m 1 , … , m k − 1 , i 1 , … , i k − 2 ) ∙ ∏ j = 1k − r C m j + i jm j C m k − 1 + r − i 1 − … − i k − 2m k − 1 ( 3.1 .2 ) bu yerda m k = N − m 1 − … − m k − 1 , S r ( m 1 , … , m k − 1 , i 1 , … , i k − 2 ) = ¿ ¿ ∑ j ( − 1 ) , j ( k − 1 ) P A j 1 ( 1) ∙ … ∙ A j m 1 + i (1) ∙ … ∙ A j 1 ( k − 1) (k − 1 ) ∙ … ∙ A j m ( k − 1) (k − 1 )( k − 1 ) + ¿ + r − i 1 − … − i k − 2 . (1.2) munosabatdan k = 2 da [2] ishning 4-bo‘limida isbotlangan (1.3.1) formula, k=3 da esa [5] ishda isbotlangan formula kelib chiqadi. Agar ( 3.1 . 1) hodisalar o‘zaro bog‘liq bo‘lmasa va A r( i ) ∙ A r( j ) = ∅ , i ≠ j , i,j=1,k−1 hamda P ( A 1 ( i)) = P ( A 2 ( i)) = … = P ( A N ( i)) = P i , i = 1 , k − 1 , shartlar bajarilsa, ( 3.1 . 2) formuladan quyidagi taqsimot kelib chiqadi: P N ( m 1 , m 2 , … , m k − 1 ) = N ! m 1 ! m 2 ! … m k ! P 1m 1 P 2m 2 … P km k bu yerda Pk=1− P1−… − Pk−1. Teoremaning isboti: Teoremani qo‘shib va chiqarib tashlash metodi yordamida isbot qilamiz. Ω = ( ω ) elmentar hodisalar fazosi va G = ( ξ 1 = m 1 , ξ 2 = m 2 , … , ξ k − 1 = m k − 1 ) bo‘lsin. U holda ehtimolning xossasiga ko‘ra P N ( m 1 , m 2 , … , m k − 1 ) = P ( G ) = ∑ ω G ϵ P ( ω ) bo‘ladi. Ushbu tenglikdan ko‘rinadiki, agar ( 3.1 . 2) formulaning o‘ng tomoni G -ga tegishli elementar hodisalar ehtimollari bo‘yicha yoyilsa, bu 34 ehtimollarning koefsientlari birga teng bo‘lishi kerak. Demak, teoremani isbotlash uchun ixtiyoriy ω Gϵ elementar hodisaning ehtimoli ( 3.1 . 2) tenglikning o‘ng tomoniga birga teng koefsient bilan kirishini ko‘rsatish yetarli. Faraz qilaylik, ω0Gϵ elementar hodisa ( 3.1 . 1) tenglamadagi hodisalardan n 1 tasining va hakozo. ( 1 ( k − 1 ) ) tenglamadagi hodisalardan nk−1 tasining tarkibiga kirsin. a ( n , m ) orqali P(ω0) ehtimolning koefsientini belgilaylik, bu yerda. n= n1+n2+… +nk−1, m=m1+m2+… +mk−1. ( 3.1 . 2) tenglikdan quyidagiga ega bo‘lamiz: a ( n , m ) = ∑ r = 0n − m ( − 1 ) r ∑ i 1 = 0r … ∑ i k − 1 = 0r − i 1 − … − i k − 2 ∏ j = 1k − 2 C m j + i jm j ∙ ∙ C n jm j + i j ∙ C m i − 1 + r − i 1 − … − i k − 2m k − 1 ∙ C n k − 1m i − 1 + r − i 1 − … − i k − 2 . ( 3.1 .3 ) Agar Cnm= n! m!(n−m)! ekanligi e’tiborga olinsa, quyidagi tenglik to‘g‘riligiga ishonch hosil qilish mumkin: C m j + n jm j ∙ C n jm j + n j = C n jm j ∙ C n j − m ji j . Bunga ko‘ra ( 3.1 . 3) dan ushbu tenglikka ega bo‘lamiz: a ( n , m ) = ∏ j = 1k − 1 C n jm j ∙ C n j − m ji j ∑ r = 0n − m ( − 1 ) r ∑ i 1 = 0r … ∑ i k − 2 = 0r − i 1 − … − i k − 3 ∏ j = 1k − 2 C n j − m ji j ∙ C n k − 1 − m k − 1r − i 1 − … − i k − 2 . Ma’lumki, (∏j=1 k−2 Cnj−mj ij ∙Cnk−1−mk−1 r−i1−…−ik−2 )∙(C¿¿n−mr)−1(3.1 .4 )¿ gipergeometrik taqsimotning umumlashmasidir. Demak , ( 3.1 . 3) ning i1,i2,… ,ik−1 o ‘ zgaruvchilarining mumkin bo ‘ lgan qiymatlari bo ‘ yicha yig ‘ indisi birga teng , ya ’ ni 35 ∑ i 1 = 0r … ∑ i k − 2 = 0r − i 1 − … − i k − 3 ∏ j = 1k − 2 C n j − m ji j ∙ C n k − 1 − m k − 1r − i 1 − … − i k − 2 = C n − mr Bu tenglikka ko‘raa(n,m)=∏j=1 k−2 Cnj mj∙Cnk−1 mk−1∑r=0 n−m (−1)rCn−mr . Agar Cn0=1(n≥0) deb qabul qilinishi e’tiborga olinsa, yuqoridagi tenglikdan ko‘rinadiki, n 1 = m 1 , … , n k − 1 = m k − 1 da n= m va a(n,m)=∏j=1 k−2 Cnj mj∙Cnk−1 mk−1∑r=0 0 (−1)rC0r=1, boshqa hollarda, ya’ni n<m da ∑ r = 0n − m ( − 1 ) r C n − mr = ( 1 − 1 ) n − m = 0 va a(n,m)=0. Teorema isbot bo‘ldi. 36 3.2- § . Karrali mos tushishlar sonining birgalikdagi taqsimoti Har biri birdan N gacha raqamlangan N ta soqqadan iborat k ( k ≥ 1 ) guruh soqqalar berilgan bo‘lsin. Avval birinchi guruh, keyin ikkinchi guruh va h.k. k − ¿ guruh soqqalarni raqamlangan N ta qutiga bittadan joylaymiz. Agar biror qutida quti raqami bilan shu qutiga tushgan i ta soqqa raqami bir xil bo‘lsa, shu o‘rinda i(1≤i≤k) karrali mos tushish hodisasi ro‘y berdi deb ataymiz. Teorema: m 1 o‘rinda bir karrali , m 2 o‘rinda ikki karrali va h.k. mk o‘rinda k karrali mos tushish hodisalarining ro‘y berish ehtimoli quyidagi formula bilan aniqlanadi: PN(m1,m2,… ,mk)= 1 m1!,… ,mk!(N !)k−1∑r=0 m0 (−1)r∑i1=0 r ∑i2=0 r−i1 … ∑ik−1=0 r−i1−…−ik−2 ∙ ∙ A r ( m 1 , … , k k − 1 , i 1 , … , i k − 1 ) i 1 ! , … , i k − 1 ! ( r − i 1 − … − i k − 1 ) !( m 0 − r ) ! , ( 3.2 .1 ) bu yerda m0= N− m1−… − mk , Ar(m1,… ,kk−1,i1,… ,ik−1)=¿ ¿ ∑ j 1 = 0m 1 + i 1 ∙ … ∙ ∑ j k − 1m k − 1 + i k − 1 ∏ n = 1k − 1 [ m k − r + ∑ ϑ = 1n ( m ϑ − j ϑ − i ϑ )]( m 0 − r + j 1 + … + j k − 1 ) ! C m n + i nj n . Isbot. Teoremani isbotlash uchun ehtimollarni qo‘shish formulasining ushbu umumlashmasidan foydalanamiz. Agar A1(1),A2(1),… ,AN(1) − − − − − − ¿ A 1 ( k) , A 2 ( k) , … , A N ( k) 37 hodisalar guruhlari berilgan bo‘lsa, tajribada birinchi guruh hodisalardan m1 tasining va h.k. k − ¿ guruh hodisalardan m k tasining ro‘y berish ehtimoli ushbu formula yordamida hisoblanadi: P N ( m 1 , m 2 , … , m k ) = ∑ r = 0m 0 ( − 1 ) r ∑ i 1 = 0r ∑ i 2 = 0r − i 1 … ∑ i k − 1 = 0r − i 1 − … − i k − 2 ∙ ∙ S r ( m 1 , … , m k , i 1 , … , i k − 1 ) ∙ ∏ j = 1k − 1 C m j + i jm j C m k + r − i 1 − … − i k − 1m k , bu yerda 0≤mi≤N ,i=1,k,0≤m1+… +mk≤N ,m0= N−m1−… −mk Sr(m1,… ,mk,i1,… ,ik−1)= ¿ ¿ ∑j(1),…,j(k)P(Aj1(1)(1)∙… ∙Ajm1+i1(1)(1)∙… ∙Aj1(k)(k)∙… ∙Ajmk+r−i1−…−ik−1 (k)(k) ). Ushbu formuladagi S r ( m 1 , … , m k , i 1 , … , i k − 1 ) ni topamiz. Agar {Aj1(1)∙… ∙Amk+r−i1−…−ik−1} hodisalar teng imkoniyatli ekanligi e’tiborga olinsa, quyidagi tenglikka ega bo‘lamiz: S r ( m 1 , … , m k , i 1 , … , i k − 1 ) = C Nm 1 + i 1 ∙ C N − m 1 − i 1m 2 + i 2 ∙ … ∙ C N − m 1 − … − m k − 1 − ¿ i 1 − … − i k − 1m k + r − i 1 − … − i k − 1 ∙ ¿ ∙ P ( A 1 ( 1) ∙ … ∙ A m 1 + i 1 (1) ∙ … ∙ A 1 ( k) ∙ … ∙ A m k + r − i 1 − … − i k − 1 (k) ) ( 3.2 .2 ) (2) tenglikdagi P(A1(1)∙… ∙Am1+i1 (1) ∙… ∙A1(k)∙… ∙Amk+r−i1−…−ik−1 (k) ) ehtimolni hisoblash uchun ehtimolning klassik ta’rifidan foydalanamiz: P ( A 1 ( 1) ∙ … ∙ A m 1 + i 1 (1) ∙ … ∙ A 1 ( k) ∙ … ∙ A m k + r − i 1 − … − i k − 1 (k) ) = m n . Har bir guruh soqqalarni N ta qutiga bittadan N ! usulda joylash mumkin. Agar guruhlar k taligi e’tiborga olinsa , n=(N !)k bo‘ladi. Endi m ning qiymatini hisoblaymiz. Faraz qilaylik, m1+i1 o‘rinda bir karrali, m 2 + i 2 o‘rinda ikki karrali va h.k. m k + r − i 1 − … − i k − 1 o‘rinda k karrali mos tushish hodisalari ro‘y bergan bo‘lsin. Agar bir karrali mos tushishlar faqat birinchi guruh elementlari hisobidan va h.k. k karrali mos 38 tushishlar 1,2 ,… ,k−¿ guruh elementlari hisobidan ro‘y bergan bo‘lsa, u holda bunday holatlar soni C m 1 + i 10 … C m k − 1 + i k − 10 ( m 0 − r ) !( m 0 + r + i 1 ) ! … ( m 0 + … + m k − 1 − r + i 1 + … + i k − 1 ) ! bo‘ladi. Agar bir karrali va h.k. k karrali mos tushishlar har xil guruhlar elementlari hisobidan ro‘y berishi mumkinligi e’tiborga olinsa, umumiy holda ushbu ifodaga ega bo‘lamiz: C m 1 + j 1j 1 ∙ … ∙ C m k − 1 + i k − 1j k − 1 ∙ ( m 0 − r + j 1 + … + j k − 1 ) !( m 0 + m 1 − r − j 1 + i 1 ) ! ∙ ∙(m0+m1+m2−r− j1− j2+i1+i2)!… (m0+… +mk−1−r− j1−… −− jk−1+i1+… +ik−1)! ( 3.2 . 3) bu yerda j1 i−¿ guruhdagi birorta ham elementi mos tushishlarda qatnashmaydi- gan elementlar soni. ( 3.2 . 3) ifodaning ji lar ( 1 ≤ i ≤ k − 1 ) bo‘yicha yig‘indisini olib, quyidagi munosabatni hosil qilamiz: Ar(m1,… ,mk−1,i1,… ,ik−1)= ¿ ¿∑j1=0 m1+i1 … ∑jk−1=0 mk−1−ik−2 Cm1+j1 j1 … Cmk−1+ik−1 jk−1 (m0− r+j1+… + jk−1)!(m0+m1−r− j1+i1)!∙ ∙(m0+m1+m2−r− j1− j2+i1+i2)!… (m0+… +mk−1−r− j1−… −− jk−1+i1+… +ik−1)!= m ( 3.2 . 4) ( 3.2 . 4) ga asosan P(A1(1)∙… ∙Am1+i1 (1) ∙… ∙A1(k)∙… ∙Amk+r−i1−…−ik−1 (k) )= Ar(m1,… ,mk−1,i1,… ,ik−1) (N !)k bo‘ladi. Ushbu ifodani ( 3.2 . 2) ga qo‘yib, quyidagi tenglikni hosil qilamiz: Sr(m1,… ,mk,i1,… ,ik−1)= ¿ ¿ C Nm 1 + i 1 C N − m 1 − i 1i 2 … C N − m 1 − … − m k − 1 − i 1 − … − i k − 1m k + r − i 1 − … − i k − 1 ∙ A r ( m 1 , … , m k − 1 , i 1 , … , i k − 1 ) ( N ! ) k . 39 Bunga asosan ehtimollarni qo‘shish formulasining umumlashmasidan ushbu ifodani hosil qilamiz:PN(m1,… ,mk)=∑r=0 m0 (−1)r∑i1=0 r ∑i2=0 r−i1 … ∑ik−1=0 r−i1−…−ik−2 ∏j=1 k−1 Cmj+ij mj Cmk+r−i1−…−ik−1 mk ∙ CNm1+i1CN−m1−i1 m2+i2 … CN−m1−…−mk−1−i1−…−ik−1 mk+r−i1−…−ik−1 ∙Ar(m1,… ,mk−1,i1,… ,ik−1) (N !)k .(3.2 .5) Ayrim soddalashtirishlardan keyin ([2], [3]) hosil qilamiz: ∏ j = 1k − 1 C m j + i jm j C m k + r − i 1 − … − i k − 1m k ∙ C Nm 1 + i 1 C N − m 1 − i 1m 2 + i 2 … C N − m 1 − … − m k − 1 − i 1 − … − i k − 1m k + r − i 1 − … − i k − 1 = ¿ ¿ [( m 0 − r ) !] − 1 ∙ N ! m 1 ! … m k ! i 1 ! … i k − 1 ( r − i 1 − … − i k − 1 ) ! . Ushbu tenglikka ko‘ra ( 3.2 . 5) dan teoremaning isboti kelib chiqadi . ( 3.2 . 1) formula k=1 va k=2 da ushbu nisbatan sodda ko‘rinishga ega bo‘ladi . P N ( m 1 ) = 1 m 1 ! ∑ r = 0N − m 1 ( − 1 ) r 1 r ! P N ( m 1 , m 2 ) = ¿ 1 m 1 ! m 2 ! N ! ∑ r = 0m 0 ( − 1 ) r ∑ i = 0r ∑ k = 0m i − i C m 1 + ik ( m 0 − r + k ) !( m 0 + m 1 − r − k − i ) ! i ! ( r − i ) !( m 0 − r ) ! bu yerda m 0 = N − m 1 − m 2 40 XULOSA Mazkur ishda qaralgan mos tushishlar haqidagi masalaning dastlabki variantlari XVIII asrning ikkinchi yarmida Monmort, Laplas, Gyugenslar tomonidan yechilib, ayrim tadbiqlari qaralgan edi. Keyinchalik XX asr o‘rtalarida Feller ushbu masalaning birmuncha murakkab variantlarini ko‘rsatib berdi. Karrali mos tushishlar, murakkab mos tushishlar haqidagi masala ham Feller tomonidan qo‘yilgan masalalar yechilib, ular umumlashtiriladi, ya’ni karrali murakkab mos tushishlar sonining taqsimoti topiladi. Shuningdek, ishda tanlanma mos tushishlar haqidagi masala, mos tushishlar sonining ko‘p o‘lchovli taqsimoti topiladi. Bu taqsimotni topishda ehtimollarni qo‘shish formulasining umumlashmasi talab qilinganligi sababli, 41 ushbu umumlashma topilib, tadbiq etiladi. Dissertatsiya ishida keltirilgan yangi natijalar quyidagilar: 1. Karrali murakkab mos tushishlar sonining taqsimoti. Ushbu taqsimotdan xususiy holda V.Bozorov va H.Qurbonovlarning karrali va murakkab mos tushishlar soni uchun olingan natijalari kelib chiqadi. 2. Karrali tanlanma mos tushishlar sonining taqsimoti ushbu natijadan xususiy holda karrali mos tushishlar sonining taqsimoti kelib chiqadi. 3. Ehtimollarni qo‘shish formulasining ko‘p o‘lchovli umumlashmasi. 4. Mos tushishlar sonlarining ko‘p o‘lchovli taqsimoti. Bu bo‘yicha ko‘p o‘lchovli taqsimotlar biror muallif tomonidan o‘rganilganligi ushbu muallifga ma’lum emas. Dissertatsiya mavzusi bo‘yicha quyidagi yo‘nalishlar bo‘yicha davom ettirish mumkin: 1. Olingan natijalarning ommaviy xizmat ko‘rsatish sistemalariga tegishli jarayonlarni o‘rganishga tadbiq qilish. 2. Olingan taqsimotlarning asimptotik holatlarini o‘rganish. 3.K o‘lchovli karrali murakkab mos tushishlar sonining taqsimotini topish. 4. Olingan natijalarning kvantlar nazariyasiga tadbiqini o‘rganish. 5. Olingan natijalarning mayda zarrachalar fizikasiga tadbiqini o‘rganish. 6. Olingan natijalarning biologik jarayonlarni o‘rganishga tadbiq qilish. Mazkur dissertatsiyada olingan natijalar ko‘plab sohalar bo‘yicha olingan natijalarni matematik asoslash, shuningdek, ma’lum natijalardan ayrimlarini nisbatan sodda usullarda olish imkonini beradi. 42 FOYDALANILGAN ADABIYOTLAR 1. Гнеденко Б. B . Курс теори вероятностей, Москва, ,,Наука’’ 1989 г. 2. Феллер В. Введение в теорию вероятностей и ее приложенения М:Мир, 1984 г. 3. Хол М. Комбинаторика, М:Мир, 1973 г. 4. A.Abdushukurov, T.Zuparov Ehtimollar nazariyasi va matematik statistika. Toshkent-2015. 43 5. Курбонов Х.К. Асимптот еский анализ числа сложнах и кратнах совподений. сб.тр. СамГУ. Вопроса математ еского анализа и его приложения, 1984 г. 6. Sirojiddinov.S.X, Mamatov M.M ehtimollar nazariyasi va matematik statistika. Toshkent-1980. 7. Курбонов Х. Одно обобщение формулы сложения вероятностей , Сб. СамГУ ,,В ислителъные алгоритмы прикладной математики’’, 1987 г. 8. И.Н.Коваленко, А.А.Филлиппова. Теори вероятностей математ еская статистика , ,,Высщая щкола’’, ,,Наука’’ 1973 г. 9. Qurbonov H. Totliyev O‘. Ehtimollarni qo‘shish teoremasining umumlashmasi, Magistrantlar ilmiy konferensiyasi materiallari, Samarqand 2018 y. 10. Qurbonov H. Totliyev O‘. Karrali murakkab mos tushishlar, Magistrantlar ilmiy konferensiyasi materiallari, Samarqand 2018 y. 11. Qurbonov H. Totliyev O‘. Karrali tanlanma mos tushish hodisalari, International conference, Mathematical analysis and its application to mathematical physics, Samarkand-2018 12. Qurbonov H. Totliyev O‘. Mos tushishlar sonlarining ko‘p o‘lchovli taqsimoti haqida, Respublika ilmiy-nazariy anjumani materiallari, Nukus 2019 y 13. http:/www.ziyonet.uz 14. http:/www.Mathedu.ru/journals.collections/. 15. http:/www.edu.uz 16. http:/ru.wikipedia.org 44

KOMBINATORIKA MASALALARINING EHTIMOLLAR NAZARIYASI MASALALARINI YECHISHGA TADBIG‘I ANNOTATSIYA Mazkur magistrlik dissertatsiyasida M arkov zanjirlari va ularning turli sohalarda masalan o‘yinlar nazariyasi, ommaviy xizmat ko‘rsatish nazariyasida qo‘llanishi ning nazariy asoslari va usullari qarab chiqiladi. Markov zanjirlari va ularning xossalarining amaliy masalalarini yechishga tadbiqiga oid misol va masalalar tahlil qilingan . ANNOTATION This master's work deals with the theoretical foundations and methods of Markov chains and their application in various fields, such as game theory, queuing theory. Examples and problems related to the use of Markov chains and their properties for solving practical problems are analyzed. Ilmiy rahbar do t s. H. Qurbonov Magistrant N. Mirsanov MUNDARIJA Kirish ………………………………………………………………… 3 I BOB. KOMBINATORIKA ELEMENTLARI VA HODISALAR YIG‘INDISINING EHTIMOLI 1.1-§ . Kombinatorikaning asosiy elementlari……………………………. 5 1.2- § . Hodisalar yig ‘ indisining ehtimoli………………………………… 13 1.3- § . Berilgan hodisalardan ma’lum sondagisining ro ‘y berish 1

ehtimoli………………………………………………. …………. 18 II BOB. KARRALI, MURAKKAB VA TANLANMA MOS TUSHISHLAR 2.1-§ . Karrali mos tushish hodisalari haqidagi masala…………………. 21 2.2- § . Murakkab mos tushishlar ………………………………………. 25 2.3- § . Karrali murakkab mos tushishlar ………………………………. 28 2.4- § . Karrali tanlanma mos tushishlar……………………………….... 31 III BOB. MOS TUSHISHLAR SONLARINING KO‘P O‘LCHOVLI TAQSIMOTI 3.1- § . Ehtimollar yig ‘indisi ehtimoli formulasining ba’zi umumlashmalari..35 3.2- § . Karrali mos tushishlar sonining birgalikdagi taqsimoti…….……. 39 Xulosa …………………………………………………………………… 44 Foydalanilgan adabiyotlar …...…………………………………………. 46 KIRISH 1. Mavzuning dolzarbligi. Kombinatorika matematikaning eng muhim bo ‘ limlaridan biri bo ‘ lib, ehtimollar nazariyasi, sonlar nazariyasi, guruhlar nazariyasi, matematik statistika, o ‘ yinlar nazariyasi va shunga o ‘ xshash ko ‘ plab sohalarga tegishli zamonaviy muomolarni hal qilishda katta ro ‘ l o ‘ ynaydi. Shuningdek, kombinatorika elementlari jadvallar tuzish ishlarida, transport masalalarini hal qilishda, ishlab chiqarishni rejalashtirishda keng qo ‘ llaniladi. 2

Kombinatorika masalalari bilan birinchilardan bo ‘ lib XVI asrda Italyan matematigi Tartaliya shug ‘ ullangan bo ‘ lib, u hal qilgan muommolar qimor o ‘ yinlari bilan bog ‘ liq edi. Chunki bu davrda yuqori tabaqalar hayotida qimor o ‘ yinlari katta o ‘ rin tutgan. Kombinatorikaning keyingi rivoji XVII asr matematiklari-fransuz olimlari Paskal va Ferma nomlari bilan bog ‘ liq. Keyinchalik esa bu sohada M.Bernulli, Leybnik va Eyler kabi olimlar ham tadqiqot ishlarini olib borishgan. Oxirgi yillarda kombinatorika tez suratlar bilan rivojlana boshladiki, bu hozirgi paytda deskrit matematika, matematik statistika va ehtimollar nazariyasining deyarli barcha sohalariga tadbiq etilishning kuchayishi bilan izohlanishi mumkin. Biroq shunga qaramasdan oliy matematika dasturlarisiz kombinatorikaga yetarlicha o ‘ rin ajratilmagan, o ‘ zbek tilida adabiyotlar deyarli yo’q. Rus tilida ham sanoqli, aksariyat adabiyotlar horijiy olimlar kitoblarining tarjimasidan iborat. Shu sababli kambinatorika elementlarining ehtimollar nazariyasi masalalarini yechishga tadbiqini tahlil qilish zaruriyati tug ‘ uldi. Ushbu magistrlik desertatsiyasida kombinatorika elementlari va ularning matematikaning boshqa sohalariga tadbiqi xususan shvet matematigi Mokmort tomonidan qo ‘ yilgan ‘‘ Mos tushushlar haqidagi masala’’ning qator variantlarining yechimlari o ‘ z aksini topgan. 2. Masalaning qo ‘ yilishi 1) Kombinatorika elementlari va ularga doir ayniyatlarni tahlil etish. 2) Mos tushushlar sonining ko ‘ p o ‘ lchovli taqsimotlarini aniqlash, ularning asimtotik holatlarini tahlil qilish. 3) Olingan natijalarni ommaviy xizmat ko ‘ rsatish nazariyasi masalalarini yechishga tadbiq etish. 3. Tadqiqot obyekti va predmeti. Tadqiqot obyekti kombinatorikaning asosiy elementlari va uning tadbiqlari, tadqiqot predmeti esa mos tushushlar 3

haqidagi masalaning asosiy variantlari va uning yechimlarini asimtotik tahlil qilish hisoblanadi. 4. Tadqiqot maqsadi va vazifalari. Tadqiqot maqsadi kombinatorika elementlarini ehtimollar nazariyasi masalalarini yechishga tadbiq etish bo ‘ lib, shu maqsadda quyidagi ishlarni amalga oshirish vazifasi belgilandi; 1) Kombinatorikaning asosiy elementlarini tahlil qilish, 2) Karrali mos tushushlar sonining taqsimotini aniqlash, 3) Murakkab mos tushushlar sonining taqsimotini aniqlash, 4) Karrali va murakkab mos tushushlar haqidagi masalani umumlashtirish, 5) Tanlanma mos tushushlar haqidagi masalani yechish. 5. Umumiy yangilik. Ko ‘ p o ‘ lchovli karrali murakkab mos tushushlar sonining taqsimoti topildi. Shunungdek ko ‘ p karrali tanlanma mos tushushlar sonining taqsimoti aniqlandi. 6. Tadqiqot natijalarining ilmiy axamiyati. Ishda olingan natijalar malum natijalarning ko ‘ p o ‘ lchovli xili uchun umumlashmalari bo ‘ lib, taqsimotlarning asimtotik xolatlari birinchi marta taxlil qilinmoqda. Ushbu natijalar mos tushushlar haqidagi masalalarning nisbatan murakkab variantlarini o ‘ rganish uchun mo ‘ ljal bo ‘ lib xizmat qiladi. 7. Ishning amaliy axamiyati. Ushbu ishda qaralgan masala sxematik xarakterga ega bo ‘ lib, ko ‘ plab real masalalarni (ommaviy xizmat ko ‘ rsatish sistemalari, mayda zarrachalar fizikasi, sof ko ‘ payish jarayonlari va boshqalar) shu sxemaga keltirish yoki yaqinlashtirish mumkin. 8. Ilmiy tadqiqot metodlari. Ushbu ishda kombinatorika va ehtimollar nazariyasining umumiy tadqiqot metodlari bilan bir qatorda matematik induksiya, elementar hodisa ehtimolini qo ‘ shish va ajratib olish metodlaridan keng foydalanildi. 4

9. Ishning tuzilishi. Ish kirish qismi va uchta bobga birlashtirilgan oltita paragraf, xulosa va foydalanilgan adabiyotlar qismlaridan iborat. Bibliografiyada 1 ta monagrafiya, 4 ta darslik, 5 ta ilmiy maqolalar jami 10 ta adabiyot ro ‘ yxati keltirilgan. Ish 52 betdan iborat. 10. Ishning qisqacha mazmuni. I- bob ikkita paragrifdan iborat bo ‘ lib, kombinatorika oid va ishda bevosita qo ‘ llanilgan malumotlar, xodisalar yig ‘ indisining extimoli va uning umumlashmalari berilgan. II-bobga karrali, murakkab va murakkab karrali mos tushushlar bo ‘ yicha olingan natijalar keltiriladi. III − ¿ bob ehtimollarni qo‘shish teoremasining umumlashmasi, mos tushishlar sonlarining ko‘p o‘lchovli taqsimoti, mos tushishlar sonining sonli harakteristikalarini hisoblash, murakkab karrali mos tushishlar soni taqsimot qonunining parametrlarining ( N − ¿ yacheyka yoki qutilar soni, K − ¿ zarracha yoki sharchalar partiyalari soni, n−¿ har bir partiyadagi zarrachalar to‘plami soni) turli o‘zgarishlardagi asimptotik holatlari qaralgan. Xulosa qismida dissertatsiya ishida qaralgan masalalarning ahamiyati, tadbiq sohalari, olingan asosiy natijalar va qo‘llanilgan tadqiqot metodlari, shuningdek, ishni davom ettirish yo‘nalishlari haqida ma’lumotlar berilgan. I BOB. KOMBINATORIKA ELEMENTLARI VA HODISALAR YIG‘INDISINING EHTIMOLI 1.1 - § . Kombinatorikaning asosiy elementlari 5

O'xshashlar

GRAFLAR NAZARIYASI ELEMENTLARI VA ULARNING MASALALAR YECHISHGA TADBIQLARI
Ko’p o’zgaruvchili funksiyalarning optimallashtirish masalalarini yechishga qo’llashning matematik modelini qurish.
Kombinatorika va kiriptografiya masalalari
Kombinatorika KURS ISHI
EHTIMOLLARNI QO‘SHISH FORMULASI VA UNING UMUMLASHMALARI