“KOMBINATORIKA ELEMENTLARI”
R E F E R A T
2
Reja:
1.Kambinato’rikaning yig’indi qoidasi
2. Ko’paytirish qoidasi
3. O’rinlashtirish
4. O’rin almashtirish
5. Gruppalashlar
6. Takrorlanuvchi o’rin almashtirishlar
7. KOMBINATORIK MASALALAR
Hulosa.
Foydalanilgan adabiyotlar.
3
Kirish.
O’zbekiston Respublikasi “Ta’lim to’g’risida”gi qonuni va “Kadrlar
tayorlash milliy dasturi”da oliy o’quv yurtlarida fanlarni o’qitishda
innavatsion texnalogiyalarini qo’llash orqali talabalarning fanlarga bo’lgan
qiziqishlarini oshirish, olingan ilmiy bilimlar asosida dunyoqarashini, yuqori
ma’naviy - ahloqiy fazilatlarini, estetik didni shakillantirib, ta’limning hayot
bilan mustahkam aloqalarini ta’minlashga etibor qaratilishi takitlangan.
Bu ulkan vazifalarni amalga oshirish uchun talabalarining, xususan
matematika fani talabalari darsga ilmiy jixatdan mustaxkam tayorgarlik
ko’rishlari bilan bir qatorda milliy g’oya va nazariyalar ustida ham masuliyat
bilan izlanishlariga to’g’ri keladi.
Maskur kurs ishi oliy o’quv yurtida matematika dasturiga moslab yozilgan
bo’lib bunda kombinatorika elementlarini sodda va tushunarli tilda bayon
etishga harakat qilingan.
Ko’pgina amaliy masalalarni hal qilishda to’plamlarning elementlari
ustida turlicha gruppalash, amallar va hokazo ishlar bajarishga tog’ri keladi.
Matematikaning shu doiradagi masalalari bilan shug’ullanadigan tarmog’i
kombinatorika deb ataladi.
Masalan: 3 ta yer uchastkasining biriga qovun, biriga tarvuz, biriga
bodring ekish mo’ljallangan. Bu poliz ekinlarini uchastkalarga necha xil
usul bilan almashlab ekish mumkin. Poliz ekinlarining turi a, b, c bo’sin, u
holda u ekinlarni 3 ta uchastkaga abc, acb, bac, bca, cab, cba usullarda ekish
mumkin.
4
1. KOMBINATORIKANING YIG’INDI 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.
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. Yani:
a) r (A B) = r (A) + r (B) = n + m
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’plamlardir.
U
holda.
r
(A1A2…An)=r(A1)+r(A2)+…+r(An)
b) A va B to’plamlar umumiy elementga ega bo’lsin.
r (A B) = r (A) + r (B) – r (A B)
A1 A2 … An to’plam uchun bu holni umumlashtiramiz. Ya’ni bu berilgan n ta
to’plam umumiy elementga ega bo’lsa, u holda bu to’plamlar birlashmasining
elementlari soni quyidagicha bo’ladi:
r (A1 A2 … An) = r (A1) + r (A2) +… + r (An) – r (A1 A2) – r (A2 A3) …-
r (An-1 An ) + r (A1 A2 A3) +…+ (-1n-1) r (A1 A2…An).
Ya’ni n ta to’plam birlashmasining elementlari soni shu to’plamlar
elementlari soniga juft sondan olingan to’plamlar kesishmalarining soni manfiy
ishora bilan toq sondagi to’plamlar kesishmalarining elementlari soni musbat
ishora bilan qo’shilishiga teng bo’ladi. Bu yig’indi A1 A2 …An to’plamlar
birlas00hmasining elementlari sonini bildiradi.
5
2. KO’PAYTIRISH QOIDASI
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.Bu
juftliklarni tuzaylik.
X = {x1, x2 …xn} va Y = {y1, y2,…ym}
XY
(x1; y1) (x1; y2) …(x1; ym)
(x2 ;y1) (x2 ;y2)…(x2; ym)
…………………………
(xn; y1) (xn; y2)…(xn; ym)
Bu yerda har bir satrda m ta juftlik bor bo’lib,har bir ustunda n ta juftlik bor
bo’lib,hammasi bo’lib bu yerdagi juftliklar soni m*n juftlik bor.
r (X Y) = r (X) · r (Y)
Bu qoida n ta to’plam uchun ham to’g’ri.
r (X1 X2 … Xn) = r (X1) · r (X2) …· r (Xn)
6
(n - 1) qator
(n - 1) qator
3. O’RINLASHTIRISH
Ta’rif: n ta elementni k tadan o’rinlashtirish deb k tadan bitta elementi yoki
elementlarining tartibi bilan farq qiluvchi gruppalarga (kombinasiyalarga) aytiladi.
Teorema: n elementni k tadan o’rinlashtirishlar soni
Akn = n (n-1) (n-2)…n- (k-1) ga teng.
Isbot. a, b, c, d…f n ta elementni 2 tadan o’rinlash tuzaylik.
ab, ac, ad…af
ba, bc, bd…bf
ca, cb, cd…cf
da, db,dc…df
……………..
fa, fb, fc…fd
n-1 gruppa
Demak, A1n = n, A2n =n (n-1)
n elementni 2 tadan o’rinlashtirish soni. Shu n ta elementni 3 tadan
o’rinlashtiraylik.
abc, abd…abf
acb, acd …asf
adb, adc…adf
……………..
afb, afc…afd
bac,bad,…baf
bca,bcd,…bcf
bda,bdc,…bdf n ta
……………..
bfa,bfc,…bfd
cab,cad,…caf
cba,cbd,…cbf
(n - 1) qator
n qator
n · (n - 1)
7
cda,cdb,…cdf
……………..
cfa,cfb,…cfd
dab,dac,…daf
dba,dbc,…dbf
dca,dcb,…dcf
……………..
dfa,dfb,…dfc…
n-2 gruppa
Demak, n ta elementni 3 tadan o’rinlashtirishlar soni
A3n = n (n-1) (n-2) bo’ladi.
Xuddi shutartibda n elementni 4 tadan o’rinlashtirishlar soni
A4n = n (n-1) (n-2) (n-3) ekanligini topish mumkin.Bu xulosalarimizni
umumlashtirsak
Akn = n (n-1) (n-2)…(n-(k-1))
Demak, n elementni k tadan o’rinlashtirishlar soni haqiqatdan
Akn = n (n-1) (n-2)…(n-(k-1)) bo’ lar ekan.
(n - 1) qator
8
4. O’RIN ALMASHTIRISH
Ta’rif: n elementni n tadan o’rinlashtirishlar o’rin almashtirishlar deyiladi.
O’rin almashtirishlar Pn bilan belgilanadi.O’rin almashtirishlar sonini
o’rinlashtirishdagi k ning o’rniga n ni qo’yib keltirib chiqarish mumkin.
A
k
n = n (n-1)…(n-(k-1)) (1) k = n
A
n
n = n (n-1)…(n-(n-1)) = n (n-1) (n-2)…1=1·2·3·…(n-2) (n-1)n = n!
Pn =A
n
n = n!
Demak, n elementni o’rinlashtirishlar soni n faktorialga teng.Birdan n gacha
bo’lgan sonlar ko’paytmasi factorial deyiladi.
Pn = n!
9
5. GRUPPALASHLAR
Ta’rif: n ta elementni k tadan gruppalashlar deb kamida 1 tadan elementi
bilan farq qiluvchi o’rinlashtirishlarga aytiladi.
Teorema: n elementni k tadan gruppalashlar soni
Ckn = Akn / Pk ga teng
Isbot: Dastlab 4 ta elementdan 3 tadan a,b,c,d o’rinlashtirishlar tuzaylik.
abc, abd, acd, bcd
acb, adb, adc, bdc
bac, bad, bca, bda
cab, cad, cbd, cba
cda, cdb, dab, dbc
dac, dca, dba, dcb
4 ta
A34 = 24 = 6 · 4
P3 = 6 = 1 · 2 · 3 = 6
Ckn = Akn / Pk = 4 · 3 · 2 / 1 · 2 · 3 = 24 / 6 = 4
Ckn = 4
Demak, bu to’g’ri bo’ladi.
Ckn = Akn / Pk
Ckn = n (n-1) (n-(k-1) / k!
10
6. TAKRORLANUVCHI O’RIN ALMASHTIRISHLAR
Ta’rif: bir necha elementi bir xil bo’lgan n ta elementni o’rin almashtirish
takrorlanuvchi o’rin almashtirish deyiladi.
k ta elementi bir xil bo’lgan n ta elementni o’rin almashtirishlar soni Pn(k)
bilan yoziladi.
Bu n ta element turli xil bo’lganda Pn = n! edi. Uning k ta elementi bir xil
bo’gani uchun bu elementlar o’rin almashtirilib hosil qilingan gruppalarning
hammasi bir xil.O’shancha gruppaning bittasinigina hisobga olinib n! ta gruppa k!
marta kamayadi. Demak, a,b, c ,c , c ,c ,…c ,d…f (n) O’rin almashtirishlar soni
Pn (k) = n!/k! bo’lar ekan.
n ta elementning k tasi bir xil bo’lishi bilan yana m tasi bir xil bo’lsin.
a, b, b, b…
b , c, c, c…c d…f(n)
Bu holda o’rin almashtirishlar soni yana m marta kamayadi.
Pn (m,k) = n!/k!m! (7)
11
7. 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
n
m 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
)
(
Y
n X
=?
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
)
(
Y
n X
=1 (2)
formulaga ko’ra
)
(
Y
n X
=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
12
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)
n()
(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
n
m 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,
XxY={(1,a),(2,a),(3,a),(4,a),(5,a), (1;b),(2;b),(3;b),(4;b),(5;b)}-dekart
ko’paytma hosil bo’ladi. Bunda n(
10
5 2
) ( )
(
)
n X n Y
XxY
bo’lgani uchun A dan
C ga 10 usul bilan boorish mumkinligi kelib chiqadi.
6 - misol. Nechta turli raqamlar bilan yozilgan ikki xonali sonlar bor?
Yechish. Birinchi raqamni 9 usul bilan ikkinchi raqamni ham 9 usul bilan tanlash
mumkin. Qoidaga ko’ra hammasi bo’lib
81
9 9
ta ikki xonali son bor. Bunda 0
dan boshlab o’liklar raqamidan boshqa raqamlar nazarda tutiladi.
3.Takrorlanadigan o’rinlashtirishlar X={x1,x2,…,xm} to’plam berilgan bo’lsin. Bu
to’plam elementlaridan uzunligi k gat eng bo’lgan mk kortejlar tuzish mumkin:
k
k
m
A m
Buni m elementdan k tadan takrorlanadigan o’rinlashtirishlar diyiladi.
7 - misol. 3 elementli x={1,2,3} to’plam elementlaridan uzunligi ikkiga teng
bo’lgan nechta kortish tuzish mumkin.
Yechish.
9
32
2
3
A
ta kortij tuzish mumkin. Mana ular.
(1;1) (1;2), (1;3)
13
(2;1) (2;2), (2;3)
(3;1) (3;2);(3;3)
8 - misol. 6 raqamli barcha telifon nomerlar sonini toping.
Yechish. Telifon nomerlar 0 dan 9 gacha bo’lgan o’nta raqamdan tuzilgani uchun
10 elementdan tuzilgan barcha tartiblangan uzunligi 6 ga teng bo’gan kortijlar
sonini topamiz:
1000000
106
6
10
A
4. Takrorlanmaydigan o’rin almashtirishlar. Malumki m elementli X to’plam
elementlarini to’rli usullar bilan tartiblashlarning umumiy soni
Pm=
12 m m
! ga temg
9 - misol. 5 ta talabani 5 stulga necha xil usul bilan o’tqazish mumkin?
Yechish. Masala 5 elementdan 5 tadan takrorlanmaydigan o’rin almashtirishlar
sonini topishga keltiradi. P5=5!=
1 2 3 4 5 120
Demak, ularni 120 xil usul bilan o’tirg’zish mumkin
5. Takrorlanmaydigan o’rinlashtirishlar. m elementli X to’plamdan tuziladigan
barcha tartiblangan n elementli to’plamlar soni
)!
(
!
)1
(
)1
(
n
m
m
n
m
m
An
m
ga teng.
10 - misol. Guruhdagi 25 talabadan tanlovga qatnashish uchun 2 talabani
necha xil usul bilan tanlash mumkin.
Yechish.
600
24 25
23
2
1
25 24 25
2
1
!
23
!
25
2
25
A
usul bilan tanlash mumkin.
11- misol. 8 kishidan sardor, oshpaz, choyxonachi va navbachilardan iborat. 4
kishini tanlash kerak. Buni necha xil usulda amalga oshirish mumkin?
Yechish. Bu masala 8 keshidan 4 tadan takrorlanmaydigan o’rinlashtirishlar sonini
topishga keltiriladi. Demak,
1680
8 7 6 5
4
8
A
usul bilan 4 kishini tanlash
mumkin.
6. Takrorlanmaydigan guruhlashlar. M elementli X to’plamning k elementli qism
to’plamlari soni
)! !
(
!
n n
m
m
P
A
C
m
n
m
n
m
14
formula bo’yicha topiladi.
12 - misol. Kursdagi 20 talabadan ko’pirda ishtirok etish uchun 5 talabani necha xil
usulda tanlah mumkin.
Yechish. Ko’rik ishtirikchilarning tartibga ahamiyatga ega bo’lmagani uchun 20
elementli to’plamning 5 elementli qism to’plamlari soni nechtaligini topamiz:
10704
2 17 6 19 4
15 1 2 3 4 5
2 3
1
20
2 3
1
!5!
15
!
20
5
20
C
Demak, 5 talabani 10704 usul bilan tanlash mumkin ekan.
13 - misol. 6 ta har xil rangli qalamdan 4 xil rangli qalamni necha xil usul bilan
tanlash mumkin.
Yechish.
15
5 3
2 1 2 3 4
1
2 3 4 5 6
1
!4!2
!6
4
6
C
xil usul bilan tanlash mumkin.
Endi chikli X to’plam qism to’plamlari sonini topish haqidagi masalani qaraymiz.
Uni hal qilish uchun istalgan tarzda x to’plamni tartiblaymiz. Sung har bir qism
to’plamni m uzunligidagi kortej sifatida shifirlaymiz: qisim to’plamga kirgan
element o’rniga 1, kirmagan element o’rniga 0 yozamiz. Masalan, agar
X={x1;x2;x3;x4;x5} bolsa, u holda (0;1;1;0;1) kortej {x2,x3,x5} qism to’plamini
shiflaydi, (0;0;0;0;0) kortej esa bo’sh tuplam, (1;1;1;1;1) kortej esa X tuplamning
o’zini shifirlaydi. Shunda qisim tuplamlar soni ikkta {0;1} elementdan to’zilgan
barcha m uzunlikdagi kortejlar soniga teng bo’ladi:
m
Am
2 2
.
14-misol. X={a;b;c;} to’plamning barcha qism to’plamlarini yozing, ular nechta
bo’ladi.
Yechish. , {a}, {b}, {c}, {a;b}, {a;c}, {b;c}, {a;b;c} lar X to’plamning barcha
qisim to’plamlari bo’lib ularning soni 23=8 ga teng.
15
Foydalanilgan adabiyotlar:
1. L.P.Stoylova, A.M.Pishkalo “Boshlang’ich matematika kursi asoslari”, Darslik,
Toshkent, “O’qituvchi”-1991 yil.
2. A. Xudoyberganov “Matematika”, Darslik, Toshkent, “O’qituvchi”-1980 yil.
3. N.Ya.Vilenkin va boshqalar “Matematika”, Moskva, “Prosvesheniya”-1977 y.
4. N.Ya.Vilenkin va boshqalar “Zadachnik praktikum po matematike”, Uchebnik,
Moskva, “Prosvesheniya”-1977 y.
5. P.Ibragimov “Matematikadan masalalar to’plami”, O’quv qo’llanma, Toshkent,
“O’qituvchi”-1995 yil.
6. P.Azimov, H.Sherboyev, Sh.Mirhamidov, A.Karimova “Matematika”, O’quv
qo’llanma, Toshkent, “O’qituvchi”-1992 yil.
7. J. Ikromov “Maktab matematika tili”, Toshkent, “O’qituvchi”-1992 yil.
8. P.P.Stoylova, N.Ya.Vilenin “Seliye neotritsatelniye chisla”, Moskva,
“Prosvesheniya”-1986 y
9. A.M.Pishkalo, P.P.Stoylova “Sbornik sadach po matematike”, Moskva,
“Prosvesheniya”-1979 y.
10.
T.Yoqubov, S.Kallibekov “Matematik mantiq elementlari”, Toshkent,
“O’qituvchi”-1996 yil.
11.
T.Yoqubov “Matematik mantiq elementlari”, Toshkent,“O’qituvchi”-1983 y.
12.
С. И. Новоселов “Специальный Курс Элементарной Алгебры” 1958-йил.
13.
www.ziyonet.uz
16
