Takrorsiz va takroriy o’rin almashtirishlar
O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARNI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
MUSTAQIL ISH
DISKRET TUZILMALAR
010-021 guruh talabasi
Bajardi: Lutfullayev Murodjon
Tekshirdi: Narmanov O.A
Takrorsiz va takroriy o’rin almashtirishlar.
Reja:
I Kirish:
Kombinatorika qanday bo’lim?
II Asosiy qism:
Takrorsiz o’rinlashtirishlar
Takrorsiz o’rin almashtirishlar
Takroriy o’rin almashtirishlar
III Xulosa
Kombinatorika – diskret matematikaning bir bo‘limi bo‘lib, u ehtimollar nazariyasi, matematik mantiq, sonlar nazariyasi, hisoblash texnikasi va kibernetika sohalarida qo‘llanilgani uchun muhim ahamiyatga ega.
Insoniyat o`z faoliyati davomida ko‘p marotaba ayrim predmetlarni barcha joylashtirish usullari sonini sanab chiqish yoki biror bir harakatni amalga oshirishdagi barcha mavjud usullarni aniqlash kabi masalalarga duch keladi.
1) 26 kishini kassada navbatga necha xil usulda joylashtirish mumkin?
2) Xokkey bo‘yicha olimpiya birinchiligida necha xil usulda oltin,
kumush va bronza medallarini taqsimlash mumkin.
Bunday tipdagi masalalarga kombinatorika masalalari deyiladi.
Kombinatorika masalalarini yechish asosiy ikki turga bo`linadi:
a) qism to`plamlarni tanlashga ko`ra;
b) elementlar tartibiga ko`ra.
Qism to`plamlarni tanlash usuli tanlanma tushunchasi bilan bog`liq.
Ta`rif 1. n elementli An to`plamdan k elementli qism to`plam ajratib olish (n,k) tanlanma deyiladi, bunda k - tanlanma hajmi deyiladi.
Ajratilgan qism to‘plamning har bir elementi bilan 1 dan n gacha bo`lgan sonlar o`rtasida bir qiymatli moslik o`rnatilgan bo‘lsa, to‘plam tartiblangan tanlanma, aksincha tartiblanmagan deyiladi.
Agar to‘plam elementlaridan biror bir ro‘yxat tuzib, keyin har bir elementga ro‘yxatda turgan joy raqami mos qo‘yilsa, har qanday chekli to‘plamni tartiblash mumkin. Bundan ko`rinadiki, bittadan ortiq elementi bo`lgan to‘plamni bir nechta usul bilan tartiblash mumkin. Agar tartiblangan to`plamlar elementlari bilan farq qilsa, yoki ularning tartibi bilan farq qilsa, ular turlicha deb hisoblanadi. Ta`rif 2. Agar tanlangan qism to`plamda elementlar tartibi ahamiyatsiz bo`lsa, u holda tanlanmalarga (n,k) guruhlash deyiladi va Сnk ko`rinishida belgilanadi. C – inglizcha “combination”, ya`ni “guruhlash” so`zining bosh harfidan olingan. Tanlanmalarda elementlar takrorlanishi va takrorlanmasligi mumkin.
Ta`rif 3. Elementlari takrorlanuvchi tartiblanmagan (n,k) tanlanmaga n
elementdan k tadan takrorlanuvchi guruhlash deyiladi va
ko`rinishida belgilanadi.
Ta`rif 4. Elementlari takrorlanuvchi tartiblangan (n,k) tanlanma n
elementdan k tadan takrorlanuvchi joylashtirish deyiladi va
kabi belgilanadi. A inglizcha “arrangement” – “tartibga keltirish” so`zining bosh harfidan olingan.
Ta`rif 5. Agar tartiblangan tanlanmalarda elementlar o`zaro turlicha bo`lsa, u holda takrorlanmaydigan joylashtirish deyiladi va Аnk kabi belgilanadi.
Ta`rif 6. n tadan n ta tartiblangan tanlanmaga o`rin almashtirish deyiladi va Pn kabi belgilanadi. O`rin almashtirish joylashtirishning xususiy xoli hisoblanadi. P inglizcha “permutation” – “o`rin almashtirish” so`zining bosh harfidan olingan.
Misol. A3 {m,n,l} to`plamning 3 ta elementdan 2 tadan barcha tartiblangan va tartiblanmagan, takrorlanuvchi va takrorlanmaydigan tanlanmalarini ko`rsating.
А32 {m;n},{m;l},{n;l},{n;m},{l;m},{l;n}=6 ta takrorlanmaydigan
joylashtirish; ta takrorlanuvchi guruhlashlar mavjud.
Ta`rif. Agar S to`plamdan A qism to`plamni n usul bilan tanlash mumkin bo`lsa, undan farqli boshqa B qism to`plamni m usulda tanlash
mumkin bo`lsa va bunda A va B larni bir vaqtda tanlash mumkin bo`lmasa, u holda S to`plamdan AB tanlanmani nm usulda olish mumkin. Agar AB bo’lsa, u holda A va B to’plamlar kesishmaydigan to’plamlar deyiladi. Xususiy holda, agar barcha i, j 1,2,...,k, i j lar uchun Ai Aj bo’lsa, u holda S A1 A2 ...Ak to’plam S to’plamning o’zaro kesishmaydigan qism to’plamlari yoki oddiygina qilib bo’laklari deyiladi.
Demak, yig’indi qoidasida A va B lar S to’plamning bo’laklaridir.
Ta`rif. Agar S to`plamdan A tanlanmani n usulda va har bir n usulda
mos B tanlanmani m usulda amalgam oshirish mumkin bo`lsa, u holda A va
B tanlanmani ko`rsatilgan tartibda n m usulda amalga oshirish mumkin.
To’plamlar nazariyasi nuqtai nazaridan qaraydigan bo’lsak, bu qoida
to’plamlarning Dekart ko’paytmasi tushunchasiga mos keladi.
Misol. “Zukhrotravel” turistik kompaniyasi “Xiva – Chirchiq” yo`nalishida
sayohat uyushtirmoqchi bo`lsa, necha xil usulda sayohat smetasini ishlab chiqish
mumkin.
Xivadan Chirchiqqa to`g`ridan to`g`ri jamoat transporti yo`q, shuning uchun
“Xiva – Toshkent – Chirchiq” yo‘nalishi bo‘yicha harakatlanishga to`g`ri keladi.
Xivadan Toshkentga samolyo’t, avtobus yoki poyezdda yetib borish
mumkin, demak, 3 xil usuldan birini tanlash mumkin;
Toshkentdan Chirchiqqa esa avtobus yoki poyezdda borish mumkin, ya`ni 2
xil tanlanma mavjud.
“Xiva – Chirchiq” sayohatini 32 6 xil usulda tashkil qilish mumkin.2.3.3. Ko`paytma qoidasini umumlashtirish.
Ta`rif. Aytaylik birin-ketin k ta harakatni amalga oshirish kerak bo‘lsin.
Agar birinchi harakatni n1 usulda, ikkinchi harakatni n2 usulda, va hokazo k -
harakatni nk usulda amalga oshirish mumkin bo‘lsa, u holda barcha k ta harakat
n1 n2 n3 ... nk usulda amalga oshiriladi.
Misol 1. Ikkinchi bosqich talabalari III semestrda 12 ta fanni o`rganishadi.
Seshanba kuniga 3 ta turli fanni nechta usulda dars jadvaliga joylash mumkin?
Bu misolda 12 ta fanni takrorlamasdan 3 tasini joylashtirish kerak. Buning uchun
birinchi fanni 12 usulda, ikkinchi fanni 11 usulda va uchinchi fanni 10 ta usulda
tanlash mumkin. Ko`paytirish qoidasiga asosan 121110 1320 .
Demak, 3 ta turli fanni 1320 usulda joylash mumkin ekan.
Misol 2. Diskret matematika fanidan talabalar o`rtasida bo`ladigan olimpiadaning
mamlakat bosqichida 16 nafar talaba qatnashmoqda. Necha xil usulda I, II va III
o`rinlar taqsimlanishi mumkin?
Yechilishi: I o`rinni 16 talabadan biri egallashi mumkin. I o`rin sohibi
aniqlangandan keyin, II o`rinni qolgan 15 talabadan biri egallaydi va nihoyat III
o`rin qolgan 14 talabadan biriga nasib qiladi. Demak I, II va III o`rin g`oliblarini
161514 3360 xil usulda aniqlash mumkin.
Misol 3. 5 soniga bo`linadigan 4 xonali sonlar nechta?
Yechilishi: Masalada takrorlanuvchi joylashtirish haqida so`z bormoqda.
Birinchi xonaga Z {0;1;2;3;4;5;6;7;8;9} to`plamning 10 ta elementidan
bittasini tanlash mumkin, lekin 0 ni birinchi xonaga qo`yish mumkin emas, aks holda son 3 xonali bo`lib qoladi. Bo`linish belgisiga ko`ra son 5 ga bo`linishi
uchun 0 yoki 5 bilan tugashi kerak.
Demak, 1- xona raqami uchun 9 ta tanlash mavjud; 2- va 3- xona raqamlari uchun esa 10 ta tanlash usuli bor; 4- xona, ya`ni oxirgi raqam uchun 0 yoki 5 raqamlari bo`lib, 2 ta tanlash mavjud. U holda ko`paytirish qoidasidan foydalansak, 910102 1800 ta 5 ga bo`linadigan 4 xonali son borligini aniqlaymiz.
Agar biror m murakkab son berilgan bo’lsa, uning bo‘luvchilar sonini topish
uchun oldin tub sonlar ko’paytmasi shakliga keltiriladi:
bunda p1, p2,...., pn – tub sonlar, 1, 2,....,n daraja ko’rsatkichlari bo’lib, m
murakkab sonning bo‘luvchilari soni
(1 1)(2 1).... (n 1)
ga teng bo’ladi.
Misol. 48 sonining bo’luvchilari sonini topish uchun 48 24 3 ni topamiz.
U holda 48 ning bo‘luvchilari soni (4 1)(11) 52 10 ekanligi topiladi.
|
