§. Natural va butun sonlar

24- §. Kombinatorika.

Kombinatorika- diskret matematikaning bir bo’limi bo’lib, asosan chekli to’plamlar ustida ish ko’radi. Kombinatorikada sodda, ammo muhim bo’lgan qoidalar bor. Bunday qoidalar sifatida qo’shish, ko’paytirish qoidalari mavjud.

m ta elementli A to’plam va n ta elementli B to’plamlar berilgan bo’lib, ular kesishmasin. Qo’shish qoidasiga ko’ra, A yoki B to’plamga tegishli bo’ladigan birorta elementni tanlash imkoniyatlari soni (m+n) ga tengdir.

Ko’paytirish qoidasiga asosan, m ta elementli A va n ta elementli B to’plamlarning elementlaridan tuzish mumkin bo’lgan barcha (a, b) juftliklar soni mn ga teng.

Misol: A =10 (har xil ruchka ), B =5 (har xil daftar).

Bu to’plamlardagi elementlarning faqat birini tanlasak, unda tanlashlar soni qo’shish qoidasiga asosan 15 ta bo’ladi.

Agar A va B to’plam elementlaridan juft-juft qilib tanlasak, tanlashlar soni ko’paytirish qoidasiga asosan 50 ta bo’ladi.

Kombinatorika berilishiga ko’ra takrorlanadigan va takrorlanmaydigan:

1) o’rin almashtirish;

2)o’rinlashtirish;

3)gruppalash turlariga ajraladi

1) O’rin almashtirishlar. Elementlari a₁, a₂, a₃,……, a_n bo’lgan to’plamni qaraymiz. Bu to’plam elementlarini har xil tartibda joylashtirib (yozib), tuzilmalar (kombinatsiyalar) hosil qilish mumkin, masalan,

(a₁,a₂,a₃,……,a_n); ( a₁,a₂,a₃,……,a_n); (a₃,a₂,a₁,……,a_n)………

Bu tuzilmalarning har birida berilgan to’plamning barcha elementlari ishtirok etgan holda ular bir-biridan faqat elementlarining joylashish o’rinlari bilan farq qiladi. Shu usul yordamida hosil qilingan kombinatsiyalarning har biri berilgan (a₁,a₂,a₃,……,a_n) to’plam elementlarining o’rin almashtirishi deb ataladi.

1-teorema. Elementlari soni n ta bo’lgan to’plam uchun o’rin almashtirishlar soni n! ga teng, ya’ni P_n =n!

Misol: Kitob javonidagi 10 ta har xil kitobni necha xil usul bilan joylashtirish mumkin?

Birinchi o’rinda turgan kitob o’rniga kitob qo’yish uchun bizga 10 xil variant mavjud, ikkinchi kitob o’rniga turgan kitob qo’yish uchun bizga 9 xil variant mavjud. Shu usulda davom ettirsak jami joylashtirishlar usuli P₁₀ =10! Ga teng bo’ladi.

2)O’rinlashtirishlar. N ta elementli (a₁,a₂,a₃,……,a_n) to’plam berilgan bo’lsin. Shu to’plamning ixtiyoriy m ta elementidan hosil qilingan tartiblangan ( tuzilmaga (kombinatsiyaga) n ta elementdan m tadan o’rinlashtirish, de ataladi.

Berilgan n ta elementdan m tadan o’rinlashtirishlar soni odatda A_n^m bilan belgilanadi.

2-teorema. N ta elementdan m tadan o’rinlashtirishlar soni eng kattasi n ga teng bo’lgan m ta ketma-ket natural sonlarning ko’paytmasiga tengdir.

A_n^m =n(n-1)……(n-m+1)

3)Gruppalash. ( to’plam berilgan bo’lsin. Bu n elementli to’plamning elementlaridan m ta elementga ega qism to’plamlarni shunday tashkil etamizki, ular bir-biridan elementlarining joylashish tartibi bilan emas, faqat tarkibi bilan farq qilsin. Bunday m ta elementli qism to’plamlarning har biriga n ta elementdan m tadan gruppalash deb ataladi.

N ta elementdan m tadan gruppalashlar sonini C_n^m bilan belgilaymiz.

4)Takrorli o’rin almashtirishlar soni. Faraz qilaylik, qandaydir n ta elementlari orasida bir xil (aynan bir xil) n₁ ta birinchi tur, bir xil n₂ ta ikkinchi tur va hokazo, bir xil n_k ta k- tur elementlar bo’lsin, bu yerda, n₁, n₂,….n_k – hech bo’lmaganda bittasi 1 dan farqli natural sonlar. Bu n ta elementlarning o’rinlarini imoniyati boricha almashtirishlar natijasida hosil bo’lgan kombinatsiyalar takrorlanuvchi elementlar qatnashgan o’rin almashtirishlar (qisqacha, takrorli o’rin almashtirshlar) deb ataladi.

