Ii bob kombinatorika elementlari

6-  t e o r e m a   ( umumlashgan  qo‘shish  qoidasi) .  Juft-jufti  bilan 

kesishmaydigan ixtiyoriy chekli 

n

A

A

A

,...,

,

2

1

 to‘plamlar uchun 

n

n

A

A

A

A

A

A









...

...

2

1

2

1







 

tenglik o‘rinlidir. 

I s b o t i .   Teorema  shartiga  ko‘ra  barcha 

n

j

i

,

1

,



, 

j

i



,  indekslar  uchun 





j

i

A

A 

 bo‘lgani sababli 5- teorema asosida kerakli tenglikni hosil qilamiz. ■ 

7- t e o r e m a . Ixtiyoriy chekli 

n

A

A

A

A

,...,

,

,

3

2

1

 to‘plamlar uchun 













n

n

A

A

A

A

A

A

A

A

...

...

3

2

1

3

2

1









 













n

n

A

A

A

A

A

A







1

3

1

2

1

...

 















n

n

n

A

A

A

A

A

A

A

A

A













1

2

4

2

1

3

2

1

...

 

n

n

A

A

A







...

)

1

(

...

2

1

1









. 

munosabat o‘rinlidir. 

I s b o t i  o‘quvchiga havola qilinadi. ■ 

8- t e o r e m a  (umumlashgan ko‘paytirish qoidasi). Elementlari soni mos 

ravishda 

k

n

n

n

n

,...,

,

,

3

2

1

 bo‘lgan 

k

A

A

A

A

,...,

,

,

3

2

1

 to‘plamlardan faqat bittadan element 

olib tuzilgan 

k

 uzunlikka ega kortejlar soni 

k

n

n

n

n

...

3

2

1

ga tengdir. 

I s b o t i .  Teoremani  isbotlash  uchun  matematik  induksiya  usulini 

qo‘llaymiz. 

1



k

 bo‘lgan hol uchun teoremaning tasdig‘i trivialdir. 

Induksiya  usulining  bazasi  sifatida 

2



k

  bo‘lgan  holni  qaraymiz.  Bu  holda 

teoremaning  tasdig‘i  yuqorida  keltirilgan  ikkita  to‘plam  uchun  ko‘paytirish 

qoidasidan kelib chiqadi. 

Induksion o‘tish: teoremaning tasdig‘i 

s

k



 (

1

,

1





k

s

) uchun to‘g‘ri bo‘lsin, 

ya’ni, 

s

A

A

A

,...,

,

2

1

 to‘plamlardan faqat bittadan element olib tuzilgan 

s

 uzunlikdagi 

 

100 

kortejlar  soni 

s

n

n

n

...

2

1

  bo‘lsin  deb  faraz  qilamiz.  Teorema  tasdig‘ining 

1





s

k

 

uchun ham to‘g‘ri ekanligini ko‘rsatamiz. 

1

3

2

1

,...,

,

,



s

A

A

A

A

  to‘plamlardan  faqat  bittadan  element  olib  uzunligi  (

1



s

)ga 

teng  bo‘lgan  kortejlar  sonini  aniqlash  uchun  turlicha  usullardan  foydalanish 

mumkin.  Bu  yerda  quyidagi  usul  bilan  kerakli  natijani  olsa  bo‘ladi.  Dastlab 

uzunligi  birga  teng  bo‘lgan  kortejlarni  tuzamiz.  Uzunligi  birga  teng  bo‘lgan 

kortejlar  berilgan  to‘plamlarning  ixtiyoriy  biridan  faqat  bitta  elementni  tanlash 

yordamida  tuzilishi  ravshan.  Tabiiyki,  agar  uzunligi  birga  teng  kortejlar 

}

,...,

,

{

1

1

12

11

1

n

a

a

a

A



  to‘plamning  elementlaridan  tuzilsa,  bunday  kortejlar  soni 

1

n

ga 

tengdir. 

Uzunligi  birga  teng  kortejlardan  ixtiyoriy  birini,  masalan, 

11

a

ni  olib,  uning 

o‘ng  tomoniga 

1

A

 

to‘plamdan  boshqa  biror  to‘plamning,  masalan, 

}

,...,

,

