Ii bob kombinatorika elementlari

1-  t e o r e m a .  Qo‘shiluvchilar  tartibini  e’tiborga  olgan  holda  istalgan 

n

 

natural  sonning 

k

ta  qo‘shiluvchilarga  bo‘laklanishlari  soni  (

1



n

)ta  elementdan 

(

1



k

)talab gruppalashlar soniga teng, ya’ni 

1

1

)

,

(







k

n

C

k

n

B

. 

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

Yuqorida  bayon  etilgan  mulohazalar  yordamida  va  1-  teoremaga  tayangan 

holda  isbotlash  osonligini  ta’kidlab,  quyidagi  teoremani  boshqa  usul  bilan 

isbotlaymiz. 

2-  t e o r e m a .  Qo‘shiluvchilar  tartibini  e’tiborga  olgan  holda  ixtiyoriy 

n

 

natural sonning barcha bo‘laklanishlari soni 

1

2



n

ga teng, ya’ni 

1

2

)

(





n

n

B

. 

I s b o t i . Natural 

n

 sonning barcha bo‘laklanishlari to‘plamini 

)

(n

S

 deb, shu 

n

  sonning  birinchi  qo‘shiluvchisi 

i

ga  (

n

i

,...,

2

,

1



)  teng  bo‘lgan  bo‘laklanishlari 

to‘plamini  esa 

)

(n

S

i

  bilan  belgilaymiz.  Tushunarliki, 



n

i

i

n

S

n

S

1

)

(

)

(





  bo‘ladi.  Agar 

)

(n

S

i

 to‘plam elementlari sonini 

)

(n

Q

i

 deb belgilasak, yuqoridagi tenglikka asosan 







n

i

i

n

Q

n

B

1

)

(

)

(

  bo‘ladi.  Endi 

)

(

)

(

i

n

B

n

Q

i





  (

1

,...,

2

,

1





n

i

)  va 

1

)

(



n

Q

n

  tengliklarni 

hisobga olib, 

)

(

1

1

)

(

)

(

1

1

1

1

i

B

i

n

B

n

B

n

i

n

i























 

tenglikka ega bo‘lamiz. Bu tenglik ixtiyoriy 

n

 natural son uchun to‘g‘ri. Shuning 

uchun, bu tenglikdagi 

n

ni (

1



n

)ga almashtirib, 

)

(

2

)

(

)

(

)

(

)

(

1

)

1

(

1

1

n

B

n

B

n

B

n

B

i

B

n

B

n

i





















, 

ya’ni 

)

(

2

)

1

(

n

B

n

B





 (

,...

2

,

1



n

) ko‘rinishdagi rekurrent munosabatni hosil qilamiz. 

Bu rekurrent munosabat ketma-ket qo‘llanilsa, 

1

2

)