N ta elementlar orasida n₁ ta birinchi tur, n₂ ta ikkinchi tur va hokazo, n_k ta k –tur bir xil elementlar bo’lgan takrorli o’rin almashtirishlar sonini C_n(n₁,n₂,….,n_k) bilan belgilaymiz.

Teorema: takrorli o’rin almashtirishlar soni uchun

C_n(n₁,n₂,….,n_k) = formula o’rinlidir. ( bu yerda n₁+n₂+….+n_k=n)

5) Takrorli o’rinlashtirishlar. n ta elementdan tashkil topgan to’plam berilgan bo’lsin. Bu elementlardan foydalanib, m ta elementdan tashkil topgan kombinatsiyalarni shunday tuzamizki, bu kombinatsiyalarga har bir element xoxlagancha marta (albatta m dan oshmagan miqdorda)kirishi mumkin bo’lsin va bu kombinatsiyalar bir-biridan ularni tashkil elementlari turlari bilan yoki bu elementlarning joylashishlari bilab farq qilishsin. Shunday usul bilan tuzilgan kombinatsiyalarning har biri n ta turli elementlardan takrorlanuvchi elementlar qatnashgan m tadan o’rinlashtirish ( qisqacha takrorli o’rinlashtiris) deb ataladi.

N ta turli elementlardan m tadan takrorli o’rinlashtirishlar sonini bilan belgilaymiz.

Teorema: n ta turli elementlardan m tadan takrorli o’rinlashtirishlar soni n^m ga teng.

6) Takrorli gruppalash. Har bir elementi birlashmaga istalgancha marta kiritiladigan va turli n ta elementlardan m tadan olinadigan hamda elementlar tartibi e’tiborga olinmaydigan birlashmalarni qaraymiz. Bunaqa birlashmalar n ta turli elementlardan m tadan takrorlanuvchi elementlar qatnashgan gruppalashlar ( qisqacha, takrorli gruppalashlar), deb ataladi.

Teorema: n ta elementdan m tadan takrorli gruppalashlar soni ga teng bo’ladi.

24-Mashq.

1.Quyidagi shartni qanoatlantiruvchi nechta ikki xonali son mavjud?

a) raqamalari orasida 5 raqami hech bo’lmaganda bir marta qatnashadi.

b)o’nlik xonasidagi raqam birlik xonasidagi raqamdan kichik.

c) o’nlik xonasidagi raqam birlik xonasidagi raqamdan katta.

Javob: (a)18 b)36 c)45 )

2. 1 dan 100 gacha bo’lgan natural sonlar ketma-ket yozib chiqildi. Natijada hosil bo’lgan sonda 0 raqami necha marta qatnashadi?

Javob: (11)

3. 1 dan 100 gacha bo’lgan natural sonlar ketma-ket yozib chiqildi. Natijada hosil bo’lgan sonda 1 raqami necha marta qatnashadi?

Javob: (21)

4. 1 dan 100 gacha bo’lgan natural sonlar ketma-ket yozib chiqildi. Natijada hosil bo’lgan sonda 3 raqami necha marta qatnashadi?

Javob: (20)

5. 10 sonidan 1000 sonigacha raqamlari yig’indisi 9 bo’lgan nechta son mavjud?

Javob: (54)

6. Firmada 20 ta qo’y va 24 ta echki bor. Necha xil usul bilan bitta qo’y va bitta echki tanlash mumkin?