{

2

2

22

21

2

n

a

a

a

A



  to‘plamning  elementlaridan  birini  joylashtirib,  birinchi 

koordinatasi 

11

a

 bo‘lgan uzunligi ikkiga teng 

2

n

ta kortejlar hosil qilamiz. Uzunligi 

birga  teng  kortej  sifatida 

1

n

ta  kortejlardan  ixtiyoriy  birini  olish  mumkinligini 

hisobga olib, hammasi bo‘lib uzunligi ikkiga teng 

2

1

n

n

ta kortejlarga ega bo‘lamiz. 

Uzunligi  ikkiga  teng  kortejlarning  har  biriga  o‘ng  tomondan 

1

A

  va 

2

A

 

to‘plamlardan boshqa biror to‘plamning, masalan, 

}

,...,

,

{

3

3

32

31

3

n

a

a

a

A



  to‘plamning 

3

n

ta  elementlaridan  birini  joylashtirib,  uzunligi  uchga  teng 

3

n

ta  kortejlar  hosil 

qilamiz. Bu  yerda  uzunligi  ikkiga teng kortej  sifatida 

2

1

n

n

ta  kortejlardan  ixtiyoriy 

birini  olish  mumkinligini  e’tiborga  olib,  uzunligi  uchga  teng 

3

2

1

n

n

n

ta  kortejlarni 

hosil qilamiz. 

Kortejlar  hosil  qilish  jarayonini  yuqoridagiga  o‘xshash  mulohazalar  bilan 

davom ettirib, bu kortejlarning har biriga o‘ng tomondan 

s

A

A

A

,...,

,

2

1

 to‘plamlardan 

boshqa 

}

,...,

,

{

)

1

(

2

)

1

(

1

)

1

(

1

s

n

s

s

s

s

a

a

a

A











  to‘plamning 

1



s

n

ta  elementlaridan  birini 

joylashtirib, uzunligi 

)

1

(



s

ga teng bo‘lgan 

1



s

n

ta kortejlar hosil qilamiz. Bu yerda 

ham  uzunligi 

s

ga  teng  kortej  sifatida 

s

n

n

n

...

2

1

ta  kortejlardan  ixtiyoriy  birini  olish 

 

101 

mumkinligini  e’tiborga  olamiz.  Shunday  qilib, 

s

n

n

n

...

2

1

  marta 

1



s

n

ta  kortej  hosil 

bo‘ldi. Demak, uzunligi 

)

1

(



s

ga teng bo‘lgan kortejlar 

1

2

1

...



s

s

n

n

n

n

tadir. ■ 

 

Muammoli masala va topshiriqlar 

 

1.  Uchnchi tartibli figurali sonlar qatnashgan amaliy misol keltiring. 

2.  1,  3,  6  va  8  raqamlaridan  foydalanib  o‘nli  sanoq  tizimida  bir,  ikki,  uch,  to‘rt 

xonali barcha sonlarni yozing. 

3.  Matematik 

induksiya 

usuli 

yordamida 

arifmetik 

va 

geometrik 

progressiyalarning  umumiy  hadlari  hamda  dastlabki 

n

ta  hadlari  yig‘indisini 

topish formulalarini isbotlang. 

4.  Matematik induksiya usulini qo‘llab quyidagi formulalarni isbotlang: 

a) 

n

n

n

n

n

2

1

...

2

1

1

1

2

1

1

2

1

...

4

1

3

1

2

1

1



























, 

b) 

























 













2

sin

2

)

1

(

sin

2

sin

)

sin(

...

)

sin(

sin

h

h

n

nh

x

nh

x

h

x

x

, bu yerda 

k

h



2



, 

Z



k

. 

5.   Matematik induksiya usulidan foydalanib quyidagi tasdiqlarni isbotlang: 

a) ixtiyoriy 

N



n

 uchun 

1

2

2

12

11







n

n

 son 133ga qoldiqsiz bo‘linadi; 

b) 

0

3

14

11

2







a

a

 (

a

 – butun son) tengsizlik o‘rinlidir; 

d) 





1

1

2

1

...

3

1

2

1

1















n

n

 tengsizlik o‘rinlidir, bu yerda 

N



n

 va 

2



n

. 

6. 

2

2

n

n



 tengsizlik o‘rinli bo‘ladigan barcha natural 

n

 sonlarni toping. 

7.  Ixtiyoriy 

n

 natural son va chekli 

A

 to‘plam uchun 

n

n

A

A



 tenglikning o‘rinli 

bo‘lishini matematik induksiya usuli yordamida isbotlang. 

