Mavzu: Kombinatorika elementlari Reja: Kombinatorikaning asosiy qoida va formulalari

kiritish-
chiqarish qoidasi
o‘rinli:
|
| |
|
|
| |
|
A
B
A
B
A
B



 

---

Ravshanki, bu tenglikdan foydalanib |
|
A
, |
|
B
, 
|
|
A
B
va 
|
|
A
B
miqdorlarning ixtiyoriy uchtasi ma’lum bo‘lganda to‘rtinchisini hisoblash mumkin. 
Misol
. 50 ta talabadan 40 tasiingliz tilini, 25 tasi esa nemis tilini 
o‘rganmoqdalar. Ikkala tilni ham o‘rganayotgan talaba nechta? 
Yechilishi. Ingliz tilini o‘rganayotgan talabalar to‘plamini 
A
orqali, nemis 
tilini o‘rganayotgan talabalar to‘plamini 
B
orqali belgilaymiz.
Ma’lumki, 
|
|
A
B
=
50, |
|
A
= 40, |
|
B
=25. U holda ikkala tilni ham 
o‘rganayotgan talabalar 
A
B
to‘plamni tashkil qilib, kiritish-chiqarish 
formulasidan
|
|
A
B
=
|
|
A
+|
|
B -
|
|
A
B
=
15
.
Ko‘paytirish qoidasi:
{
,
|
,
}
Ñ
a b
a
A b
B
 
 

ko‘rinishdagi to‘plam 
uchun
|
| |
| |
|
C
A
B


Eslatma
. Yuqorida bayon qilingan ikkita to‘plam uchun qo‘shish, 
ko‘paytirish hamda kiritish - chiqarish qoidalarini chekli sondagi istalgan chekli 
to‘plamlar uchun umumlashtirish mumkin. 
Masalan, uchta chekli 
, ,
A B C
to‘plamlar uchun 
A
B
C
A
B
C



A
B
A
C
B
C



A
B
C

kiritish - chiqarish qoidasi o‘rinli.
Misol
. 40 nafar turistdan 20 nafariingliz tilini, 15 nafari fransuz tilini, 11 
nafari esa ispan tilini biladilar.Ingliz va fransuz tillarini etti nafar turist, ingliz va 
ispan tillarini besh nafar turist, fransuz va ispan tillarini esa uch nafar turist biladi. 
Ikki nafar turist uchta tilni bilgani ma’lum bo‘lsa, turistlar ichida nechtasi shu 
uchta tildan birortasini ham bilmaydi? 
Yechilishi
. Ingliz tilini biladigan turistlar to‘plamini 
E
deb, frantsuz 
tilinibiladigan turistlar to‘plamini 
F
deb, ispan tilini biladigan turistlar to‘plamini 
esa 
I
deb belgilaymiz. U holda 
|
|
E
20

, 
|
|
F

15, 
| |
I

11, 
7
E
F

, 
5
E
F

, 
3
I
F

, 
2
E
F
I

.
Dastlab kamida bitta tilda gaplashadigan turistlar sonini topamiz: 
E
F
I
E
F
I



E
F
E
I
F
I



E
F
I


20 15 11 7 5 3 2
33


     
Demak, 
40 33
7


nafar turist shu uchta tildan birortasini ham bilmaydi.
O‘rinlashtirishlar, o’rin almashtirishlar, birikmalar.
Predmetlardan tashkil topgan tuzilmalar 
kombinatsiyalar
deb ataladi. 
Uch xil turdagi kombinatsiyalar o‘rganiladi: o‘rin almashtirish, o‘rinlashtirish va 
birikmalar. 
O’rinlashtirishlar 
A
alfavit 
n
ta belgidan tashkil topgan bo‘lsin. Uzunligi 
m
ga teng bo‘lgan 
so‘zlar (ya’ni uzunligi 
m
ga teng bo‘lgan ketma-ketliklar) sonini sanab chiqaylik.
Har bir so‘zni tashkil etgan belgilar orasidagi takrorlanadiganlari bor 
bo‘lgan holda bunday so‘zlar sonini 
m
n
A
(
n
ta elementdan
m
tadantakrorli 

---

o‘rinlashtirishlar soni)
, bu belgilarning barchasi har hil bo‘lgan holda 
(
takrorsiz o‘rinlashtirishlar soni
) deb belgilaymiz. 
Bu ikki miqdor uchun formulalar quyidagicha: 
, 
. 
Bu yerda 
(
n
– faktorial deb o‘qiladi) 
Endi uzunligi 
dan ko‘p bo‘lmagan so‘zlar sonini sanab chiqaylik.
Bunda qo’shish (jamlash) qoidasiga ko‘ra so‘zlarni tashkil etgan belgilar 
orasidagi takrorlanadiganlari bor bo‘lgan holda bunday so‘zlar soni
ga, 
bu belgilarningbarchasi har hil bo‘lgan holda 
ga teng. 
Misol
. 
1)
20 ta belgidan tashkil topgan alfavit berilgan bo‘lsin.
Uzunligi 3 ga teng bo‘lgan so‘zlar sonini sanab chiqaylik. Bunda belgilarning 
barchasi takrorlanmasin. 
Yechilishi.
2) 
20 ta belgidan tashkil topgan alfavit berilgan bo‘lsin.
Uzunligi 3 ga teng bo‘lgan so‘zlar sonini sanab chiqaylik. Bunda belgilarning 
ayrimlari takrorlanishi mumkin. 
Yechilishi.
. ■