Javob: (480)

7. Shaxmat doskasidagi qora va oq kvadratlarni necha xil usul bilan ko’rsatish mumkin?

Javob: (1024)

8. 6 juft har xil o’lchamdagi qo’lqoplar bor. Chap qo’l va o’ng qo’lda har xil o’lchamda bo’ladigan qo’lqoplarni necha xil usul bilan tanlash mumkin?

Javob: (30)

9. Uch nusxada algebra bo’yicha o’quv kitoblar, yetti nusxada geometriya bo’yicha o’quv kitoblar va yetti nusxada trigonometriya bo’yicha o’quv kitoblari bor. Har bir o’quv kitoblaridan bittadan nusxa olishni necha xil usul bilan tanlash mumkin?

Javob: (147)

10. 100 dan 10000 gacha bo’lgan sonlar orasida uchta bir xil raqam uchraydigan nechta son mavjud?

Javob: ( 333)

11. O’n birta odamdan iborat futbol komandasida necha xil usul bilan kapitan va unga yordamchi tanlash mumkin?

Javob: (110)

13.Necha xil usul bilan qatorga qizil, qora, ko’k va yashil rangli koptoklarni qo’yish mumkin.

Javob: (24)

14.Mamlakatda 20 ta shahar bo’lib, har bir shahar avia yo’llar bilan bog’langan. Bu mamlakatda nechta avia yo’llar bor?

Javob: (380)

15. Nechta 5 ta har xil rangdan 3 ta har xil rang tanlash mumkin?

Javob: (10)

16. Komissiya tarkibi 3 ta odamdan iborat bo’lsa, 20 ta odamdan necha xil usul bilan komissiya tuzish mumkin?

Javob:(1140)

17.Kitob javonida 10 ta matematika va 5 ta fizika kitoblari mavjud bo’lib, bu kitob javonidan 5 ta kitob tanlab olindi. Tanlab olingan kitoblar bir xil turda bo’lishini necha xil usul bilan tanlash mukin?

Javob: (253)

18. Uchburchakning tomonlarida 20 ta , 6 ta va 4 ta nuqtalar belgilandi(Bu belgilangan nuqtalarning hech qaysi uchburchakning uchlari bo’lmaydi). Uchlari belgilangan nuqtalarda bo’lgan nechta uchburchak mavjud?

Javob: (480 )

19. Avtomobilning nomeri bir, ikki yoki uchta harfdan va to’rta raqamdan iborat bo’lishi mumkin. Agar o’zbek alifbosida 29 ta harf bo’lsa, nechta avtomobil nomeri mavjud?

Javob: (25259)

20. Kitob javonida 30 tomli kitob bo’lib, birinchi va ikkinchi tomli kitoblar yonma-yon turadigan qilib necha xil usul bilan joylashtirish mumkin?

