Ii bob kombinatorika elementlari

2-  x o s s a .  Agar   

,...

,...,

,

,

2

1

0

n

a

a

a

a

  ketma-ketlikning  hosil  qiluvchi  funksiyasi 

)

(x

f

a

  va 

,...

,...,

,

,

2

1

0

n

b

b

b

b

  ketma-ketlikning  hosil  qiluvchi  funksiyasi 

)

(x

f

b

  bo‘lsa,  u 

 

166 

holda 

elementlari 









n

i

i

n

i

n

b

a

d

0

 

(

,...

2

,

1

,

0



n

) 

sonlardan  iborat  bo‘lgan 

,...

,...,

,

,

2

1

0

n

d

d

d

d

 ketma-ketlikning hosil qiluvchi funksiyasi 

)

(

)

(

)

(

x

f

x

f

x

f

b

a



 bo‘ladi. 

Haqiqatdan ham, ketma-ketlikning hosil qiluvchi funksiyasi ta’rifiga ko‘ra, 



















n

k

k

k

n

k

k

k

a

x

a

x

a

x

f

0

0

lim

)

(

, 

















n

k

k

k

n

k

k

k

b

x

b

x

b

x

f

0

0

lim

)

(

 

bo‘lgani uchun quyidagi tengliklar ketma-ketligi o‘rinlidir: 









































































n

k

k

k

n

k

k

k

n

n

k

k

k

n

n

k

k

k

n

b

a

x

b

x

a

x

b

x

a

x

f

x

f

0

0

0

0

lim

lim

lim

)

(

)

(

 

)

(

lim

lim

0

0

0

0

x

f

x

d

x

d

x

b

a

k

k

k

n

k

k

k

n

n

k

k

k

i

i

k

i

n

























 

















. ■ 

Ayrim  ketma-ketliklarning  hosil  qiluvchi  funksiyalarini  avvaldan  ma’lum 

bo‘lgan  hosil  qiluvchi  funksiyalarga  mos  darajali  qatorni  hadlab  differensiallash 

amali yordamida topish mumkin. 

3-  m i s o l .  Ushbu 

,...

3

,

2

,

1

,

0

  ketma-ketlikning  hosil  qiluvchi  funksiyasi 

2

)

1

(

)

(

x

x

x

f





 bo‘ladi. 

Haqiqatdan  ham,  qaralayotgan  ketma-ketlikka 







0

k

k

kx

  ko‘rinishdagi  darajali 

qator  mos  keladi.  Darajali  qatorni  hadlab  differensiallash  amalini 







0

k

k

x

  qatorga 

qo‘llab  va 

1



x

  bo‘lgan  hol  uchun  o‘rinli 

x

x

k

k











1

1

0

  tenglikni  hisobga  olib, 

quyidagi tengliklar ketma-ketligini yozamiz: 

 



























0

0

1

0

k

k

k

k

k

k

x

dx

d

x

kx

x

kx

 

2

0

)

1

(

1

1

x

x

x

dx

d

x

x

dx

d

x

k

k





























. ■ 

Umuman  olganda,  hosil  qiluvchi  funksiyalarni  tuzishda  darajali  qatorni 

hadlab differensiallash amalidan foydalanish quyidagi xossaga tayanadi. 

 

167 

3-  x o s s a .  Agar 

,...

,...,

,

,

2

1

0

n

a

a

a

a

  ketma-ketlikning  hosil  qiluvchi  funksiyasi 

)

(x

f

a

  bo‘lsa,  u  holda  elementlari 

1

)

1

(







n

n

a

n

b

  (

,...

2

,

1

,

0



n

)  sonlardan  iborat 

,...

,...,

,

,

2

1

0

n

b

b

b

b

 ketma-ketlikning hosil qiluvchi funksiyasi 

dx

x

df

x

f

a

b

)

(

)

(



 bo‘ladi. 

Haqiqatdan  ham,  hosil  qiluvchi  funksiyaning  ta’rifidan  va  darajali  qatorni 

hadlab differensiallash haqidagi xossaga ko‘ra 























0

1

0

)

1

(

)

(

k

k

k

k

k

k

b

x

a

k

x

b

x

f

 





 





















1

0

1

1

s

s

s

k

k

k

x

a

dx

d

x

a

dx

d

 

tengliklar o‘rinlidir. 

0

a

 o‘zgarmasning hosilasi nolga teng ekanligini e’tiborga olib 

 

 

dx

x

df

x

a

dx

d

x

a

dx

d

dx

da

x

a

dx

d

x

f

a

k

k

k

s

s

s

s

s

s

b

)

(

)

(

0

1

0

1





























 

munosabatni hosil qilamiz. ■ 

4- m i s o l . 

,...

4

,

3

,

2

,

1

 ketma-ketlikning hosil qiluvchi funksiyasini topish talab 

etilsin. 

Hosil  qiluvchi  funksiya  ta’rifiga  ko‘ra  izlanayotgan  funksiya 









0

)

