GRUPPALASHLAR Reja: 1. Takrorlanmaydigan gruppalashlar. 2. Takrorlanmaydigan gruppalashlarning xossalari. Tayanch iboralar: Takrorlanmaydigan gruppa. Chеkli to`plamlarning to`plam ostilari soni. Ma’ruza matni 1.Takrorlanmaydigan guruhlashlar. «m elementli X to’plamning nechta k elementli qism to’plamlari bor?» — degan masalani hal qilaylik. Masalan, 4 elementli A = {a; b; c; d) to’plamning nechta 3 elementli qism to’plami borligini ko’raylik. Ular{a;b; c}, {a; b; d}, {a; c; d}, {b; c; d}. Demak, 4 ta shunday qism to’plam bor ekan. Bunday qism to’plamlar takrorlanmaydigan guruhlashlar deb ataladi. Bu qism to’plamlarni tartiblaganda 6 barobar ko’proq 3 o’rinli kortejlarga ega bo’lamiz. Masalan, {a; b; c} ni tartiblasak: (a; b; c), (a; c; b), (b; a; c), (b; c; a), (c; a; b), (c; b; a) tartiblangan uchliklarga ega bo’lamiz, tartiblanishlar soni 3! = 6 marta ko’p. Bu bog’lanishdan foydalanib, guruhlashlar sonini topish formulasini keltirib chiqarish mumkin. m elementli to’plamning k elementli qism to’plamlari soni 𝐶𝑚 𝑘 bilan belgilanadi va m elementdan k tadan takrorlanmaydigan guruhlashlar soni deyiladi. (C — fransuzcha combinaison — «birikma» so’zidan olingan.) Takrorlanmaydigan guruhlashlar soni uchun 𝐴𝑚 𝑘 = 𝐶𝑚 𝑘 · 𝑃𝑚 ⇒ 𝐶𝑚 𝑘 = 𝐴𝑚 𝑘 𝑃𝑚 = 𝑚! (𝑚 − 𝑘)! 𝑘! formulaga ega bo’lamiz. Masala. Sinfdagi 20 o’quvchidan ko’rikda ishtirok etish uchun uch o’quvchini necha xil usul bilan tanlash mumkin? Yechish. Ko’rik ishtirokchilarining tartibi ahamiyatga ega bo’lmagani uchun 20 elementli to’plamning 3 elementli qism to’plamlari soni nechtaligini topamiz: 𝐶20 3 = 20! 3! 17! = 18 · 19 · 20 1 · 2 · 3 = 3 · 19 · 20 = 1140. Javob: 3 o’quvchini 1140 usul bilan tanlash mumkin ekan. N ta elementdan r tadan olingan ob’ektlar kombinatsiyasi soni shu vaqtda N ta elementan r tadan elementni o‘rnini almashtirmasdan hosil qilingan to‘plam ostilari soniga teng. Biz buni ushbu ko‘rinishda yozamiz       r n . Biz bu holatda tanlashlar tartibini qaramaymiz. Misol uchun  4 ,3 ,2 ,1 sonlar to‘plamini qaraymiz. Ikki elementli almashtirishlarsiz tanlashlar soni 4!/2!=12 ga teng. Bu aniq  ,42,43 41 ,32,34, 31 ,23,24 21 12,13,14, . 4ta elementdan 2 tadan kombinatsiyasi   34 ,23,24 12,13,14, va uning soni oltiga teng. E’tibor bering !2!2 /!4 2 4 6         . N ta elementli A to‘plam r o‘lchamli n !/ r !( n - r )! Ta to‘plam ostiga ega. Shunday qilib biz )! (! ! r n r n r n         ga ega bo‘lamiz.1 2. 𝑪𝒎 𝒌 ko’rinishdagi sonlarning xossalari. 1°. 𝐶𝑚 𝑘 = 𝐶𝑚 𝑚−𝑘. 2°. 𝐶𝑚 𝑘 = 𝐶𝑚−1 𝑘−1 + 𝐶𝑚−1 𝑘 . 3°. 𝐶𝑚 0 = 𝐶𝑚 𝑚 = 1. 1-xossani isbot qilish uchun 𝐶𝑚 𝑘 = 𝑚! 𝑘!(𝑚−𝑘)!f o r m u l a d a n foydalanamiz: 𝐶𝑚 𝑚−𝑘 = 𝑚! (𝑚 − 𝑘)! (𝑚 − (𝑚 − 𝑘))! = 𝑚! (𝑚 − 𝑘)! (𝑚 − 𝑚 + 𝑘)! = 𝑚! (𝑚 − 𝑘)! 𝑘! = 𝐶𝑚 𝑘 . Xossaga ko’ra,𝐶20 3 = 𝐶20 17; 𝐶5 2 = 𝐶5 3va h. k. 2-xossaning isboti. 1 Mathematical Literacy for Humanists, Herbert Gintis,60-62 𝐶𝑚−1 𝑘−1 + 𝐶𝑚−1 𝑘 = (𝑚 − 1)! (𝑚 − 𝑘)! (𝑚 − (𝑚 − 𝑘))! + (𝑚 − 1)! 𝑘! (𝑚 − 1 − 𝑘)! = = (𝑚 − 1)! (𝑘 − 1)! (𝑚 − 𝑘)! + (𝑚 − 1)! 𝑘! (𝑚 − 𝑘 − 1)! = (𝑚 − 1)! 𝑘! (𝑚 − 1 − 𝑘)! + + (𝑚 − 1)! (𝑚 − 𝑘) 𝑘! (𝑚 − 𝑘 − 1)! (𝑚 − 𝑘) = (𝑚 − 1)! 𝑘 𝑘! (𝑚 − 𝑘) + (𝑚 − 1)! (𝑚 − 𝑘) 𝑘! (𝑚 − 𝑘) = = (𝑚 − 1)! 𝑘 + (𝑚 − 1)! (𝑚 − 𝑘) 𝑘! (𝑚 − 𝑘)! = (𝑚 − 1)! (𝑘 + 𝑚 − 𝑘) 𝑘! (𝑚 − 𝑘)! = = (𝑚 − 1)! 𝑚 𝑘! (𝑚 − 𝑘)! = 𝑚! 𝑘! (𝑚 − 𝑘)! = 𝐶𝑚 𝑘 2°-va 3°-xossalardan foydalanib, 𝐶𝑚 𝑘 ko’rinishdagi sonlarning qiymatini ketma-ket hisoblash mumkin. 1. Paskal uchburchagi va N’yuton binomi. 3°-xossaga ko’ra 𝐶0 0 = 𝐶1 0 = 𝐶1 1 = 𝐶2 0 = 𝐶2 2 = 1. Bundan 2° ga ko’ra 𝐶𝑚 𝑘 ko’rinishdagi sonlarni Paskal uchburchagi ko’rinishida joylashtirish mumkin. Har bir son o’zining tepasidagi ikkita son yig’indisidan iborat. 𝐶2 1 = 𝐶1 0 + 𝐶1 1 = 1 + 1 = 2. Har bir qatordagi sonlar (a + b) m ko’phadning yoyilmasidagi binomial koeffitsiyentlarga teng. Ularning yig’indisi m elementli X to’plamning barcha qism to’plamlari sonini beradi. 2.Chekli to’plam qism to’plamlari soni. 2 elеmеntli to‘plamning hammasi bo‘lib nechta qism to‘plami bоr degan savolga javob beraylik. Ular 1 ta bo‘sh, 2 ta 1 elеmеntli va 1 ta 2 elеmеntli, ya’ni to‘plamning o‘zidan ibоrat bo‘lgan qism to‘plamlardir. Jami: 1+2+1=4. Dеmak, 2 elеmеntli to‘plamning hammasi bo‘lib 4 ta qism to‘plami bоr ekan Quvvati n ga teng bo’lgan A to’plamning to’plam ostilari soni 0 elementli, 1 elementli, 2 elementli, 3 elementli, …, n elementli toplam ostilari sonining yig’indisidan iborat bo’ladi. Now consider the finite set S = {1, 2, 3, . . . , 8} (and so |S| = 8) and ask how many subsets (including S and the empty set ∅) are contained in S. As you might remember, there are 28 such subsets, and this can be shown in at least two ways. The most direct way of seeing this is to form subsets of S by the following process: 1 2 3 4 5 6 7 8 yes or no yes or no yes or no yes or no yes or no yes or no yes or no yes or no where in the above table, a subset if formed by a sequence of yes’s or no’s according as to whether or not the corresponding element is in the subset. Therefore, the subset {3, 6, 7, 8} would correspond to the sequence (no, no, yes, no, no, yes, yes, yes). This makes it already clear that since for each element there are two choices (“yes” or “no”), then there must be 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 28 possibilities in all. Masalan А={1,2,3,4,5,6,7,8} to’plam quvvati |A|=8. To’plam ostilari soni 0 elementli, 1 elementli, 2 elementli, 3 elementli, 4 elementli, 5 elementli, 6 elementli, 7 elementli, 8 elementli toplam ostilari sonining yig’indisidan iborat A to’plamning barcha qism to’plamlarini 0 va 1 lardan iborat ketma- ketlik bilan ifodalash mumkin. Agar element qism to’plamga tegishli bo’lsa, 1 X bilan, tegishli bo’lmasa, 0 bilan almashtiramiz. Masalan {3,6,7,8} qism to’plamini (0,0,1,0,0,1,1,1) kabi shifrlash mumkin. Shunday kortejlar soni 2·2·2·2·2·2·2·2=28ga teng. m elementli A to’oplamning barcha qism to’plamlari soni 2m ga teng2. Umumiy holda chekli m elementli X to’plamning barcha qism to’plamlari sonini topish masalasini qo’yaylik. Uni hal qilish uchun istalgan tarzda X to’plamni tartiblaymiz. So’ng har bir qism to’plamini m o’rinli kortej sifatida shifrlaymiz: qism to’plamga kirgan element o’rniga 1, kirmagan element o’rniga 0 yozamiz. Shunda qism to’plamlar soni 2 ta {0; 1} elementdan tuzilgan barcha m o’rinli kortejlar soniga teng bo’ladi: A̅2 m=2 m. Bundan, 4 elementli to’plam to’plam ostilari soni 2 4 = 16 ga, 3 elementli to’plamning to’plamostilari soni 23 =8 ga tengligi kelib chiqadi. Shu bilan birga bu son Paskal uchburchagining 4-qatoridagi sonlar yig’indisiga ham teng, ya’ni 𝐶3 0 + 𝐶3 1 + 𝐶3 2 + 𝐶3 3 = 1 + 3 + 3 + 1 = 8. Umumiy holda:𝐶𝑚 0 + 𝐶𝑚 1 + ⋯ + 𝐶𝑚 𝑚−1 + 𝐶𝑚 𝑚 = 2𝑚. Nazorat uchun savollar. 1. Takrorlanmaydigan gruppalashlar soni qanday topiladi? 2. Takrorlanmaydigan gruppalashlarning xossalarini ayting va isbotlang. Foydalaniladigan asosiy adabiyotlar ro‘yxati Asosiy adabiyotlar 1. Xamedova N.A, Ibragimova Z, Tasetov T. Matеmatika. Darslik. T.: Turon- iqbol, 2007. 363b(26-33 bet). Qo‘shimcha adabiyotlar 1. Abdullayeva B.S., Sadikova A.V., Muxitdinova M.N., Toshpo‘latova M.I., Raximova F. Matematika. TDPU. (Boshlang‘ich ta’lim va sport-tarbiyaviy ish bakalavriyat ta’lim yo‘nalishi talabalari uchun darslik) Toshkent-2012, 284 bet (70-83 betlar) 2 Herbert Gintis. Mathematical Literacy for Humanists. Printed in the United States of America, 2010 2. Mathematical Literacy for Humanists, Herbert Gintis, (60-62 betlar) Nazorat savollari Т-sxema O`ziga xos xususiyatlari O`rinlashtirishlar Guruhlashlar 1) O`xshashlik tomoni 1) O`xshashlik tomoni 2) Farqi 2) Farqi 3) Fandagi ahamiyati 3) Fandagi ahamiyati Ilova 1. 1. 1,2,3 raqamlar ishtirokida nechta uch xonali son tuzish. Raqamlarni t a k r o r l a s h m u m k i n 2, 7, 9 raqamlar ishtirokida nechta uch x o n a l i s o n t u z i s h . 2. Maktab binosining 5 ta tordamchi eshigi bor. Necha usul bilan bu eshiklardan kirib chiqish mumkin? 2Oshxona taomnomasida 5 ta birinchi, 8 t a i k k i n c h i v a 3. Qutida qizil, qora, yashil sharlar bor. 2 ta sharni qutidan necha usul bilan olish mumkin? 3. Qutida 2 ta qizil, qora va yashil sharlar bor. 2 ta turli rangli sharlarni qutidan necha usul bilan olish mumkin? lits-so’rov savollari  Kombinatorika deb nimaga aytiladi?  Birikmalar necha xil bo’ladi?  Takrorlanuvchi o’rinlashtirish deb nimaga aytiladi?  Takrorlanishli guruhlashlar deb nimaga aytiladi?  Diskret to’plam deb qanday to’plamga aytiladi? Test savollari 1. Dekart ko`paytma elementlari sonini sanash uchun qo`llanadigan qoida a) yig`indi b) ko`paytma c) akslantirish d) ayirish 2. To`plamlar birlashmasi elementlari sonini sanash uchun qo`llanadigan qoida a) yig`indi a) ko`paytma b) akslantirish c) ayirish 3. m elementli X to’plam elementlaridan tuzilgan k o’rinli kortejlar - a) Takrorlanadigan o’rinlashtirishlar b) Takrorlanmaydigan o’rinlashtirishlar c) Takrorlanmaydigan o’rin almashtirishlar d) Takrorlanmaydigan guruhlashlar 4. m elementli X to’plam elementlaridan takrorlamay tuzilgan k o’rinli kortejlar - e) Takrorlanadigan o’rinlashtirishlar f) Takrorlanmaydigan o’rinlashtirishlar g) Takrorlanmaydigan o’rin almashtirishlar h) Takrorlanmaydigan guruhlashlar 5. n elementdan n tadan takrorlanmaydigan o’rinlashtirishlar - a) Takrorlanadigan o’rinlashtirishlar b) Takrorlanmaydigan o’rinlashtirishlar c) Takrorlanmaydigan o’rin almashtirishlar d) Takrorlanmaydigan guruhlashlar 6. m elementli X to’plam elementlaridan n elementlardan tuzilgan m elementli qism to`plamlar - a) Takrorlanadigan o’rinlashtirishlar b) Takrorlanmaydigan o’rinlashtirishlar c) Takrorlanmaydigan o’rin almashtirishlar d) Takrorlanmaydigan guruhlashlar 7. A m n nimani bildiradi? a) Takrorlanadigan o’rinlashtirishlar b) Takrorlanmaydigan o’rinlashtirishlar c) Takrorlanmaydigan o’rin almashtirishlar d) Takrorlanmaydigan guruhlashlar 8. P n nimani bildiradi ? a) Takrorlanadigan o’rinlashtirishlar b) Takrorlanmaydigan o’rinlashtirishlar c) Takrorlanmaydigan o’rin almashtirishlar d) Takrorlanmaydigan guruhlashlar Nazorat savollari Т-sxema O`ziga xos xususiyatlari O`rinlashtirishlar O`rin almashtirishlar 1) O`xshashlik tomoni 1) O`xshashlik tomoni 2) Farqi 2) Farqi 3) Fandagi ahamiyati 3) Fandagi ahamiyati Ilova 1. 1. 1,2,3 raqamlar ishtirokida nechta uch x o n a l i 2, 7, 9 raqamlar ishtirokida nechta uch x o n a l i 2. Maktab binosining 5 ta tordamchi eshigi bor. Necha usul bilan bu eshiklardan kirib chiqish mumkin? 2Oshxona taomnomasida 5 ta birinchi, 8 t a i k