Kombinatorika elementlari

3 . Ko’paytirish qoidasi

Chekli to’plamlarning dekart ko’paytmasi elementlari sonini topishga imkon beradigan qoida ko’paytma qoidasi deyiladi.

X va Y chekli to’plamlar dekart ko’paytmasining elementlari soni X to’plam bilan Y to’plamdagi elementlari sonlarining ko’paytmasiga teng. X va Y to’plamlar dekart ko’paytmasi (x,y) ko’rinishidagi juftliklardan iborat bo’lib bu juftliklar soni nechta degan savolga ko’paytirish qoidasi javob beradi.

X = {x₁, x₂ …x_n} va Y = {y₁, y₂,…y_m} Bu ikki to’plam Dekart ko’paytmasi XY ta’rifga ko’ra quyidagi juftliklardan iborat bo’ladi. Bu juftliklarni tuzaylik.

(x₁; y₁) (x₁; y₂) …(x₁; y_m)

(x₂ ;y₁) (x₂ ;y₂)…(x₂; y_m)

…………………………

(x_n; y₁) (x_n; y₂)…(x_n; y_m)

Bu yerda har bir qatorda m ta juftlik, har bir ustunda n ta juftlik bor bo’lib, hammasi bo’lib m n ta juftlik bor.

r (X Y) = r (X) · r (Y) = m×n

Ko’paytma qoidasiga oid kombinatorika masalasining umumiy ko’rinishi: «Agar x elementni m usul, y elementni n usul bilan tanlash mumkin bo’lsa, (x;y) tartiblangan juftlikni mn usul bilan tanlash mumkin».

Demak, X va Y to’plamlar dekart ko’paytmasining (kortejlari) juftliklari soni X to’plam elementlari soni bilan Y to’plam elementlari sonlarining ko’paytmasiga teng

Bu qoida n ta to’plam uchun bu formula quyidagicha yoziladi. r (X₁ X₂… X_n) = r (X₁) · r (X₂) …· r (X_n), (n>2),

Masalan, A shahardan B shaharga 3 yo’l bilan, B shahardan C shaharga ikki yo’l bilan borish mumkin bo’lsa, A shahardan C shaharga necha xil usul bilan borish mumkin?

Yo’lning 1-qismini 3 xil, 2-qismini 2 xil yo’l bilan o’tish mumkin bo’lsa, umumiy yo’lni 3·2 = 6 usul bilan o’tish mumkin.

Umumlashgan ko’paytma qoidasi: «Agar x elementni m usul bilan, y elementni, x ni tanlab bo’lgandan so ‘ng, n usul bilan tanlash mumkin bo’lsa, (x;y) juftlikni mn usul bilan tanlash mumkin».

Masala. Nechta turli raqamlar bilan yozilgan ikki xonali sonlar bor? Yechish. 1-raqamni 9 usul bilan (1, 2, …, 9), 2-raqamni ham 9 usul bilan

(noldan boshlab o’nliklar raqamidan boshqa raqamlar) tanlash mumkin. Hammasi bo’lib 9·9 = 81 ta shunday son bor ekan.

1.3.1. Sinfda 40 ta o`quvchi bor. Ulardan 32 tasi matematika to`garagida, 21 tasi

“Yosh rassomlar” to`garagida shug`ullanadi. 15 ta o`quvchi ikkalasida ham shug`ullanadi. Sinfdagi qancha o`quvchi ikkilasida ham shug`ullanmaydi?

1.3.2. Ingliz va nemis tillari o`rganayotgan 100 o`quvchidan ingliz tilini 85 ta, nemis tilini 45 ta o`quvchi o`rganadi. Qancha o`quvchi ikkila tilni ham o`rganadi?

1.3.3. 200 ta talabadan ingliz tilini 42 ta, nemis tilini 30 ta, fransuz tilini 28 ta, ingliz va nemis tilini 8 ta, ingliz va fransuz tilini 10 ta, nemis va farnsuz tilini 5 ta talaba o`rganadi. 3 ta talaba uchala tilni ham o`rganadi. Qancha talaba faqat 1 tadan tilni o`rganadi, qancha talaba birorta ham tilni o`rganmaydi?

1.3.4. 80 ta maktab o`quvchisidan 40 tasi futbol, 50 tasi voleybol o`ynaydi. Ikkala o`yinni ham o`ynaydigan o`quvchilar qancha bo`lishi mumkin? Hech bo`lmaganda 1 ta o`yinni o`ynovchi o`quvchilar sonichi?

1.3.5. 100 ta o`quvchidan 40 tasi futbol, 50 tasi voleybol o`ynaydi. Ikkala o`yinni ham o`ynaydigan o`quvchilar qancha bo`lishi mumkin? Hech bo`lmaganda 1 ta o`yinni o`ynovchi o`quvchilar soni – chi?

1.3.6. 25 ta o`quvchidan 15 tasi matematikaga, 12 tasi ona tiliga qiziqadi. Ikkala fanga qiziquvchi o`quvchilar soni qancha bo`lishi mumkin? Hech bo`lmaganda bittasiga qiziquvchilar – chi?

1.3.7. 25 ta o`quvchidan 12 tasi matematikaga, 8 tasi o`bek tiliga qiziqadi. Ikkala fanga qiziquvchi o`quvchilar soni qancha bo`lishi mumkin? Hech bo`lmaganda bittasiga qiziquvchilar – chi? Ikkala fanga ham qiziqmaydigan oquvchilarchi?

1.3.8. A=a,b,c,d va B=m,f to`plamlar berilgan. Berilgan to`plamlarning dekart ko`paytmasi qancha elementni o`z ichiga olishi mumkin?

1.3.9. n(A)=52, n(B)=100 bo’lsa, n(A×B) to'plamlarning dekart ko'paytmasi qancha elementni o'z ichiga oladi?

1.3.10. A={1,3,5,...101} B={5,10,15,...100} bo’lsa A va B to'plamlarning dekart ko'paytmasida nechta uzunligi 2 ga teng kortej bor?

1.3.11. A={1,3,5,..99} B={5,10,15,... 50} C={2,4,6,8} bo’lsa A, B va C to'plamlarning dekart ko'paytmasining kortejlari uzunligini aniqlang? Bunday kortejlar nechta.

1.3.12. Beshga karrali qancha ikki xonali son bor?

1.3.13. Beshga karrali nechta 3 xonali toq son bor?