1

(

k

k

x

k

 

darajali  qatorning  yig‘indisidan  iboratdir.  1-  xossaga  ko‘ra  qaralayotgan  ketma-

ketlikning  hosil  qiluvchi  funksiyasi 

,...

1

,...,

1

,

1

  va 

,...

3

,

2

,

1

,

0

  ketma-ketliklarning  hosil 

qiluvchi  funksiyalari  yig‘indisidan  iboratdir.  1-  va  3-  misollar  natijalaridan 

foydalanib, quyidagilarga ega bo‘lamiz: 



























0

0

0

)

1

(

k

k

k

k

k

k

kx

x

x

k

2

2

2

)

1

(

1

)

1

(

1

)

1

(

1

1

x

x

x

x

x

x

x





















. 

Demak, 

,...

4

,

3

,

2

,

1

 ketma-ketlikning hosil qiluvchi funksiyalasi

2

)

1

(

1

)

(

x

x

f





 bo‘ladi. 

2.7.3.  Hosil  qiluvchi  funksiyalarning  kombinatorikaga  tatbiqi.  Hosil 

qiluvchi  funksiyaning  ta’rifi  va  xossalaridan  ko‘rinadiki,  ketma-ketliklar  bilan 

bog‘liq  bo‘lgan  xilma-xil  masalalarni  o‘rganish  va  ularni  hal  qilishda  bu 

funksiyalardan  foydalanish  mumkin.  Bu  o‘rinda,  ayniqsa,  kombinatorik  amallar 

bilan  bog‘liq  ketma-ketliklarning  hosil  qiluvchi  funksiyalari  alohida  qiziqish 

 

168 

o‘yg‘otishini  ta’kidlaymiz.  Hosil  qiluvchi  funksiyalarning  kombinatorikaga 

tatbiqini ko‘rsatish maqsadida, avvalo, quiydagi misolni qaraymiz. 

5-  m i s o l .  Berilgan  chekli,  butun  va  manfiymas 

s

  son  uchun  hadlari 















,

        

,

0

,

0

      

,

n

s

s

n

C

a

n

s

n

  formula  asosida  aniqlangan 

,...

,...,

,

,

2

1

0

n

a

a

a

a

  sonlar  ketma-

ketligi berilgan bo‘lsin, bu yerda 

)!

(

!

!

n

s

n

s

C

n

s





 – binomial koeffitsientlar. Bu sonlar 

ketma-ketligining hosil qiluvchi funksiyasini topish talab etilsin. 

Nyuton binomi formulasiga ko‘ra 

s

s

n

n

n

s

n

n

n

x

x

C

x

a

)

1

(

0

0

















 

munosabat o‘rinli bo‘ladi. 

Demak, berilgan butun 

0



s

 son uchun 

,...

0

,...,

0

,

0

,

,...,

,

,

2

1

0

s

s

s

s

s

C

C

C

C

 ko‘rinishdagi 

sonlar ketma-ketligining hosil qiluvchi funksiyasi 

s

x

x

f

)

1

(

)

(





 ko‘rinishga egadir. 

■ 

Yuqorida, 

aniqrog‘i, 

ushbu 

bobning 

3- 

paragrafida 

binomial 

koeffitsientlarning xossalari ko‘rilgan edi. Quyidagi teorema ularning xossalaridan 

yana birini ifodalaydi. 

1-  t e o r e m a .  Ixtiyoriy  natural 

m

, 

n

  va 

n

m

k





  sonlar  uchun  quyidagi 

tenglik o‘rinlidir: 

k

m

n

n

k

m

k

i

i

k

m

i

n

C

C

C













)

,

min(

)

,

0

max(

. 

I s b o t i .  Elementlari  mos  ravishda  quyidagi  tengliklar  bilan  aniqlangan 

,...

,

,

2

1

0

a

a

a

 va 

,...

,

,

2

1

0

b

b

b

 ketma-ketliklarni qaraymiz: 















,

        

,

0

,

0

      

,

n

i

n

i

C

a

i

n

i

 















.

        

,

0

,

0

      

,

m

i

m

i

C

b

i

m

i

 

5- misolni hisobga olsak, bu ketma-ketliklarning hosil qiluvchi funksiyalari 

mos  ravishda 

n

a

x

x

f

)

1

(

)

(





  va 

m

b

x

x

f

)

1

(

)

(





  ko‘rinishda  bo‘ladi.  Hosil  qiluvchi 

funksiyalarning  2-  xossasiga  ko‘ra 









0

)

(

)

