O‘zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al‑xorazmiy nomidagi toshkent axborot texnologiyalari universiteti sirtqi bo‘lim Telekommunikatsiyalar yo‘nalishi Algoritmlash va matematik modellashtirish kafedrasi

2.Guruhlash, o’rinlashtirish va o’rin almashtirishlar

Kombinatorika masalalarini yechish asosiy ikki turga bo’linadi:

1. 
   qism to’plamlarni tanlashga ko’ra;
   
2. 
   to’plam elementlari tartibiga ko’ra.
   

ⁿ elementli ^A_n 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 ⁿ 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.

С

n
Agar tanlangan qism to’plamda elementlar tartibi ahamiyatsiz bo’lsa,u holda tanlanmalarga (n, k)  guruhlash deyiladi va ^k
ko’rinishida belgilanadi. C – inglizcha “combination”, ya’ni
“guruhlash” so’zining bosh harfidan olingan.
Tanlanmada elementlar takrorlanishi va takrorlanmasligi mumkin.

Elementlari takrorlanuvchi tartiblanmagan
(n, k) tanlanmaga ⁿ
~ _k

elementdan k tadan takrorlanuvchi guruhlash deyiladi va ^С_n
ko’rinishida belgilanadi.

Elementlari takrorlanuvchi tartiblangan
(n, k) tanlanma ⁿ
~ _k

elementdan ^k tadan takrorlanuvchi o’rinlashtirish deyiladi va ^А_n
kabi belgilanadi. A inglizcha “arranjiment” – “tartibga keltirish”
so’zidan olingan.

А
Agar tartiblangan tanlanmalarda elementlar o’zaro turlicha bo’lsa, u

n
holda takrorlanmaydigan o’rinlashtirish deyiladi va belgilanadi.
^k kabi

va ^P_n
ⁿ tadan ⁿ ta tartiblangan tanlanmaga o’rin almashtirish deyiladi
kabi belgilanadi. O’rin almashtirish o’rinlashtirishning xususiy

holi hisoblanadi. ^P_n inglizcha “permutation” – “o’rin almashtirish”
so’zining bosh harfidan olingan.

Misol.

A₃  {a,b, c}
to’plamning 3 ta elementdan 2 tadan barcha

tartiblangan va tartiblanmagan, takrorlanuvchi va takrorlanmaydigan tanlanmalarini ko’rsating.

1. 
   
   3
   ^{А2  {a;b},{a;c},{b;c},{b;a},{c;a},{c;b}}=6 ta takrorlanmaydigan
   

o’rinlashtirish;

А₃
2) ^{~2  {a;a},{a;b},{a;c},{b;b},{b;c},{b;a},{c;a},{c;b},{c;c} 9}
ta takrorlanadigan

o’rinlashtirish;

3. 
   
   3
   ^{С2  {a;b},{a; c},{b; c} 3} ta takrorlanmaydigan guruhlash;
   

С₃
4) ^~2  ^{a;a},{a;b},{a;c},{b;b},{b;c},{c;c}^ 6
ta takrorlanuvchi guruhlash;

5) ^{P3  {{a,b,c},{a,c,b},{b, a,c},{b,c, a},{c, a,b},{c,b, a}}}=6 o’rin almashtirish
mavjud.

Kombinatorikaning asosiy qoidalari

Kombinatorikaning 1-qoidasi (yig’indi qoidasi):

Agar S to’plamdan A qism to’plamni ⁿ 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 mumkin.
A ∪ B
tanlanmani
n  m
usulda olish

Agar
A  B  
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
A_i  A_j  
bo’lsa, u holda
S  A₁  A₂ ...  A_k
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.

Misol. 410-18 guruh talabalari 16 nafar yigit va 8 nafar qizlardan iborat bo’lib, ular orasidan bir kishini ajratib olish kerak bo’lsa, ularning soni qo’shiladi va 16+8=24 talaba orasidan tanlab olinadi.

Kombinatorikaning 2-qoidasi (ko’paytma qoidasi):

Agar S to’plamdan A tanlanmani ⁿ usulda va har bir ⁿ usulda mos
B tanlanmani ^m usulda amalga oshirish mumkin bo’lsa, u holda A va

B tanlanmani ko’rsatilgan tartibda mumkin.
n  m
usulda amalga oshirish

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 chiqishi mumkin?
Yechilishi: 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 samolyot, 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. Demak, “Xiva – Chirchiq” sayohatini
^{3 2  6} xil usulda tashkil qilish mumkin va 6 хil narх taklif qilish
mumkin.

Ko’paytma qoidasini umumlashtirish:

Aytaylik birin-ketin k ta harakatni amalga oshirish kerak bo’lsin.

Agar birinchi harakatni
n₁ usulda, ikkinchi harakatni
n₂ usulda, va

hokazo k - harakatni ^nk usulda amalga oshirish mumkin bo’lsa, u holda

barcha k ta harakat
n₁  n₂  n₃  ... n_k
usulda amalga oshiriladi.

Misol. Ikkinchi bosqich talabalari 3-semestrda 12 ta fanni o’rganishadi. Seshanba kuniga 3 ta turli fanni nechta usulda dars jadvaliga joylash mumkin?
Yechilishi: Bu misolda 12 ta fanni takrorlamasdan 3 tasini o’rinlashtirish kerak. Buning uchun
birinchi fanni 12 usulda, ikkinchi fanni 11 usulda va

uchinchi fanni 10 ta usulda tanlash mumkin. Ko’paytirish qoidasiga
asosan 121110 1320 .
Demak, 3 ta turli fanni 1320 usulda joylash mumkin ekan.


Misol. Diskret matematika fanidan talabalar o’rtasida bo’ladigan olimpiadaning respublika bosqichida 16 nafar talaba qatnashmoqda. Necha xil usulda 1-, 2- va 3-o’rinlar taqsimlanishi mumkin?
Yechilishi: 3-o’rinni 16 talabadan biri egallashi mumkin. 1-o’rin sohibi aniqlangandan keyin, 2-o’rinni qolgan 15 talabadan biri egallaydi va nihoyat 1-o’rin qolgan 14 talabadan biriga nasib qiladi. Demak 1-, 2-

va 3-o’rin g’oliblarini
161514  3360
xil usulda aniqlash mumkin.

Misol. 5 soniga bo’linadigan 4 xonali sonlar nechta?
Yechilishi: Masalada takrorlanuvchi o’rinlashtirish 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,

9 10 10  2  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:

p

1
m  ^1
 p^2
... p^n

2

n
bunda p₁, p₂,...., p_n – tub sonlar,
₁, ₂, , _n
daraja ko’rsatkichlari

bo’lib, ^m murakkab sonning bo’luvchilari soni
(₁ 1)  (₂ 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)  (11)  5  2  10
ekanligi topiladi.