Referat mavzu: kombinatorika

O`zbekiston Respublikasi Oliy va O`rta maxsus Ta`lim Vazirligi

Nizomiy nomidagi Toshkent Davlat pedagogika Universiteti

REFERAT
Mavzu: KOMBINATORIKA ELEMENTLARI. TAKRORLANADIGAN VA TAKRORLANMAYDIGAN O'RIN ALMASHTIRISHLAR. TAKRORLANMAYDIGAN GRUPPALASHLAR. PASKAL BURCHAGI

Bajardi: Shakarimova Sayyora
Tekshirdi:
TOSHKENT-2022
MAVZU KOMBINATORIKA ELEMENTLARI. TAKRORLANADIGAN VA TAKRORLANMAYDIGAN O'RIN ALMASHTIRISHLAR. TAKRORLANMAYDIGAN GRUPPALASHLAR. PASKAL BURCHAGI
QOIDALARI
R E J A
1.Kombinatorika fani nimani o'rganadi?
2.Boshlang'ich sinf matematikasida kombinatorika fanining tutgan o'rni.
3.O'RINLASHTIRISH VA O'RINALMASHTIRISHLAR
Hayotda shunday masalalar uchraydiki, unda u yoki bu to'plamning qandaydir qism to'plamlarini ajratishga to'g'ri keladi. Masalan, agronomning yerlar orasidan eng mahsuldor yerni tanlash masalasi, tikuvchining sifatli mahsulotlar ishlab chiqarishi uchun yaxshi materialni tanlash masalasi, ofitserlarning soldatlar orasidan naryadlarni tanlashi, quruvchining mustahkam bino qurishi uchun qurilish materiallaridan oqilona foydalanishi, shaxmatchining yurishlardan yaxshi yurishni tanlashi , shofyorning manzilga etishi uchun barcha yo'llardan eng yaqinini tanlashi va hokazo . Bunday ko'rinishdagi masalalarda yer, material, ish , yurish u yoki bu kombinatsiyalardan foydalaniladi. Bunday ko'rinishdagi masalalarga kombinatorik masalalar deyiladi.
Matematikaning kombinatorik masalalari bilan shug'ullanuvchi bo'limiga kombinatorika fani deyiladi. Kombinatorika masalalari
birinchi marta ehtimollik nazariyasi vujudga kelishi munosabati bilan XVI - XVII asrlarda qaraldi. Kombinatorikada chekli to'plamlar, ularni to'plam ostilari, akslantirishlar, chekli to'plam elementlaridan tuzilgan kortejlar o'rganiladi. Shuning uchun kombinatorikani chekli to'plamlar nazariyasi qismi deb tushunish mumkin. Ko'pgina kombinatorik masalalarni echish asosan 2 ta qoida: yig'indi va ko'paytma qoidalariga asoslangan. Kombinatorikaning yig'indi qoidasi chekli to'plamlar birlashmasidagi elementlar sonini, ko'paytma qoidasi esa chekli to'plamlar dekart ko'paytmasidagi elementlar sonini topishdan iborat.
Shu qoidalar bilan tanishamiz.
Chekli A to'plam elementlari sonini n(A) deb belgilaylik. n ta elementdan iborat bo’lgan to'plamni n - tartibli to'plam deb ataymiz. Masalan, Agar A= {a,b,c,d,e,f} bo'lsa, u holda n(A)=6 , shuning uchun A to'plamni 6- tartibli to'plam deymiz.
A to'plam m ta elementdan tuzilgan bo'lsin: B to'plam esa n ta
elementdan tuzilgan bo'lsin . AUB to'plami nechta elementdan tashkil topgan? Bu masalaga hech ikkilanmasdan bu to'plamlar orasida ikki holni ko'rish mumkin:
A va В to'plamlar kesishmasi 0 to’plamdan iborat;
A va В to'plamlar o'zaro kesishmasi 0 to’plamdan iborat emas.
Agarda A va B to'plamlar kesishmasa, u holda AUB to'plami "m+n" ta elementga ega bo'ladi.
Misol: 1) A= {a,b,c,d} B={e,f,k} AUB= {a,b,c,d,e,f,k} n(A)=4 , n(B)=3 , A^B=0 , n(AUB)=7
A={oq, ko'k, qora}
B={qizil, sariq}
n(A)=3 , n(B)=2 , AnB=0 , n(AUB) =5
A=4 ta olma
B=6 ta anor, hamma meva nechta ?
n(A)=4 , n(B)=6 , A^B=0 , n(AUB)=10 shu qoidaga asoslanib boshlang'ich sinflarda masala va misollar tushuntiriladi.
Agar A va В to'plamlar kesishsa, (A ^B ^ 0) u holda to'plamlar birlashmasidagi elementlar soni har bir to'plam elementlar soni yig'indisi bilan , shu to'plamlar kesishmasidagi elementlar sonining ayirmasiga teng: n(AUB)=n(A)+n(B)-n(A n B)
Misol: 1) A={a,b,c,d,e} B={d,e,f,g} to'plamlar berilgan bo'lsin . Bunda: n(A)=5 , n(B)=4 Bu to'plamlar birlashmasini tuzsak:
AUB={a,b,c,d,e,f,g} yoki n(AUB)=7 n(Aⁿ B )=2 Demak ,(5+4)-2=7
Ingliz va nemis tillarini o'rganayotgan 100 o'quvchidan ingliz tilini 85 ta , nemis tilini 45 ta o'quvchi o'rganadi. Qancha o'quvchi ikkala tilni ham o'rganadi?
n(A)=85 talaba ingliz tilini o'rganuvchi n(B) = 45 talaba nemis tilini o'rganuvchi n(AUB)=100 ta talaba n(AUB)= n(A)+n(B)- n(A n B )
100= (85+45)-X X=(85+45)-100=30 ta
Agar to'plam 3 ta bo'lsa , quyidagi yig'indi qoidasi o'rinli : n(AUBUC)= n(A) + n(B)+ n(C) - n(A n B)- n(A n C) - n(B n C) + n(A n B n C )
Misol: A={a,b,c,d,e,f,g} B={a,e,g,l,k,o} C={a,b,d,f,o}
n(A)=7 , n(B)=6 , n(c)=5 , n(A n B)=3 n(A n C)=4 n(B n C)=2
n(A n B n C )=1
n(AUBUC)=7+6+5-2-3-4+1=10
Kombinatorikaning ikkinchi qoidasi, berilgan chekli to'plamlar elementlaridan tuzilgan kortejlar sonini topishdan iborat .
Shunday masalani qaraylik.
A={ai, a₂ ,...,a_m }va B= {bi, b₂, ...,b_n} to'plamlaridan nechta (a_k;bi) ko'rinishdagi juftlik elementlarini tuzish mumkin?
Bu elementlarni jadval ko'rinishida yozamiz:
(a1 b1), (a1 b₂), (a1 Ьз) ,...,(a1 bn)
(a₂ b1), (a2 b2), (a2 Ьз),. .. ,(a2 bn)
(a3 b1), (a3 b2), (a3 Ьз),. .. ,(a3 bn) ^(am ^b1^{), (a}m ^b2^{), (a}m ^ЬзХ - • • ^,(am ^bn⁾
bu erdan shu narsa ko'rinadiki , bu juftliklar m ta qator , har bir qator n ta elementdan iborat bo'ladi. Demak, umumiy juftliklar sonini mn ga teng .
Shunday qilib , m- tartibli A to'plam , n - tartibli B to'plam elementlaridan mn ta tartiblangan juftlikni tuzish mumkin.
Bunday tartiblangan juftliklar to'plamini A va B to'plamlar dekart ko'paytmasi deb aytgan edik. Shuning uchun quyidagi yozuv o'rinli: n(AxB)=n(A)xn(B) (1)
Ko'paytma qoidasining umumiy holi :
n(A₁ xA₂xA₃x xA_n)=n(A₁ )xn(A₂)x xn(A_n) (2)
ni ham isbotlash mumkin.
Kombinatorikada (1) ni quyidagicha ta'riflash mumkin:
Agar a elementni m usulda, b elementni n usulda tanlash mumkin bo'lsa, u holda (a;b) tartiblangan juftlikni mn usulda tanlash mumkin. Masala: A qishloqdan B qishloqqa 3 ta yo'l olib boradi. B qishloqdan C qishloqqa esa 2 ta yo'l olib boradi.A qishloqdan B qishloqni bosib o'tib C ga necha usulda borish mumkin
Yechish: A va B orasidagi yo'lni 1,2,3 sonlari bilan belgilaymiz. B va C qishloqlar orasidagi yo'lni a,b deb belgilaymiz.
2 a


U holda ko'paytma qoidasiga asosan 3 x 2=6 usulda A dan C ga B ni bosib o'tish mumkin: (1;a), (1;b), (2;a), (2;b), (3;a), (3;b)
Misol: A={a,b,c,d} B={m,f} to'plamlar berilgan. Berilgan to'plamlarning Dekart ko'paytmasi n (AxB)=n(A)xn(B) qancha elementni o'z ichiga oladi? Bu masalani quyidagicha ishlaymiz: n(AxB)=n(A)xn(B) n(A)=4 n(B)=2 n(A)xn(B)=4 2=8
Boshlang'ich sinf matematikasida kombinatorika fani asosiy o'rin tutadi, chunki ayrim kombinatorik misollar boshlang'ich sinfdanoq echiladi
1- sinf darsligidagi quyidagi misolga qaraymiz: Bog'da 5 tup olma bor edi, yana 3 tup olma ekishdi. Bog'dagi olmalar necha tup bo'ldi?
Bu masalani o'quvchi 5+3=8 tarzida echadi.
Ushbu masalani kombinatorik masalalarni echish , ya'ni yig'indi qoidasi tarzida bajarsak, quyidagicha bo'ladi.
A- bog'dagi 5 tup olma
B-yana ekilgan 3 tup olma
AUB- bog'dagi olmalarning necha tupligi
Misol: 10 m chit va 10 m satin sotib olishdi. 12 m matoni ishlatishdi. Necha metr mato qoldi?
Bu masalani yig'indi qoidasiga oid ekanligini tekshiramiz.
A-10m chit
B-10 m satin
C-12 m mato ishlatilgani
(AUB)\C necha metr mato qoldi?
Boshlang'ich sinf o'quvchisiga bu tarzda tushuntirish ancha murakkab bo'lganligi uchun , buni ularga ushbu misol tarzida o'rgatamiz: (10+10)-12=8 (m) - mato qoldi.
Xulosa qilib shuni aytish mumkinki, hayotdagi juda ko'p masalalar u yoki bu variantlar (kombinatsiyalar)ni qo'llab echiladi, boshqacha qilib aytganda, qulay imkoniyatlardan foydalanib echilar ekan , kombinatorika fani keng qo’llanishga ega. Bu fanning dastlabki tushunchalari boshlang'ich sinflardanoq o'rganiladi, shu sababli, bo'lajak boshlang'ich sinf o'qituvchilari kombinatorika bo'yicha ma'lum bilim , malaka va ko'nikmalarga ega bo'lishi kerak.
Quyidagi masalani qaraymiz: m-tartibli X to'plamdan uzunligi k ga teng qilib tuzilgan kortejlar soni topilsin.
Bu umumiy masalani echishdan oldin 4-tartibli X={ a,b,c,d} to'plamdan nechta uzunligi 2 ga teng bo'lgan kortejlarni tuzish mumkinligini qaraylik.Mumkin bo'lgan barcha juftliklar quyidagilar :
(a;a); (a;b); (a;c); (a;d);
(b;a); (b;b); (b;c); (b;d);
(c;a) (c;b); (c;c) ; (c;d);
(d;a); (d;b); (d;c); (d;d). demak ,bular 16 ta ekan.
Endi yuqoridagi umumiy masalani echaylik.X to'plam m-tartibli to'plam ekan, n(X)=m dir . Bu masalani echish uchun k dona X to'plamdan iborat to'plamlar dekart ko'paytmasidagi elementlar sonini topaylik.Dekart ko'paytmasi qoidasiga asosan:
n(XxXxXx xX)=n(X)- n(X) ■ n(X)- n(X) ■ n(X)
n(X)=m. Demak ,bu elementlar soni k dona m o'z-o'zining ko'paytmasiga
teng , ya'ni n(XxXxXx xX)=m mm.. ,.m=m^k
Shunday qilib, m -tartibli X to'plamdan uzunligi k ga teng bo'lgan kortejlar soni m^k ga teng
TA'RIF: m- tartibli to'plam elementlaridan ,uzunligi k ga teng qilib tuzilgan kortejlarga, m elementdan k tadan qilib tuzilgan elementlari takrorlanuvchi o'rinlashtirishlar deb aytiladi.Ularning soni esa A^k_m deb belgilanadi .
(A^k_m - frantsuzcha " arrangement"- o'rinlashtirish)
Demak ,
A^km = m^k
Misol: X = { 1,2,3,4,5 } to'plam elementlaridan nechta 2 xonali sonlarni
2 2
tuzish mumkin. A ₅=5 =25
Yuqoridagi elementlari takrorlanuvchi o'rinlashtirishlar formulasi quyidagi masalani echishga olib keladi :
" m- tartibli to'plam X dagi barcha to'plam ostilari soni nimaga teng ?" X to'plam elementlarini nomerlaymiz: X={x_b x₂,x₃,...,x_m} Har qanday A ^ X to'plam uzunligi m ga teng va faqat Ova 1 dan iborat kortej orqali ifodalash mumkin.Agar A to'plamda element mavjud bo'lsa o'sha yerda 1,mavjud bo'lmasa, 0 ni yozamiz:
Masalan: X={x_b x₂, x₃, X4} bo'lsa, A^X, A={ x₂,x4} ni (0,1,0,1) kortej sifatida tasvirlaymiz. Bu paytda yuqoridagi masalamiz," {0;1} to'plam elementlaridan tuzilgan uzunligi m ga teng kortejlar sonini topish" ga keladi.(l) formulaga asosan,bunday ko'rinishdagi kortejlar soni 2^m ga teng bo'ladi .
Misol: X= {a,b,c } to'plam -2 =8 ta to'plam ostiga ega.
TA'RIF : Agar X to'plam elementlari qanday dir tartibda nomerlangan bo'lsa , u holda bunday X-chekli to'plamga tartiblangan to'plam deb aytiladi.
Tartiblangan to'plam tushunchasi kortejlar tushunchasining xususiy holidir. Kortej larda elementlar takrorlanishi mumkin , lekin tartiblangan to'plamda elementlar takrorlanmaydi. Masalan: (a;b, a;c, b;d ) - korteji
tartiblangan to'plam bo'la olmaydi. (a, b , c, d , e , f ) - bu tartiblangan to'plamdir.
Biror bir to'plam elementlarini bir necha usulda tartiblash mumkin. Masalan: Talabalar to'plamini, viloyatlar bo'yicha, bo'ylariga qarab, alfavitga qarab va hakazo , tartibda joylashtirish mumkin.
X to'plam m-tartibli to'plam bo'lsin. Bu to'plam elementlarini necha usulda tartiblash mumkin?
X={xi, x₂, x₃,.x_m} - to'plamdagi xi elementlarni m usulda joylashtirish mumkin, x₂ elementni esa ( m-1) usulda joylashtirish mumkin , .va xokazo xm element faqatgina 1 marta tanlanadi, u holda ko'paytma
qoidasiga asosan , tartiblab chiqish soni m(m-1) ■ 1 ga teng.
1 dan m gacha bo'lgan sonlar ko'paytmasiga m! (faktorial) deb aytiladi.
Masalan: 3!= 1 ■ 2 ■ 3= 6
TA'RIF: m- tartibli tartiblangan to'plamga m elementdan iborat elementlari takrorlanmaydigan o'rin almashtirishlar deb aytiladi. Uning elementlar soni P_m deb belgilanadi. (P_m- frantsuzcha- " permutation" - o’rin almashtirish degan ma’noni anglatadi).
Demak, P_m=m(m-1)- 21=m! (2)
Yuqoridagi (2) formula elementlari takrorlanmaydigan o'rin almashtirishlar sonini topish formulasidir. Bundan tashqari elementlari takrorlanuvchi o'rin almashtirishlar formulasi mavjud: n=ni+n₂+n₃+....+n_k bo'lganda ,
Pn(ni,n2... .nk)= n!/ (ni!n2 !^nk!) (3)
Shunday masalani qaraylik: m - tartibli X to'plamda nechta tartiblangan k elementli to'plamni tuzish mumkin?
X={x_bx₂,x₃,...x_m} Bu to'plamdan k elementli tartiblangan to'plamlarni
tuzaylik: (x_b x₂,.. .xk); (x_bx₂,.. .x^xk+O ( x_b x₂,.. ,x_mx_m+1)
Bu erda x₁ ni m marta x₂ ni (m-1) marta, x₃ ni (m-2 ) marta va h .k. z.
x_k ni (m-k+1)marta tanlash mumkin.
Demak, m- elementli X to'plamdan k elementli qilib tuzilgan tartiblangan to'plamlar soni:
m(m-1)-... (m-k+1) ga teng bo’ladi.
TA'RIF: m- elementli X to'plamdan k elementli qilib tuzilgan tartiblangan to'plamga m elementdan k tadan qilib tuzilgan elementlari takrorlanmaydigan o'rinlashtirishlar deb aytiladi.
Ularning soni A^km deb belgilanadi.
Demak, A^k_m = m(m-1)(m-2)-... (m-k+1)
Yoki
A^k_m =m! /(m-k)! (4)
m=k da A^m_m=P_m= m!, bundan 0!=1 deb shartlashib olingan. Misol:{a,b,c,d} to'plam elementlaridan 3 tadan qilib tuzilgan tartiblangan to'plamlar sonini toping.
A³4=4!/(4-3)!=24
Garchand boshlang'ich sinflarda o'rinlashtirish hamda o'rin almashtirish terminlari ishlatilmasa hamki bu tushunchaga dahldor masalalar, topshiriqlar boshlang'ich sinf darsliklaridan o'rin olgan. Masalan:1) 3,4 , 5 , 6 . raqamlaridan foydalanib nechta uch xonali , nechta ikki xonali sonlarni tuzish mumkin?
2) 2, 3,4 sonlarini o'rnini necha usulda almashtirish mumkin va hakazo.

FOYDALANILGAN ADABIYOTLAR:

1 .Н.Я.Виленкин, А.М.Пишкало. Математика-М. «Просвещение», 1977.
А.А.Столяр, Л.П.Лелчук. Математика-Минск.1975.
Н.Я.Виленкин. Индукция. Комбинаторика. М. «Просвещение». 1976.
А.Худойберганов. Математика. Т. «Укитувчи», 1980.
Р.Иброхимов. Математикадан масалалар туплами. Т.
«У китувчи», 1995.