(

s

s

s

b

a

x

d

x

f

x

f

  bo‘ladi,  bunda 









s

i

i

s

i

s

b

a

d

0

 

(

,...

2

,

1

,

0



s

).  Ushbu 

n

m

k





  shartni  qanoatlantiruvchi  ixtiyoriy 

k

  natural  sonni 

 

169 

olamiz.  Qaralayotgan 

,...

,

,

2

1

0

a

a

a

  va 

,...

,

,

2

1

0

b

b

b

  ketma-ketliklarning  aniqlanishiga 

ko‘ra 

n

i



  shart  bajarilganda 

0



i

a

  va 

m

i

k





  shart  bajarilganda  esa 

0





i

k

b

 

bo‘lgani uchun 





























)

,

min(

)

,

0

max(

)

,

min(

)

,

0

max(

0

n

k

m

k

i

i

k

m

i

n

n

k

m

k

i

i

k

i

k

i

i

k

i

k

C

C

b

a

b

a

d

 

munosabat o‘rinlidir. 

Boshqa tomondan olib qaraganda, 























m

n

i

i

i

m

n

m

n

m

n

b

a

x

C

x

x

x

x

f

x

f

0

)

1

(

)

1

(

)

1

(

)

(

)

(

. 

Agar 





















,

        

,

0

,

0

      

,

m

n

i

m

n

i

C

i

m

n

i



  deb  olsak,  u  holda  yuqorida  hosil  qilingan 











m

n

i

i

i

m

n

b

a

x

C

x

f

x

f

0

)

(

)

(

  tenglikni 









0

)

(

)

(

i

i

i

b

a

x

x

f

x

f



  ko‘rinishda  yozish  mumkin.  Bu, 

o‘z  navbatida, 

)

(

)

(

x

f

x

f

b

a

  funksiya 

,...

,

,

2

1

0







  ketma-ketlikning  hosil  qiluvchi 

funksiyasi ekanligini ko‘rsatadi. 

Hosil qiluvchi funksiyalarning 2- xossasiga ko‘ra 

)

(

)

(

x

f

x

f

b

a

 funksiya hadlari 

m

n

k





  bo‘lganda 











)

,

min(

)

,

0

max(

n

k

m

k

i

i

k

m

i

n

k

C

C

d

  tenglik  bilan, 

m

n

k





  bo‘lganda  esa 

nollardan  iborat  ketma-ketlikning  hosil  qiluvchi  funksiyasi  ekanligi  yuqorida 

ko‘rsatilgan edi. 

Shunday qilib, 

 





















m

n

k

k

n

k

m

k

s

s

k

m

s

n

m

n

k

k

k

m

n

x

C

C

x

C

0

)

,

min(

)

,

0

max(

0

. 

Bu  tenglik 

x

  o‘zgaruvchining  barcha  qiymatlarida  to‘g‘ri  bo‘lganligidan, 

isbotlanishi kerak bo‘lgan tenglikni hosil qilamiz. ■ 

Fibonachchi qatoridagi birinchi haddan oldin 

0

0



u

 sonni qo‘yib

40

, 

2

,

,

1

,

0

1

2

1

0















n

u

u

u

u

u

n

n

n

, 

ketma-ketlikning (umumlashgan Fibonachchi sonlari ketma-ketligining) 

)

(x

u

 hosil 

qiluvchi funksiyani topamiz. 

                                                           

40

  Fibonachchi  qatorini  chap  tomonga  ham  istalgancha  davom  ettirish  mumkin.  Tabiiyki,  bunday  ish  ko‘rilganda, 

har qadamda hosil bo‘lgan ketma-ketlik qandaydir bir umumlashgan Fibonachchi qatori bo‘laveradi. 

 

170 

Buning uchun, dastlab, quyidagi tengliklar ketma-ketligini yozamiz: 





































2

1

2

2

0

)

(

)

(

k

k

k

k

k

k

k

k

k

k

x

u

u

x

x

u

x

x

u

x

u

 











































0

0

2

2

1

2

2

p

p

p

s

s

s

k

k

k

k

k

k

x

u

x

x

u

x

x

x

u

x

u

x

 

)

(

)

(

2

x

xu

x

u

x

x







. 

Endi  hosil  bo‘lgan 

)

(

)

(

)

(

2

x

xu

x

u

x

x

x

u







  tenglikni 

)

(x

u

  funksiyaga  nisbatan 

tenglama deb qarab, 

2

,

,

1

,

0

1

2

1

0















n

u

u

u

u

u

n

n

n

, 

ketma-ketlikning 

2

1

)

(

x

x

x

x

u







 hosil qiluvchi funksiyaga ega bo‘lamiz. 

II  bobning  5-  paragrafida  isbotlangan  (Fibonachchi  sonlarini  hisoblashga 

mo‘ljallangan)  Bine  formulasini 

,...

2

,

1

,

0



n

  hol  uchun  umumlashgan  Fibonachchi 

sonlari  ketma-ketligining  hosil  qiluvchi  funksiyasidan  foydalanib  yana  bir  marta 

isbotlaymiz.