Mavzu: Kombinatorika elementlari

Mavzu: Kombinatorika elementlari
Reja
1. Kombinatorikaning asosiy qoida va formulalari.
2. O‘rinlashtirishlar, o’rin almashtirishlar, birikmalar.
Tayanch tushunchalar: kombinatorika elementlari, kombinatorikaning asosiy qoida va teoremalari, guruhlashlar va o‘rinlashtirishlar, birikmalar, elementlar, takrorlanuvchi o’rinlashtirishlar, takrorlanuvchi guruhlashlar.
Ob’yektlarni tanlash va ularni ma’lum tartibda joylashtirish kabi matematik masalalar har doim insonni qiziqtiriradigan sohalardan hisoblangan.
Kombinatorika – bu matematikaning chekli to‘plam elementlarini berilgan qoidalar asosida tanlash va joylashtirish bilan bog‘liq masalalarni yechish usullarini o‘rganuvchi bo‘limdir.
Kombinatorika tarixiga nazar tashlasak, bir necha ming yil avval Xitoyda sehrli kvadratlar tuzish, qadimgi Yunonistonda figurali sonlar nazariyasini tuzish masalasini o‘rganishgan. Kombinatorika masalalari Samarqanddagi Ulug‘bek maktabining taniqli matematigi G’iyosiddin Jamshid Koshiy, X asrda yashab ijod etgan Umar Xayyom, keyinchalik Evropa olimlari jumladan, B.Paskal, J.Kordano, G.Leybnits, Ya.Bernulli, P.Ferma, L.Eyler va boshqa olimlarning ishlarida uchraydi. Kombinatorikaning asosiy qoida va formulalari. A debchekli A to‘plam elementlari sonini belgilaymiz. Kombinatorikada sodda, o‘z-o‘zidan ravshan bo‘lgan, ammo muhim qoidalar bor. Bunday qoidalar sifatida jamlash, ko‘paytirish hamda kiritish va chiqarish qoidalari deb ataluvchi qoidalarni ko‘rsatish mumkin. Qo‘shish (jamlash) qoidasi: Agar A to‘plam n ta elementdan, B to‘plam esa m ta elementdan iborat bo‘lib, bu ikki to‘plam o‘zaro kesishmasa, u holda A va B ning barcha elementlaridan iborat A B to‘plam n +m ta elementga ega, ya’ni | | | | | | A B A B   Qo’shish qoidasi bilan A va B to‘plamlar o‘zaro kesishganda ham A B to‘plam elementlari nechtaligini hisoblash mumkin. Bunda quyidagi kiritishchiqarish qoidasio‘rinli: | | | | | | | | A B A B A B    Ravshanki, bu tenglikdan foydalanib | | A , | | B , | | A B va | | A B miqdorlarning ixtiyoriy uchtasi ma’lum bo‘lganda to‘rtinchisini hisoblash mumkin. Misol. 50 ta talabadan 40 tasiingliz tilini, 25 tasi esa nemis tilini o‘rganmoqdalar. Ikkala tilni ham o‘rganayotgan talaba nechta? Yechilishi. Ingliz tilini o‘rganayotgan talabalar to‘plamini A orqali, nemis tilini o‘rganayotgan talabalar to‘plamini B orqali belgilaymiz. Ma’lumki, | | A B = 50, | | A = 40, | | B =25. U holda ikkala tilni ham o‘rganayotgan talabalar A B to‘plamni tashkil qilib, kiritish-chiqarish formulasidan | | A B =| | A + | | B -| | A B =15. Ko‘paytirish qoidasi: Ñ a b a A b B      { , | , } ko‘rinishdagi to‘plam uchun | | | | | | C A B   Eslatma. Yuqorida bayon qilingan ikkita to‘plam uchun qo‘shish, ko‘paytirish hamda kiritish - chiqarish qoidalarini chekli sondagi istalgan chekli to‘plamlar uchun umumlashtirish mumkin. Masalan, uchta chekli A B C , , to‘plamlar uchun A B C A B C       A B A C B C  A B C kiritish - chiqarish qoidasi o‘rinli. Misol. 40 nafar turistdan 20 nafariingliz tilini, 15 nafari fransuz tilini, 11 nafari esa ispan tilini biladilar.Ingliz va fransuz tillarini etti nafar turist, ingliz va ispan tillarini besh nafar turist, fransuz va ispan tillarini esa uch nafar turist biladi. Ikki nafar turist uchta tilni bilgani ma’lum bo‘lsa, turistlar ichida nechtasi shu uchta tildan birortasini ham bilmaydi? Yechilishi. Ingliz tilini biladigan turistlar to‘plamini E deb, frantsuz tilinibiladigan turistlar to‘plamini F deb, ispan tilini biladigan turistlar to‘plamini esa I deb belgilaymiz. U holda | | E  20, | | F  15, | | I  11, E F  7 , E F  5, I F  3, E F I  2. Dastlab kamida bitta tilda gaplashadigan turistlar sonini topamiz: E F I E F I       E F E I F I   E F I         20 15 11 7 5 3 2 33 Demak, 40 33 7   nafar turist shu uchta tildan birortasini ham bilmaydi. O‘rinlashtirishlar, o’rin almashtirishlar, birikmalar. Predmetlardan tashkil topgan tuzilmalar kombinatsiyalardeb ataladi. Uch xil turdagi kombinatsiyalar o‘rganiladi: o‘rin almashtirish, o‘rinlashtirish va birikmalar. O’rinlashtirishlar A alfavit n ta belgidan tashkil topgan bo‘lsin. Uzunligi m ga teng bo‘lgan so‘zlar (ya’ni uzunligi m ga teng bo‘lgan ketma-ketliklar) sonini sanab chiqaylik. Har bir so‘zni tashkil etgan belgilar orasidagi takrorlanadiganlari bor bo‘lgan holda bunday so‘zlar sonini m A n ( n ta elementdan m tadantakrorli o‘rinlashtirishlar soni), bu belgilarning barchasi har hil bo‘lgan holda (takrorsiz o‘rinlashtirishlar soni ) deb belgilaymiz. Bu ikki miqdor uchun formulalar quyidagicha: , . Bu yerda (n – faktorial deb o‘qiladi) Endi uzunligi dan ko‘p bo‘lmagan so‘zlar sonini sanab chiqaylik. Bunda qo’shish (jamlash) qoidasiga ko‘ra so‘zlarni tashkil etgan belgilar orasidagi takrorlanadiganlari bor bo‘lgan holda bunday so‘zlar soni ga, bu belgilarningbarchasi har hil bo‘lgan holda ga teng. Misol. 1)20 ta belgidan tashkil topgan alfavit berilgan bo‘lsin. Uzunligi 3 ga teng bo‘lgan so‘zlar sonini sanab chiqaylik. Bunda belgilarning barchasi takrorlanmasin. Yechilishi. 2) 20 ta belgidan tashkil topgan alfavit berilgan bo‘lsin. Uzunligi 3 ga teng bo‘lgan so‘zlar sonini sanab chiqaylik. Bunda belgilarning ayrimlari takrorlanishi mumkin. Yechilishi. . ■ O’rin almashtirishlar. ta elementli o‘rin almashtirishlar deb, bir-biridan faqat elementlarining tartibi bilan farq qiladigan ta elementli birikmalarga aytiladi. Masalan, 3 ta elementdan 6 ta o‘rin almashtirish bajarish mumkin: . ta elementli o‘rin almashtirishlar soni quyidagi formula yordamida hisoblanadi: Misol.1)Afsuski, bugun, yomg‘ir, yog‘adi so‘zlaridan nechta gap tuzish mumkin? Yechilishi. . ■ 2)w,e,d,i,g,m,a,t,h harflarining “we”,”dig”,”math” so‘zlaridan hech qaysisini o‘z ichiga olmagan barcha o‘rin almashtirishlar nechta? Masalan, d,g,i,w,e,t,h,m,a shu shartni qanoatlantirmaydi. Yechilishi. Barcha o‘rin almashtirishlar soni ga teng. “we” so‘zini o‘z ichiga olmagan barcha o‘rin almashtirishlar to‘plamini ,”dig” so‘zini o‘z ichiga olmagan barcha o‘rin almashtirishlar to‘plamini m A n m m A n n  ! ( 1)( 2)....( 1) ( )! m n n A n n n n m n m        n n ! 1 2 3 ... , 0! 1       m 0 1 2 2 3 0 ... 1 ... n k m m n n n n n k A A A A A n n n n              0 1 2 0 ... n k m n n n n n k A A A A A        3 20 A     20(20 1)(20 2) 6840 3 3 20 A   20 8000 n n A B va C , ABC BAC ACB CAB CBA BCA , , , , , n P n n n n        1 2 1 !   4 P      1 2 3 4 24 9! 362880  A1 A2 ”math” so‘zini o‘z ichiga olmagan barcha o‘rin almashtirishlar to‘plamini deylik. Kamida bitta so‘zni o‘z ichiga olmagan barcha o‘rin almashtirishlar soni ga teng. Ravshanki, (we,d,i,g,m,a,t,h elementlarning o‘rin almashtirishlari soni), (w,e,dig,m,a,t,h elementlarning o‘rin almashtirishlari soni), (w,e,d,i,g,math elementlarning o‘rin almashtirishlari soni), (we,dig,m,a,t,h elementlarning o‘rin almashtirishlari soni), (w,e,dig,math) elementlarning o‘rin almashtirishlari soni), (we,d,i,g,math) elementlarning o‘rin almashtirishlari soni), (we,dig,math) elementlarning o‘rin almashtirishlari soni). Demak, . U holda, “we”,”dig”,”math” so‘zlarini o‘z ichiga olmagan barcha o‘rin almashtirishlar soni . Faraz qilaylik, qandaydir so‘zni tashkil qilgan belgilar orasida aynan bir xil ta birinchi tur, bir xil ta ikkinchi tur, va hokazo, bir xil ta - tur belgilar bo‘lsin, bu yerda , ,… – natural sonlar. Bu belgilarning o‘rinlarini almashtirish natijasida hosil bo‘lgan so‘zlar takrorli o‘rin almashtirishlar (anagrammalar) deb ataladi. Barcha anagrammalar sonini bilan belgilasak, u uchun formula o‘rinlidir. Misol .KOMBINATORIKA so‘zidan nechta anagramma tuzish mumkin? Yechilishi.Bu so‘z ikkita K, ikkita O, bitta M, bitta B, ikkita I, bitta N, ikkita A, bitta T va bitta R harfidan tashkil topganligi bois, anagrammalar soni ga teng. Qiziqarli ma’lumot. Ayrim adabiyotlarda nafaqat so‘zlardan, balki so‘z birikmalari hamda gaplardan tashkil topgan anagrammalar qaraladi. Anagrammalarni tuzish – tabiiy til so‘zlari hamda gaplari bilan kombinatorik mashqlarning qadimiy turi bo‘lib, unga 2000 yildan oshdi. Shunisi qiziqki ANAGRAMS so‘zining harflaridan ARS MAGNA – buyuk san’at (lot.) so‘z birikmasini tuzish mumkin. Ma’lumki, fransuz qiroli Lyudovik o‘zining qarorgohida anagrammist lavozimini kiritib, uning yillik maoshini 1200 livr deb belgilagan. A3 A A A A A A 1 2 3 1 2 3       A A A A A A 1 2 1 3 2 3  A A A 1 2 3 1 A  8! 2 A  7! 3 A  6! 1 2 A A  6! 2 3 A A  4! 1 3 A A  5! 1 2 3 A A A  3! A A A 1 2 3         8! 7! 6! 6! 5! 4! 3! 45222 9! 45222 362880 45222 317658     1 n 2 n k n k 1 n 2 n k n 1 2 ( , ,..., ) P n n nk 1 2 1 2 1 2 ( ... )! ( , ,..., ) ! !... ! k k k n n n P n n n n n n     13! 13! (2,2,1,1,2,1,2,1,1) 2! 2! 2! 2! 16 P    Ayrim anagrammalar nafaqat ma’noga, balki dastlabki so‘zga (yoki so‘z birikmasiga ) qarama-qarshi ma’nodagi so‘zni (yoki so‘z birikmasini) tashkil qiladi. Ulardan ayrimlarini keltiramiz: 1. evils agents (jahannam elchilari) – evangelists (evangelistlar) 2. real fun (katta xursandchilik) – funerals (dafn marosimi) 3. no more stars (boshqa yulduzlar yo‘q) – astronomer (astronom) Birikmalar. Agar elementlar tartibi nazarda soqit qilinsa, shunday masala vujudga keladi: n elementli to‘plamdan nechta m elementli turli qism to‘plam ajratish mumkin? Bunday qism to‘plamlar n ta elementdan m tadan tuzilgan birikmalar deyiladi. Uzunligi n ga teng bo‘lgan va tarkibida aynan m ta harf bo‘lgan ko‘rinishdagi so‘z bunday birikmani tashkil qiladi. Birikmalar soni formulasi bilan hisoblanadi. Misol. Ikkita unli va uchta undosh fonemadan iborat besh fonemali so‘zlar soni ga teng. a ... ... m n m a a b b  ! !( )! m n n n C m m n m          2 5 5! 1 2 3 4 5 10 2!3! 1 2 1 2 3 C           