8.  Yetti so‘mdan ortiq butun son bilan ifodalanuvchi pul to‘lovini faqat 3 so‘mlik 

va 5 so‘mliklar bilan amalga oshirish mumkinligini isbotlang. 

9.  “Kombinatorika”  so‘zidan  bitta  unli  yoki  undosh  harf  tanlash  imkoniyatlari 

sonini aniqlang.  

10. 

13 nafar qiz va 12 nafar o‘g‘il boladan tashkil topgan talabalar guruhidan 

 

102 

bir nafar talaba tanlash imkoniyatlari sonini aniqlang. 

11. 

“Kombinatorika”  so‘zidan  bitta  unli  va  bitta  undosh  harf  tanlash 

imkoniyatlari sonini aniqlang. 

12. 

Qiroatxonada  har  biri  ikki  o‘rinli  stollar  to‘rt  qatorga  sakkiztadan 

joylashtirilgan.  Haftaning  yakshanba  kunidan  tashqari  har  kuni  qiroatxona 

o‘quvchilarga  sakkiz  soat  xizmat  ko‘rsatadi.  Qiroatxonaning  bir  haftada 

o‘quvchilarga  mumkin  bo‘lgan  eng  ko‘p  xizmat  ko‘rsatish  vaqtini  (o‘rin



soat 

birligida) toping. 

13. 

Agar 

A

  va 

B

  shaharlarni  to‘rtta  yo‘l, 

B

  va 

C

  shaharlarni  esa  uchta  yo‘l 

bog‘lasa, u holda 

A

 shahardan 

B

 shahar orqali 

C

 shaharga borish imkoniyatlari 

sonini aniqlang. 

14. 

Shaxmat taxtasiga oq va qora shohlarni bir-biriga hujum qilmaydigan holda 

joylashtirish imkoniyatlari sonini toping. 

15. 

Shaxmat  taxtasiga  oq  va  qora  ruxlarni  bir-biriga  hujum  qilmaydigan  holda 

joylashtirish imkoniyatlari sonini toping. 

16. 

Yakkamualliflikda  yozilgan  Axmedovning 

A

n

ta,  Botirovning 

B

n

ta  va 

Davronovning 

D

n

ta kitoblardan 

a) bitta kitobni, b) turli mualliflarning ikkita kitobini, 

d) turli mualliflarning uchta kitobini 

tanlash imkoniyatlari sonini aniqlang. 

17. 

Agar tarkibida 

n

ta savoli bo‘lgan so‘rovnomaning har bir savoliga 

a) “ha” yoki “yo‘q”, b) “ha”, “yo‘q”, “bilmayman” 

degan  javobni  yozish  mumkin  bo‘lsa,  u  holda  so‘rovnomaning  savollariga 

berish mumkin bo‘lgan barcha javoblar imkoniyatlari sonini aniqlang. 

18. 

Universitetning “Matematik modellashtirish” kafedrasida 12 nafar professor-

o‘qituvchilar bo‘lib, ularning har biri o‘zbek va rus tillaridan tashqari yana hech 

bo‘lmasa  bitta  chet  tilini  biladi.  Professor-o‘qituvchilarning  10  nafari  tojik,  7 

nafari ingliz, 6 nafari esa olmon tilini biladi. Agar professor-o‘qituvchilarning 5 

nafari  tojik  va  ingliz,  4  nafari  tojik  va  olmon  hamda  3  nafari  ingliz  va  olmon 

tillarini bilsa, u holda o‘zbek va rus tillaridan tashqari a) uchala chet tilini, b) 

 

103 

ikkita  chet  tilini,  d)  faqat  ingliz  tilini  biladigan  professor-o‘qituvchilar  sonini 

aniqlang. 

19. 

Quyidagi formulani isbotlang: 

















)

,

min(

...

)

,

min(

...

)

,...,

max(

1

2

1

1

1

n

n

n

n

a

a

a

a

a

a

a

a

 

)

,...,

min(

)

1

(

...

)

,

,

min(

...

)

,

,

