Ii bob kombinatorika elementlari

2.4.3.  Takrorli  gruppalashlar.  Har  bir  elementi  birlashmaga  istalgancha 

marta kiritiladigan va turli 

n

ta elementlardan 

m

tadan olinadigan hamda elementlar 

tartibi e’tiborga olinmaydigan birlashmalarni (kortejlarni) qaraymiz. 

3-  t a ’ r i f .  Bunaqa  birlashmalar 

n

ta  turli  elementlardan 

m

tadan 

takrorlanuvchi  elementlar  qatnashgan  gruppalashlar  (qisqacha,  takrorli 

gruppalashlar) deb ataladi. 

n

ta 

elementlardan 

m

tadan 

takrorlanuvchi 

elementlar 

qatnashgan 

gruppalashlar ta’rifidan ko‘rinib turibdiki, turli kombinatsiyalar bir-birlaridan hech 

bo‘lmasa  bitta  elementi  bilan  farq  qiladi. 

n

ta  elementdan 

m

tadan  takrorli 

gruppalashlar sonini 

m

n

C

 deb belgilaymiz. 

3- t e o r e m a . 

n

ta elementdan 

m

tadan takrorli gruppalashlar soni 

m

m

n

C

1





ga 

teng, ya’ni 

m

m

n

m

n

C

C

1







. 

I s b o t i . 

}

,...,

,

{

2

1

n

a

a

a

  to‘plam  uchun 

n

ta  elementdan 

m

tadan  takrorli 

gruppalashlar  sonini  aniqlash  zarur.  Har  bir  takrorli  gruppalashdagi  elementlarni 

 

132 

n

ta  qismga  shunday  bo‘lish  mumkinki,  har  bir 

i

-  bo‘lakda 

i

a

  element  qanchadir 

marta  qatnashadi  yoki  biror  marta  ham  qatnashmaydi.  Har  bir  shunday 

gruppalashni  nol  va  birlardan  iborat  kod  yordamida  quyidagicha  shifrlaymiz:  har 

bir 

i

a

  element  o‘rniga  bu  element 

i

-  bo‘lakda  necha  marta  qatnashsa,  shuncha 

birlar  yozamiz  (tabiiyki,  bu  element  biror  marta  ham  qatnashmasligi  mumkin,  u 

holda  hech  narsa  yozilmaydi);  turli  bo‘lak  elementlarini  bir-biridan  nollar  bilan 

ajratamiz (bu yerda yonma-yon joylashgan nollar hosil bo‘lishi mumkin – bu nollar 

mos  elementlarning  gruppalashda  qatnashmaganligini  anglatadi).  Masalan, 

}

,

,

,

,

,

{

f

e

d

c

b

a

  to‘plam  elementlaridan  tuzilgan  6ta  elementdan  9tadan  takrorli 

bbbcddddf

  gruppalashga 

1001

0111010111

  shifr,  6ta  elementdan  12tadan  takrorli 

ff

aaaabeeeee

  gruppalashga  esa 

111011

1111010011

  shifr,  aksincha, 

0

1010001111

 

shifrga 6ta elementdan 6tadan takrorli 

abeeee

 gruppalash mos keladi. 

Shunday  qilib, 

n

ta  elementdan 

m

tadan  har  bir  takrorli  gruppalash  uchun 

qandaydir 

m

ta birlar va (

1



n

)ta nollardan iborat ketma-ketlikni va, aksincha, 

m

ta 

birlar  va  (

1



n

)ta  nollardan  tashkil  topgan  har  bir  ketma-ketlik  uchun 

n

ta 

elementdan 

m

tadan biror takrorli gruppalashni mos qo‘ygan bo‘lamiz (bir qiymatli 

moslik o‘rnatildi).  Binobarin, 

n

ta  elementdan 

m

tadan  takrorli  gruppalashlar  soni 

(

1



n

)ta nol va 

m

ta birlardan tashkil topgan kortej elementlaridan tuzilgan takrorli 

o‘rin almashtirishlar soniga, ya’ni 

)

1

,

(

1







n

m

C

m

n

ga tengdir. Demak, 

m

m

n

m

n

m

n

C

n

m

m

n

n

m

C

C

1

1

)!

1

(

!

)!

1

(

)

1

,