Javob: ( 2

21. Kitob javonida 30 tomli kitob bo’lib, uchinchi va to’rtinchi tomli kitoblar yonma-yon turmaydigan qilib necha xil usul bilan joylashtirish mumkin?

Javob: ( 28

22. Aylana stol atrofida n ta erkak va n ta ayolni necha xil usul bilan bir jinsdagilar yonma-yon o’tirmaydigan qilib joylashtirish mumkin?

Javob: (2)

23. Karta qutisida 52 ta karta bo’lib, bu qutidan 10 ta karta olindi. Olingan kartalar orasida hech bo’lmaganda bitta tuz bo’lishi uchun bu hodisani necha marta takrorlash kerak?

Javob: ( )

24. Karta qutisida 52 ta karta bo’lib, bu qutidan 10 ta karta olindi. Olingan kartalar orasida bitta tuz bo’lishi uchun bu hodisani necha marta takrorlash kerak?

Javob: ( )

25. Karta qutisida 52 ta karta bo’lib, bu qutidan 10 ta karta olindi. Olingan kartalar orasida ikkitadan kam tuz bo’lmasligi uchun bu hodisani necha marta takrorlash kerak?

Javob: ( )

26. Karta qutisida 52 ta karta bo’lib, bu qutidan 10 ta karta olindi. Olingan kartalar orasida ikkita tuz bo’lishi uchun bu hodisani necha marta takrorlash kekak?

Javob: ( )

27. n ta elementni joylashtirishda belgilangan m ta elementni yonma-yon turmaydigan qilib necha xil usulda joylashtirish mumkin?

Javob: (n

28. n ta har xil sharni m ta har xil qutiga necha xil usul bilan joylashtirish mumkin? (qutidagi hajm cheklanmagan)

Javob: ( mⁿ)

29. “Matematika” so’zidagi harflardan nechta so’z tuzish mumkin?

Javob: (151200)

30. Komissiya rais, o’rinbosar va 5 ta odamdan iborat. Necha xil usul bilan bu lavozim majburiyatlarni bu odamlarga taqsimlash mumkin?

Javob: (42)

31. Vazada 10 ta qizil va 5 ta oq rangdagi gullar bo’lib, vazadan 5 ta bir xil rangdagi gullarni necha xil usul bilan tanlab olish mumkin?

Javob: (253)

32. 800 m, 400m,200m va 100 metrlik yugirish estafetasida 15 ta odamni necha xil usul bilan tanlash mumkin?

Javob: (32760)

33. Shaxmat doskasida ikkita ruhni necha xil usul bilan bir-birini olmaydigan qilib joylashtirish mukin? (agar ikkita ruh gorizontal yoki vertikal yo’lga turib qolsa, bir-birini oladi)

Javob: (3136)

34. Shaxmat doskasida ikkita ruhni necha xil usul bilan bir-birini oladigan qilib joylashtirish mukin? (agar ikkita ruh gorizontal yoki vertikal yo’lga turib qolsa, bir-birini oladi)

Javob: (896)

35. 30 ta odamni har bir guruhga 10 tadan odam bo’lgan uchta guruhga ajratishni necha xil usul bilan amalga oshirish mumkin?

Javob: (30!/(10!)³)

36. Kitob javonida 30 tomli kitob joylashtirildi. Birinchi va ikkinchi tomli kitoblarni yonma-yon turmaydigan qilib necha xil usul bilan joylashtirish mumkin?

Javob: ( 30! -229!)

37. Har kuni navbatchilikka 2 tadan odam qo’yib 6 kunga 12 ta odamni taqsimlab, necha xil usul bilan navbatchilik ro’yxatini tuzish mumkin? (Har bir odam bir marta navbatchilik qiladi)

Javob: ((12!/(2!)⁶)

38. 6 ta har xil rangdagi materiallarni 5 qavatli qurilish binosida yetkazish kerak. Bu materiallarni qavatlarga necha xil usul bilan taqsimlash mumkin?

Javob: ( 5⁶)

39. Ikkita xat tashuvchi 10 ta har xil xatni 10 ta adresga yetkazish kerak. Bu ishni necha xil usul bilan taqsimlash mumkin?

Javob: (2¹⁰)

40. Metroning poyezdida yo’lovchilar tushadigan 16 bekat mavjud. 100 ta yo’lovchini bu bekatlarda tushishini necha xil usul bilan taqsimlash mumkin? (16 ta bekatda yo’lovchilar chiqmaydi)

41. Vazada 10 ta qizil va 4 ta oq atirgul bor. Bitta qizil va ikkita oq atirgulni necha xil usul bilan tanlash mumkin?

Javob; (60)

42.7 ta erkak va 4 ta ayoldan tarkibida hech bo’lmaganda 2 ta ayol bo’lgan 6 ta odam tanlash kerak. Buni necha xil usul bilan amalga oshirish mumkin?

Javob: (371)

43. Otaning 5 ta har xil kitobi bo’lib, u o’zining 8 ta o’g’liga taqsimlab bermoqchi. Buni necha xil usul bilan amalga oshiradi?

b) agar har bir bola bittadan ortiq kitob olmasa

Javob: (a) 8⁵; b) A₈⁵ =6720)

44. 4,5 va 6 raqamlaridan tuzilgan hamda 4 raqami 3 marta, 5 va 6 raqamlari 2 martadan takrorlangan nechta 7 xonali son mavud?

Javob: (7!/ (3!2!2!))