min(

1

1

1

2

3

2

1

n

n

n

n

n

a

a

a

a

a

a

a

a



















. 

 

Mustaqil ishlash uchun savollar 

 

1.  Kombinatorika predmeti nima? 

2.  Kombinatorika sohasida ilmiy tadqiqotlar olib borgan qaysi olimlarni bilasiz? 

3.  Kombinatorika  matematikaning  alohida  ilmiy  yo‘nalishi  sifatida  qachon 

shakllandi? 

4.  Figurali sonlar deganda nimani tushunasiz? 

5.  “Kombinatorika” iborasi kim tomonidan qachon kiritilgan? 

6.  Matematik induksiya usulidan foydalanib tasdiq qanday isbotlanadi? 

7.  Qo‘shish va ko‘paytirish qoidalari qanday ifodalanadi? 

8.  Umumlashgan qo‘shish va ko‘paytirish qoidalarini bilasizmi? 

 

2.2. Asosiy kombinatsiyalar 

To‘plam. Element. Kombinatsiya. O‘rin almashtirish. Betakror o‘rin almashtirish. 

O‘rin almashtirishlar soni. O‘rinlashtirish. O‘rinlashtirishlar soni. Gruppalash. 

Gruppalashlar soni. Ko‘paytirish qoidasi. Matematik induksiya usuli. Faktorial. 

 

2.2.1.  O‘rin  almashtirishlar.  Elementlari 

n

a

a

a

a

,...,

,

,

3

2

1

  bo‘lgan  to‘plamni 

qaraymiz. Bu to‘plam elementlarini har xil tartibda joylashtirib (yozib), tuzilmalar 

(kombinatsiyalar) hosil qilish mumkin, masalan, 

n

a

a

a

a

,...,

,

,

3

2

1

; 

n

a

a

a

a

,...,

,

,

3

1

2

; 

n

a

a

a

a

,...,

,

,

1

3

2

. 

Bu tuzilmalarning har birida berilgan to‘plamning barcha elementlari ishtirok etgan 

holda ular bir-biridan faqat elementlarining joylashish o‘rinlari bilan farq qiladilar. 

 

104 

1- t a ’ r i f . Shu usul yordamida hosil qilingan kombinatsiyalarning har biri 

berilgan 

}

,...,

,

,

{

3

2

1

n

a

a

a

a

 to‘plam elementlarining o‘rin almashtirishi deb ataladi. 

Aslida  “o‘rin  almashtirish”  iborasi  to‘plam  elementlarining  o‘rinlarini 

o‘zgartirish  harakatini  anglatsada,  bu  yerda  uni  shu  harakat  natijasidagi  hosil 

bo‘lgan  tuzilma  sifatida  qo‘llaymiz.  Bu  iboradan  uning  asl  ma’nosida  ham 

foydalanamiz. 

O‘rin almashtirishni ifodalashda uning elementlarini ajratuvchi belgi sifatida 

yuqorida  “,”  (vergul)  belgisidan  foydalanildi.  Ammo  bu  muhim  emas,  bu  yerda 

boshqa  belgidan  ham  foydalanish,  hattoki,  yozuvning  ixchamligi  maqsadida, 

elementlar  orasidagi  ajratuvchi  belgilarni  tushirib  qoldirilish  ham  mumkin.  Bu 

eslatma bundan keyin bayon etiladigan boshqa kombinatorik tuzilmalar uchun ham 

o‘rinlidir. 

To‘plam  tushunchasiga  asoslanib,  bu  yerda  qaralayotgan  o‘rin 

almashtirishlar  tarkibida  elementlarning  takrorlanmasligini  eslatib  o‘tamiz.  Shu 

sababli  bunday  o‘rin  almashtirishlarni  betakror  (takrorli  emas)  o‘rin 

almashtirishlar  deb  ham  atash  mumkin.  Ushbu  bobning  4-  paragrafida  takrorli 

o‘rin almashtirishlar ko‘riladi. 

Berilgan 

n

ta elementli to‘plam uchun barcha o‘rin almashtirishlar sonini 

n

P

 

bilan belgilash qabul qilingan

10

. 

Bitta  elementli 

}

{a

  to‘plam  uchun  faqat  bitta 

a

  ko‘rinishdagi  o‘rin 

almashtirish borligi ravshandir: 

1

1



P

. 

Ikkita  elementli 

}

,

{ b

a

  to‘plam  elementlaridan  o‘rin  almashtirishlarni  bitta 

elementli 

}