(





n

n

B

 kelib chiqadi. ■ 

2-  m i s o l .  To‘qqiz  qavatli  binoning  birinchi  qavatidan  sakkiz  kishi  liftda 

yuqoriga  ko‘tarilayotgan  bo‘lsin.  Agar  to‘qqizinchi  qavatga  liftdagi  kishilarning 

faqat  bittasi  chiqishi  shart  bo‘lsa,  lift  yo‘lovchilarining  bino  qavatlariga  chiqish 

imkoniyatlari sonini aniqlang. 

 

155 

Masalaning  shartiga  binoan,  liftdagi  sakkiz  kishidan  faqat  bir  kishi 

to‘qqizinchi qavatga chiqishi shart bo‘lgani uchun, qolgan yetti kishining ikkinchi 

qavatdan  sakkizinchi  qavatgacha  chiqishining  ko‘p  imkoniyatlari  bor.  Bu 

imkoniyatlar  soni  liftning  birinchi  va  to‘qqizinchi  qavatlar  orasidagi  to‘xtashlar 

sonidan  bog‘liq  bo‘lib,  yettining  barcha  bo‘laklanishlari  yordamida  ifodalanishi 

mumkin.  Masalan,  lift  binoning  ikkinchi  qavatidan  sakkizinchi  qavatigacha  faqat 

bir marta to‘xtab, liftdagi yetti kishi tushib qolgan bo‘lsa, u holda bu hodisa 

7

7



 

ko‘rinishdagi  bo‘laklash  vositasida  ifodalanadi;  agar  to‘qqizinchi  qavatgacha  lift 

ikki  marta  to‘xtab,  oldin  uch  kishi,  keyin  to‘rt  kishi  tushib  qolgan  bo‘lsa,  bu 

holatga 

4

3

7





 ko‘rinishdagi bo‘laklash mos keladi va hokazo. 

2- teoremadan foydalanib, yettining barcha bo‘laklanishlari soni 

64

2

2

6

1

7







 

ekanligini topamiz. Demak, agar to‘qqizinchi qavatga faqat bir kishi chiqishi shart 

bo‘lsa,  u  holda  lift  yo‘lovchilarining  bino  qavatlariga  chiqish  imkoniyatlari  soni 

64ga tengdir. Agar hal qilingan masalada to‘qqizinchi qavatga faqat bir kishining 

chiqishi  sharti  bo‘lmasa  edi,  u  holda  sakkizning  barcha  bo‘laklanishlari  sonini 

topishga to‘g‘ri kelar edi. ■ 

Endi  natural  sonlarni  qo‘shiluvchilar  tartibi  e’tiborga  olinmagan 

vaziyatda bo‘laklash masalasi bilan shug‘ullanamiz. 

Odatda, natural 

n

  sonning  ixtiyoriy 

k

ta  (

k

  –  natural  son, 

n

k



) 

k

a

a

a

,...,

,

2

1

 

qo‘shiluvchilarga  bo‘laklanishini  qandaydir  shartlarga,  masalan, 

k

a

a

a







...

2

1

 

yoki 

k

a

a

a







...

2

1

 tengsizliklarga bo‘ysunadigan qilib olish qulay bo‘ladi. 

Qo‘shiluvchilar  tartibi  e’tiborga  olinmagan  holda  natural 

n

  sonning 

k

ta 

qo‘shiluvchilarga  bo‘laklanishlari  sonini 

)

,

( k

n

R

 

bilan, 

uning 

barcha 

bo‘laklanishlari sonini esa 

)

(n

R

 bilan belgilaymiz. 

Bundan  keyin,  bo‘laklash  deganda  qo‘shiluvchilar  tartibi  e’tiborga 

olinmagan holdagi bo‘laklashni nazarda tutamiz. 

Tabiiyki, quyidagi tenglik o‘rinlidir: 







n

k

k

n

R

n

R

1

)

,

(

)

(

. 

 

156 

Osonlik  bilan  ko‘rish  mumkinki, 

1

)

1

(



R

, 

2

)

2

(



R

, 

3

)

3

(



R

, 

5

)

4

(



R

, 

7

)

5

(



R

, 

11

)

6

(



R

, 

15

)

7

(



R

. 

3- m i s o l . 8 uchun barcha bo‘laklashlar 1- jadvalda ifodalangan. Jadvaldan 

ko‘rinib turibdiki, 8 uchun, hammasi bo‘lib, 22 bo‘laklash imkoniyati bor: 

22

1

1

2

3

5

5

4

1

)

,

8

(

)

8

(

8

1

























k

k

R

R

. ■ 

Albatta,  yuqorida  keltirilgan  formula  yordamida  ixtiyory  natural 

n

  uchun 

uning  barcha  bo‘laklanishlari  sonini  aniqlash  mumkin.  Lekin 

n

  yetarlicha  katta 

qiymatga  ega  bo‘lganda  bu  formuladan  foydalanish  juda  ko‘p  hisoblashlar 

bajarishni  taqozo  qiladi.  Ushbu  bobning  navbatdagi  7-  paragrafida 

)

(n

R

ning 

qiymatini hisoblash uchun boshqacha yo‘l borligi ko‘rsatilgan. 

2.6.2.  Ferrers

39

  diagrammasi.  Natural 

n

  son 

k

ta 

k

a

a

a

,...,

,

2

1

  natural 

qo‘shiluvchilarnung yig‘indisi qilib bo‘laklangan bo‘lsin. 

2-  t a ’ r i f . 

k

ta  qatordan  tashkil  topgan  va  (yuqoridan  pastga  qarab 

hisoblaganda) 

i

-  qatorida 

i

a

ta  nuqtaga  ega  bo‘lgan  diagramma 

n

  sonni 

k

ta 

k

a

a

a

,...,

,

2

1

  natural  qo‘shiluvchilarnung  yig‘indisi  qilib  bo‘laklashga  mos  Ferrers 

diagrammasi deb ataladi. 

                                                           

39

 Ferrers (Norman Makleod, 1829 – taxminan 1894 yildan so‘ng vafot etgan) – ingliyz matematigi. 

1- jadval 

Qo‘shi-

luvchilar 

soni 

 

Bo‘laklanishlar 

Bo‘laklanis

hlar soni 

1 

8=8 

1

)

