Kombinatorika masalalari

Kombinatorika masalalari Reja: 1 Yg'indi va ko'paytma qoidasi 2 O'rinlashtirishlar 3. O'rin almashtirishlar 4. Guruhlashlar 3. Darsning jihozi: Doska, bo'r, ko'gazmali qurollar 4. Topshiriqlar. Kombinatorika elementlariga oid nazariy mashg'ulotlarni puxta o'rganib qullanmada va darslikda berilgan misollarni echib kelish. Kombinatorik masalalar. 1. Yig'ndi va ko'paytma qoidasi. a) Agar A va B o'zaro kesishmaydigan to'plamlar bo'lib, A da m element, B da n element bo'lsa berlashmada m+n element bo'ladi. Agar A va B to'plamlar o'zaro kesishsa birlashmaning elemintlari soni m+n dan A va B lar uchun mumumiy bo'lgan elementler sonini ayrib tashlab topiladi. b) Agar A va B to'plamlar chekli va Ada n element Bda m element bo'lsa, bu elementlardan tuzilgan k uzunlikdagi kortijlar soni gat eng. Endi bu qoidalarga xos misollar keltiramiz. Yig'ndi qoidasi () =n(A)+n(B) (1) n ()=n (A)+n(B)-n () (2) Formulalar orqali ifodalanishini bilamiz. (1) formula bilan yechiladigan kombinatorika masalasi umumiy holda quydagicha ifodalanadi: Agar X elementi m usul, Y elementi n usul bilan tanlash mumkin bo'lsa, X yoki Y elementini m+n usul bilan tanlash mumkin. 1-misol. Savatda 10 dona olma va 20 dona shoftoli bor, bo'lsa 1 dona mevani necha xil usul bilan tanlash mumkin. yechish. 1 dona mevani 10+20=30 usul bilan tanlash mumkin 2-misol. X=1,2,3,4, Y=a,b,c,d,e to'plamlar berilgan =? yechish. n (x)=4. n(Y)=5 bo'lgan uchun n(XxY)=4+5=9. 3-misol. X=2,4,6,8, y=2,5,7,9 to'hlamlar berilgan. n (XxY)=? yechish n(x)=4, n(y)=4 Lekin 2 sonni xar ikkala to'plamda ham qatnashadi, demak =1 (2) formulaga ko'ra =4+4-1=7. 4 - misol. 30 ta talabadan 25 tasi matematikadan yakuniy nazoratdan, 23 tasi iqtisod yakuniy nazariydan o'ta oldi. 3 ta talaba ikkala fan bo'yicha yakuniy nazariydano'ta olmadi. Nechta qarzdor talaba bor. yechish. A bilan matematika yakuniy nazariydan o'tmagan talabalar to'plamini, B bilan iqtisod fanidan yakuniy nazariydan o'tmagan talabalar to'plamini belgilaymiz. U holda n(A) = 30-25=5, n(B)=30-23=7 n()=3, n()=5+7-3=9. Demak, 9 ta qarzdor talaba bor. Bizga ma'lumki ko'paytma qoidasi n(AXB)=n(A) (3) ko'rinishda yoziladi. Ko'payutma qoidasiga oid kombinatorika masalasi quyidagicha ko'rinishda bo'ladi. Agar X elementini m usul, Y elementini n usul bilan tanlash mumkin bo'lsa, (x;y) tartiblangan juftlikni usul bilan tanlash mumkin 5-misol. A qishloqdan B qishloqqa 5 ta yo'l olib boradi, B qishloqdan C qishloqqa esa 2 ta yo'l olib boradi. A qishloqdan C qishloqqa B qishloq orqali necha xil usul bilan borsa bo'ladi. yechish. A dan C ga (1,a)(1,b), (2,a),(2,b),(3,a),(3,b),(4,a),(4,b),(5,a),(5,b) juftliklar orqali berilgan yo'nalishlarda borish mumkin. Bunda yo'lning birinchi qismi 5 xil usul bilan, 2 - qismi 2 hil usul bilan bosib o'tiladi. X=1,2,3,4,5,, Y-a,b. deb olsak, ...