2.Yig’indi qoidasi. Yig`indi va ko`paytma qoidasi
A va B to`plamlar berilgan bo`lsin. Bu to`plamlar birlashmasining elementlari sonini yig`indi qoidasidan foydalanib topiladi. Bu qoida quyidagicha:
A to`plamning elementlari n ta bo`lsin. r(A) = n. B to`plamning elementlari soni m ta bo`lsin. r(B) = m ko’rinisda yoziladi.
a. A va B to`plamlar umumiy elementga ega bo`lmasa, u holda bu to`plamlar birlashmasining elementlari soni A to`plam elementlari soni bilan B to`plam elementlari soni yig`indisidan iborat bo`ladi. Ya`ni:
r (AB) = r (A) + r (B) = n+m
Kombinatorikada to’plamlar birlashmasi elementlari sonini hisoblash masalasi yig’indi qoidasi deb ataladi.
Agar A∩B =∅ bo’lsa,
n(A∪B) = n(A) + n(B) (1) bo’ladi.
Ya’ni kesishmaydigan A va B to’plamlar birlashmasi elementlari soni shu to’plamlar elementlari sonlarining yig’indisiga teng.
Agar A∩B≠∅ bo’lsa,
n(A∪B) = n(A) + n(B) - n(A∩B) (2)
bo’ladi. Ya’ni umumiy elementga ega ikki to’plam birlashmasi ele- mentlari soni to’plamlarning har biri elementlari sonlari yig’indisidan ularning umumiy elementlari sonining ayrilganiga teng. (2) formula (1) formulaning umumiy holi bo’lib, (1) formulada n(A∩B)=∅, ya’ni to’plamlarning umumiy elementi yo’q.
Yigindi qoidasi umumiy elementga ega bo’lgan uchta A, B, C to’plam uchun quyidagicha yoziladi: agar A∩B∩C = ∅bo’lsa,
n(A∪B∪C) = n(A) + n(B) + n(C) - n(A∩B) - n(A∩C) - n(B∩C) +
n(A∩B∩C) (3) bo’ladi.
formula bilan yechiladigan kombinatorika masalasi umumiy holda quyidagicha ifodalanadi: agar x elementni k usul, y elementni m usul bilan tanlash mumkin bo’lsa, «x yoki y» elementni k + m usul bilan tanlash mumkin.
Masalan, savatda 8 ta olma va 10 ta nok bor bo’lsa, 1 ta mevani 8 + 10 = 18 usul bilan tanlash mumkin.
formula bilan yechiladigan masala: 40 talabadan 35 tasi matematika imtihonini, 37 tasi rus tili imtihonini topshira oldi. 2-talaba ikkala fandan
«2» oldi. Nechta qarzdor talaba bor?
Yechish. A — matematika fanidan «2» olgan, B - rus tili fanidan «2» olgan talabalar to’plami bo’lsin. n(A) = 40 - 35 = 5 n(A∩B) = 2. n(B)= 40 - 37 = 3 n(A∪B) = 5 + 3- 2 = 6.
Javob: 6 ta qarzdor talaba bor.
formula - yig’indi qoidasi bilan yechiladigan masalani ko`raylik.
1 -masala. Sinfda 40 o`quvchi bor. Uning 26 tasi basketbol, 25 tasi — suzish, 27 tasi — gimnastika bilan shug`ullanadi, bir vaqtda suzish va gimnastika bilan — 15 ta, basketbol va gimnastika bilan — 16 ta, suzish va gimnastika bilan shug`ullanuvchilar — 18 ta. 1 o`quvchi darsdan ozod. Hamma sport turi bilan nechta o`quvchi shug`ullanadi? Nechta o`quvchi faqat 1 ta sport turi bilan shug`ullanadi?
Yechish. Maslada 3 ta to`plam qaralyapti: А — basketbol bilan shug`ullanuvchilar, В — suzish bilan shug`ullanuvchilar, С — gimnastika bilan shug`ullanuvchilar. Bu uch to`plam kesishadi.
Bu 3 to`plam kesishmasidagi elementlar sonini х bilan belgilasak, quyidagi tenglamaga ega bo`lamiz:
26 + 25 — (3З — х) + (18 — х) + 27 — (34 - x) + 1 = 40.
Bu yerda х = 10. Demak, hamma sport turi bilan 10 ta o`quvchi, faqat 1 ta sport turi bilan 10 ta: basketbol bilan — 5 ta, suzish bilan — 2 ta, gimnastika bilan — 3 ta o`quvchi shug`ullanadi.
2-masala. 50 talabadan 20 tasi nemis tilini, 15 tasi inghliz tilini o`rganadi. Ikkala tilni biluvchi va faqat 1 ta tilni biluvchi talabalar soni nechta bo`lishi mumkin?
Yechish. Maslada 2 ta to`plam qaralyapti: А —barcha talabalar to`plami, В — nemis tilini o`rganadigan, С — inghliz tilini o`rganadigan talabalar to`plami. Masala sharti bo`yicha n(А) = 50, n(В) =20, n(С) = 15.
А, В va To`plamlar orasidagi munosabatlarni Eyler-Venn diagrammalarida quyidagicha tasvirlash mumkin. Ikki tilni biluvchi talabalar soni В va С to`plamlar kesishmasi elementlari sonini topish bilan bog`liq. Faqat 1 ta tilni biluvchi talabalar soni ikki to`plam birlashmasi elementlari sonini topish bilan bog`liq.
n ( B C) = 0 n ( B C) = 15 n (B ∪ C) = 35 n (B ∪ C) = 20 х—Ikki tilni biluvchi talabalar soni bo`lsa, 0 ≤ x ≤ 15 (x N0). у — 1 ta tilni
biluvchi talabalar soni bo`lsa, 20 ≤ у ≤ 35 (у N0).
Bu qoidani n ta to`plam uchun ham to`g`ri deb qabul qilamiz. Ya`ni A1, A2 … An ta to`plam berilgan bo`lsin va bu to`plamlar umumiy elementga ega emas. Ya`ni o`zaro kesishmaydigan to`plamlar.
U holda. r (A1A2...An)=r(A1)+r(A2)+...+r(An) bo’ladi.
b) A va B to`plamlar umumiy elementga ega bo`lsin u holda r (AB) = r (A) + r (B) – r (AB)
A1 A2 ... An to`plam uchun bu holni umumlashtiramiz. Ya`ni berilgan n ta to`plam umumiy elementga ega bo`lsa, u holda bu to`plamlar birlashmasining elementlari soni quyidagicha bo`ladi:
r (A1A2... An) = r (A1) + r (A2) +...+ r (An) – r (A1A2) – r (A2A3) …--r (An-1 An) + r (A1 A2 A3) +…+
(-1n-1) r (A1 A2…An)
Dostları ilə paylaş: |