1

,

8

(



R

 

2 

8=7+1=6+2=5+3=4+4 

4

)

2

,

8

(



R

 

3 

8=6+1+1=5+2+1=4+3+1= 

=4+2+2=3+3+2 

5

)

3

,

8

(



R

 

4 

8=5+1+1+1=4+2+1+1=3+3+1+1= 

=3+2+2+1=2+2+2+2 

5

)

4

,

8

(



R

 

5 

8=4+1+1+1+1=3+2+1+1+1= 

=2+2+2+1+1 

3

)

5

,

8

(



R

 

6 

8=3+1+1+1+1+1=2+2+1+1+1+1 

2

)

6

,

8

(



R

 

7 

8=2+1+1+1+1+1+1 

1

)

7

,

8

(



R

 

8 

8=1+1+1+1+1+1+1+1 

1

)

8

,

8

(



R

 

 

 

157 

2- shakl 

2- расм 

Ferrers  diagrammasi  tushunchasiga  asoslangan  diagrammali  usul  deb 

yuritiluvchi  usul  sonlarni  qo‘shiluvchilar  yig‘indisi  qilib  bo‘laklash  masalalarini 

tahlil qilishda keng qo‘llaniladi. 

Bo‘laklashda  qo‘shiluvchilar  tartibi  e’tiborga  olinmaganligi  sababli  Ferrers 

diagrammasini tuzishda, odatda, uning qatorlaridagi nuqtalar soni yuqoridan pastga 

qarab o‘smaydigan, ya’ni 

k

a

a

a







...

2

1

 shart bajariladigan (yoki, kamaymaydigan 

ya’ni 

k

a

a

a







...

2

1

  shart  bajariladigan)  tartibga  rioya  qilinadi.  Bundan  tashqari, 

qatorlardagi  nuqtalar  diagrammaning  vertikal  ustunlarini  tashkil  etadigan  qilib 

tuziladi. 

3-  t a ’ r i f .  Shunday  tartibda  tuzilgan  diagramma  normal  Ferrers 

diagrammasi deb ataladi. 

4-  m i s o l .  14=5+3+2+2+1+1  bo‘laklashga  1-  shaklda  tasvirlangan  Ferrers 

diagrammasi mos keladi. Bu diagramma normal Ferrers diagrammasidir. ■ 

Ixtiyoriy  bo‘laklashga  mos  keluvchi  normal  Ferrers 

diagrammasining  qatorlarini  ustun,  ustunlarini  esa  qator  qilib 

o‘zgartirilsa (ya’ni diagramma trasponirlansa), tabiiyki, yana normal 

Ferrers diagrammasi hosil bo‘ladi. 

4-  t a ’ r i f .  Bu  hosil  bo‘lgan  diagrammaga  dastlabki 

diagrammaning transpozitsiyasi (yoki ikkilanma diagrammasi) deb ataladi. 

Normal  Ferrers  diagrammasining  transpozitsiyasi  natijasida  hosil  bo‘lgan 

ikkilanma  diagramma  transponirlansa  dastlabki  diagramma  hosil  bo‘lisi 

ravshandir.  Demak,  istalgan  son  uchun  tuzilgan  barcha  diagrammalarni  o‘zaro 

ikkilanma bo‘lgan diagrammalar juftlariga ajratish mumkin. Shuni e’tiborga olish 

kerakki,  ba’zi  diagrammalar  o‘z-o‘ziga  ikkilanma  bo‘ladi,  shuning  uchun  ular 

ikkita bir xil diagrammalar juftini tashkil etadi deb hisoblash mumkin. 

Ikkilanma  diagrammalarni  qo‘shma  diagrammalar  deb,  ularga  mos 

keluvchi  bo‘laklashlarni  esa  qo‘shma  bo‘laklashlar  deb  ham 

ataydilar. 

1- shakl 

 

158 

5- m i s o l . 4- misolda qaralgan 14=5+3+2+2+1+1 bo‘laklashga mos Ferrers 

diagrammasiga  qo‘shma  diagrammani  2-  shakldagidek  tasvirlash  mumkin.  Mos 

qo‘shma bo‘laklash esa: 14=6+4+2+1+1. ■ 

2.6.3.  Bo‘laklashlarning  xossalari.  Quyidagi  uchta  3–5-  teoremalar 

bo‘laklashlarning ba’zi xossalarini ifodalaydi. 

3- t e o r e m a . Ixtiyoriy 

n

 natural sonning har xil natural qo‘shiluvchilarga 

bo‘laklanishlari  soni  shu  sonning  toq  qo‘shiluvchlarga  bo‘laklanishlari  soniga 

teng. 

I s b o t i . 

n

 

natural 

sonning 

p

b

b

b

,...,

,

2

1

 

toq 

qo‘shiluvchilarga 

bo‘laklanishlaridan ixtiyoriy birini qaraymiz: 



 



 





 



 





 



 



p

r

p

p

p

r

r

b

b

b

b

b

b

b

b

b

n



























...

...

...

...

2

1

2

2

2

1

1

1

, 

bu  yerda  har  bir 

i

b

  (

p

i

,

1



)  qo‘shiluvchi  bo‘laklanishda 

i

r

  (

n

r

i





1

)  marta 

qatnashadi. 

i

r

  sonning  ikkilik  sanoq  sistemasidagi 

is

i

i

q

q

q

i

r

2

...

2

2

2

1









 

tasvirlanishini yozamiz, bunda 

0

...

2

1









is

i

i

q

q

q

 qandaydir (

s

ta) butun sonlar. 

Qaralayotgan 

n

 sonning yuqoridagi bo‘laklanishida 

i

r

ta 

i

b

 qo‘shiluvchilarni 

bir-biridan  farqli 

is

i

i

q

i

q

i

q

i

b

b

b

2

,...,

2

,

2

2

1

  qo‘shiluvchilarga  almashtiramiz.  Tabiiyki, 

bunday 

almashtirish 

i

r

ta 

i

b

 

qo‘shiluvchilar  yig‘indisining  qiymatini 

o‘zgartirmaydi.  Shu  jarayonni  barcha 

p

i

,...,

2

,

1



  qiymatlar  uchun  takrorlab  va 

qo‘shiluvchilarning  mos  qiymatlarini  yozib, 

n

  sonning  har  xil  qo‘shiluvchilarga 

bo‘laklanishlaridan  birini  hosil  qilamiz,  chunki 

i

b

, 

j

b

  sonlarning  toqligi  tufayli 

j

l

q

j

q

i

b

b

2

2



 bo‘ladi. 

Shunday  qilib, 

n

  sonning  toq  qo‘shiluvchilarga  bo‘laklanishlaridan  har 

biriga  shu  sonning  har  xil  qo‘shiluvchilarga  bo‘laklanishlaridan  biri  mos  kelishi 

isbotlandi. Bu tasdiqning teskarisini ham isbotlash mumkin. ■ 

6-  m i s o l .  3-  misolda  8ning  barcha  bo‘laklashlari  keltirilgan  va  bu 

bo‘laklashlar soni 22ga tengligi ko‘rsatilgan edi. 22ta bo‘laklashlardan oltitasi har 

xil  qo‘shiluvchilardan  tuzilgan.  Xuddi  shuncha  toq  qo‘shiluvchili  bo‘laklashlar 

mavjud.  3-  teoremaning  isbotidagidek  mulohaza  yuritib  8ning  har  xil 

 

159 

qo‘shiluvchili  va  toq  qo‘shiluvchili  barcha  bo‘laklanishlari  orasidagi  bir  qiymatli 

moslikni ko‘rsatish mumkin. 

Haqiqatdan ham, 

1

7

2

1

2

7

1

1

1

7

1

7

8

0

0

























, 

3

5

2

3

2

5

1

3

1

5

3

5

8

0

0

























, 

,

1

2

5

2

1

2

1

2

5

)

2

2

(

1

2

5

3

1

1

5

1

1

1

5

8

0

1

0

0

1

0















































 

2

6

2

1

2

3

2

1

2

3

1

1

3

3

8

1

1





























, 

,

1

4

3

2

1

2

1

2

3

)

2

2

(

1

2

3

5

1

1

3

1

1

1

1

1

3

8

0

2

0

0

2

0



















































 

8

2

1

8

1

1

1

1

1

1

1

1

1

8

3



























. ■ 

Diagrammali  usul  yordamida  bo‘laklashlarning  turli  xossalarini  osonlik 

bilan  isbotlash  mumkin.  Quyida  shunday  xossalardan  ikkitasini  ifodalovchi  4-  va 

5- teoremalarni keltiramiz.