(























. ■ 

4-  m i s o l .  Har  birining  yoqlariga  1,  2,  3,  4,  5  va  6  sonlari  yozilgan  kub 

shaklidagi  ikkita  soqqalarni  tashlaganda  jami  nechta  sonlar  juftligini  hosil  qilish 

mumkin? 

Soqqalarni tashlaganda jami quyidagi 21 imkoniyatlardan biri ro‘y beradi: 

,

2

,

2

,

6

,

1

,

5

,

1

,

4

,

1

,

3

,

1

,

2

,

1

,

1

,

1





























 

,

5

,

3

,

4

,

3

,

3

,

3

,

6

,

2

,

5

,

2

,

4

,

2

,

3

,

2





























 





























6

,

6

,

6

,

5

,

5

,

5

,

6

,

4

,

5

,

4

,

4

,

4

,

6

,

3

. 

 

Bu juftliklar oltita elementdan ikkitadan takrorli gruppalashlarni tashkil 

etadi. 

 

133 

Ularning soni 3- teoremaga asosan 

21

2

7

2

1

2

6

2

6











C

C

C

 bo‘ladi. ■ 

2.4.4.  Ko‘phad  formulasi.  Takrorli  kombinatsiyalar  vositasida  Nyuton 

binomi  tushunchasini  umumlashtiramiz,  ya’ni 

n

m

a

a

a

)

...

(

2

1







  ifodaning 

yoyilmasini topish muammosini qaraymiz. Buning uchun qaralayotgan ifodani 

n

ta 

bir xil ifodalar ko‘paytmasi, ya’ni 















































paytuvchi

ko'

 

ta

2

1

2

1

2

1

)

