“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