{a

  to‘plam  uchun 

a

  o‘rin  almashtirishidan  foydalanib  quyidagicha 

tashkil  qilamiz: 

b

  element 

a

  elementdan  keyin  yozilsa 

ab

  o‘rin  almashtirishga, 

oldin  yozilsa  esa 

ba

  o‘rin  almashtirishga  ega  bo‘lamiz.  Demak,  ko‘paytirish 

qoidasiga  (ushbu  bobning  1-  paragrafiga  qarang)  binoan  ikkita  o‘rin  almashtirish 

bor: 

2

1

2

2







P

. 

Uchta elementli 

}

,

,

{

c

b

a

 to‘plam uchun o‘rin almashtirishlar tashkil qilishda 

                                                           

10

 Fransuzcha “permution” so‘zi o‘rin almashtirish ma’nosini anglatadi. 

 

105 

ikkita  elementli 

}

,

{ b

a

  to‘plam  uchun  tuzilgan 

ab

  va 

ba

  o‘rin  almashtirishlardan 

foydalanish  mumkin.  Berilgan  to‘plamning 

c

  elementini 

ab

  va 

ba

  o‘rin 

almashtirishning  har  biriga  uch  xil  usul  bilan  joylashtirish  mumkin:  ularning 

elementlaridan  keyin,  elementlarining  orasiga  va  elementlaridan  oldin. 

Ko‘paytirish  qoidasini  qo‘llasak,  uchta  elementli 

}

,

,

{

c

b

a

  to‘plam  uchun  oltita 

(

3

2

1

6

3









P

)  har  xil  o‘rin  almashtirishlar  hosil  bo‘lishini  aniqlaymiz.  Ular 

quyidagilardir: 

 cba

bac, bca, 

cab,

abc, acb, 

. 

To‘rtta elementli 

}

,

,

,

{

d

c

b

a

 to‘plamni qarab, uchta elementli 

}

,

,

{

c

b

a

 to‘plam 

uchun tuzilgan oltita o‘rin almashtirishlarning har biriga 

d

 elementni to‘rt xil usul 

bilan  joylashtirish  imkoniyati  borligini  e’tiborga  olsak,  ko‘paytirish  qoidasiga 

ko‘ra, 

4

3

2

1

24

4











P

  bo‘lishini  topamiz.  Bu  yerda  barcha  o‘rin  almashtirishlar 

quyidagilardir: 

dabc

adbc

abdc

abcd

,

,

,

, 

dacb

adcb

acdb

acbd

,

,

,

, 

dcab

cdab

cadb

cabd

,

,

,

, 

dbac

bdac

badc

bacd

,

,

,

, 

dbca

bdca

bcda

bcad

,

,

,

, 

dcba

cdba

cbda

cbad

,

,

,

. 

Shu  tarzda  davom  etib  “

n

ta  elementli  to‘plam  uchun  barcha  o‘rin 

almashtirishlar  soni  birdan 

n

gacha  bo‘lgan  barcha  natural  sonlarning 

ko‘paytmasiga  teng”  deb  faraz  qilish  mumkin: 

n

n

P

n

)

1

(

...

2

1











.  Bu  farazning 

to‘g‘riligi quyidagi 1- teoremada isbot qilinadi. 

Dastlabki 

n

ta natural sonlar ko‘paytmasini 

!

n

 ko‘rinishida

11

 belgilash qabul 

qilingan,  ya’ni 

!

...

3

2

1

n

n











. 

!

n

  belgisidan  bunday  ma’noda  birinchi  bo‘lib  K. 

Kramp

12

 1808 yilda nashr etilgan algebra bo‘yicha qo‘llanmada foydalangan. 

                                                           

11

  Bu  yozuv  “en  faktorial”  deb  o‘qiladi;  faktorial  so‘zi  lotincha  “factor”  so‘zidan  olingan  bo‘lib,  ko‘paytuvchi 

ma’nosini anglatadi. 

12

  Kristian  Kramp  (Christian,  1760-1826)  –  olmon  matematigi.  Asosiy  ishlari  kombinatorika,  geometriya  va 

algebraga bag‘ishlangan. 

 

106 

n

...

3

2

1







 ifodada 

1



n

 bo‘lganda faqat 1 soni ishtirok etadi, shuning uchun, 

ta’rif sifatida 

1

!

1



 deb hisoblash qabul qilingan. Bundan tashqari, 

0



n

 bo‘lganda 

esa 

!

n

  ifoda  umuman  ma’nosini  yo‘qotadi.  Lekin,  ta’rif  sifatida 

1

!

0



  deb  qabul 

qilinadi.