...

)...(

...

)(

...

(

n

m

m

m

a

a

a

a

a

a

a

a

a



















 

shaklida  yozib,  qavslarni  ochamiz  va  o‘xshash  hadlarni  ixchamlaymiz.  Natijada, 

n

m

a

a

a

)

...

(

2

1







  ifodaning  yoyilmasi  hosil  bo‘ladi.  Yoyilmaning  tarkibidagi 

qo‘shiluvchilarning  har  birida 

m

a

a

a

,...,

,

2

1

  elementlardan  tashkil  topgan  takrorli 

o‘rin  almashtirishlar  bor,  bu  yerda  har  bir  qo‘shiluvchi  qandaydir  koeffitsient  va 

n

ta 

elementlarning 

m

n

m

n

n

a

a

a

...

2

1

2

1

 

ko‘rinishdagi  ko‘paytmasidan  iboratdir. 

Yoyilmadagi 

m

n

m

n

n

a

a

a

...

2

1

2

1

  ko‘paytmaning  koeffitsientini  aniqlash  uchun 

n

ta 

(

m

n

n

n

n









...

2

1

) elementli takrorli o‘rin almashtirishlar sonini topish kerak, ya’ni 

)

,...,

,

(

2

1

m

n

n

n

n

C

 sonni hisoblash kerak. Shunday qilib, quyidagi teorema isbotlandi. 

4- t e o r e m a . Ixtiyoriy haqiqiy 

m

a

a

a

,...,

,

2

1

 va natural 

n

 sonlar uchun 



















n

n

n

n

n

m

n

n

m

n

n

m

m

m

a

a

a

n

n

n

C

a

a

a

...

2

1

2

1

2

1

2

1

2

1

...

)

,...,

,

(

)

...

(

 

formula  o‘rinlidir,  bu  formulaning  o‘ng  tomonidagi  yig‘indi 

n

n

n

n

m









...

2

1

 

shartni  qanoatlantiruvchi  barcha  manfiymas  butun 

m

n

n

n

,...,

,

2

1

  sonlar  uchun 

amalga oshiriladi. 

Isbotlangan oxirgi tenglik  ko‘phad formulasi yoki umumlashgan Nyuton 

binomi 

formulasi 

deb 

yuritiladi. 

)

,...,

,

(

2

1

m

n

n

n

n

C

 

sonlarni 

ko‘phadiy 

koeffitsientlar deb ataymiz. 

k

n

C

  binomial  koeffitsient 

)

,...,

,

(

2

1

m

n

n

n

n

C

  ko‘phadiy  koeffitsientning 

2



m

 

bo‘lgandagi xususiy holidir. Haqiqatdan ham, 

n

n

n





2

1

 tenglikda 

k

n



1

 deb olsak, 

u holda 

k

n

n

n

n









1

2

 va 

k

n

n

C

k

n

k

n

n

n

n

n

n

C









)!

(

!

!

!

!

!

)

,

(

2

1

2

1

 bo‘ladi. 

 

134 

5-  m i s o l . 

3

)

(

c

b

a





  ifodaning  yoyilmasini  toping.  Avvalo  3  sonini 

bo‘laklaymiz,  ya’ni  3ni  mumkin  bo‘lgan  barcha  imkoniyatlar  bilan  manfiymas 

butun sonlar yig‘indisi shaklida yozamiz: 

3=3+0+0, 3=2+1+0, 3=2+0+1, 3=1+2+0, 3=1+1+1, 

3=1+2+0, 3=0+3+0, 3=0+2+1, 3=0+1+2, 3=0+0+3. 

Demak, ko‘phad formulasiga ko‘ra, 













c

a

C

b

a

C

a

C

c

b

a

2

3

2

3

3

3

3

)

1

,

0

,

2

(

)

0

,

1

,

2

(

)

0

,

0

,

3

(

)

(

 











3

3

2

3

3

2

3

)

0

,

3

,

0

(

)

2

,

0

,

1

(

)

1

,

1

,

1

(

)

0

,

2

,

1

(

b

C

ac

C

abc

C

ab

C

 

3

3

2

3

2

3

)

3

,

0

,

0

(

)

2

,

1

,

0

(

)

1

,

2

,

0

(

c

C

bc

C

c

b

C







. 

Takrorli  o‘rin  almashtirishlar  soni 

!

!...

!

!

)

,...,

,

(

2

1

2

1

k

k

n

n

n

n

n

n

n

n

C



  formulasini  qo‘llab 

quyidag tenglikni hosil qilamiz: 







3

)

(

c

b

a

 

3

2

2

3

2

2

2

2

3

3

3

3

6

3

3

3

c

bc

c

b

b

ac

abc

ab

c

a

b

a

a





















. ■ 

Ko‘phad  yoyilmasining  hadlarini  yozganda  shunga  e’tibor  berish  kerakki, 

agar 

m

n

n

n

,...,

,

2

1

 (

n

n

n

n

m









...

2

1

) sonlar 

m

k

k

k

,...,

,

2

1

 (

n

k

k

k

m









...

2

1

) sonlarning 

o‘rin almashtirishlari yordamida hosil qilinishi mumkin bo‘lsa, u holda 

m

n

m

n

n

a

a

a

...

2

1

2

1

 

va 

m

k

m

k

k

a

a

a

...

2

1

2

1

  hadlarning  koefitsientlari  o‘zaro  teng  bo‘ladi.  Shuning  uchun 

n

 

sonining 

m

n

n

n

n









...

2

1

  ko‘rinishda  ifodalanishlaridan  qandaydir  shartni 

bajaradigan  birortasini,  masalan, 

m

n

n

n







...

2

1

  (yoki 

m

n

n

n







...

2

1

)  shartni 

qanoatlantiradiganini  topib,  unga  mos 

m

n

m

n

n

a

a

a

...

2

1

2

1

  ifodada  daraja  ko‘rsatgichlarini 

mumkin bo‘lgan barcha usullar bilan almashtirish kerak bo‘ladi. 

Masalan, 5- misoldagi 

b

a

2

, 

c

a

2

, 

2

ab

, 

2

ac

, 

c

b

2

 va 

2

bc

 hadlarning ko‘phadiy 

koeffitsientlari  o‘zaro  tengdir.  Yuqorida  ko‘rsatilgan  shart  asosida  3  sonini 

manfiymas  butun  sonlar  yigindisi  ko‘rinisida  bo‘laklashning  3  imkoniyati  bor: 

3=3+0+0, 3=2+1+0, 3=1+1+1. Shuning uchun, 

3

)

(

c

b

a





 ifodaning yoyilmasida 3 

xil turli koeffitsientlarga egamiz: 

1

)

0

,

0

,

3

(

3



C

, 

3

)

0

,

1

,

2

(

3



C

 va 

6

)

1

,

1

,

1

(

3



C

. Demak, 













3

3

3

3

)

(

c

b

a

c

b

a

 

abc

bc

c

b

ac

ab

c

a

b

a

6

)

(

3

2

2

2

2

2

2















. 

 

135 

Ko‘phad  formulasi  yordamida  ko‘phadiy  koeffitsientlarning,  ya’ni 

)

,...,

,

(

2

1

m

n

n

n

n

C

  sonlarning  ba’zi  xossalarini  osonlik  bilan  isbotlash  mumkin. 

Masalan, 

n

n

n

n

n

m

n

m

n

n

n

C

m













...

2

1

2

1

)

,...,

,

(

, 

bu  yerda  yig‘indi 

n

n

n

n

m









...

2

1

  shartni  qanoatlantiruvchi  barcha  manfiymas 

butun 

m

n

n

n

,...,

,

2

1

 sonlar uchun amalga oshiriladi va qo‘shiluvchilar tartibi e’tiborga 

olinadi. 

Haqiqatdan  ham,  agar  ko‘phad  formulasida 

1

...

2

1









m

a

a

a

  deb  olsak, 

kerakli tenglikni hosil qilamiz. 

 

Muammoli masala va topshiriqlar