Mavzu: Algebraning ta’rifi va misollar, morfizmlar, factor-algebra. Reja

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 o‘yg‘otishini ta’kidlaymiz. Hosil qiluvchi funksiyalarning kombinatorikaga tatbiqini ko‘rsatish maqsadida, avvalo, quiydagi misolni qaraymiz.

5-misol. Berilgan chekli, butun va manfiymas s son uchun hadlari

an

C ^n ,

0 n s,

formula

asosida aniqlangan a0 , a1 , a2 ,..., an ,...

sonlar

ketma-



s

s n,

0,

ketligi

berilgan bo‘lsin, bu yerda Cn



s!

–

binomial

koeffitsientlar. Bu

s

n!(s n)!

sonlar ketma-ketligining hosil qiluvchi funksiyasini topish talab etilsin.

Nyuton binomi formulasiga ko‘ra



s

an x^n

Cs^n x^n (1 x)^s

n0

n0

munosabat

o‘rinli bo‘ladi.

Demak,

berilgan

butun

s 0

son

uchun

C^0

, C^1, C^2 ,..., C^s ,0,0,...,0,...

ko‘rinishdagi

sonlar ketma-ketligining

hosil

qiluvchi

s

s

s

s

funksiyasi

f (x) (1 x)^s

ko‘rinishga egadir.

Yuqorida, aniqrog‘i, ushbu bobning 3- paragrafida binomial koeffitsientlarning xossalari ko‘rilgan edi. Quyidagi teorema ularning xossalaridan yana birini ifodalaydi.

1-teorema. Ixtiyoriy natural m , n va k m n sonlar uchun quyidagi tenglik o‘rinlidir:

min(k ,n)

Cⁱ C ^k^i C ^k .
_{n m nm}

Fibonachchi qatoridagi birinchi haddan oldin u₀ 0 sonni qo‘yib,

u₀ 0, u₁1, u_n u_n2 u_n1, n 2 ,

ketma-ketlikning (umumlashgan Fibonachchi sonlari ketma-ketligining) u(x) hosil qiluvchi funksiyani topamiz.

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

			
u(x)uk x^k x		uk x^k x(uk2 uk1)x^k
k0		k2	k2
				
 xuk2 x^kuk1x^k x x^2us x^s xup x ^p
k2	k2		s0	p0

• 
  x x²u(x) xu(x) .
  

Endi hosil bo‘lgan u(x) x x²u(x) xu(x) tenglikni u(x) funksiyaga nisbatan tenglama deb qarab,

u₀ 0, u₁1, u_n u_n2 u_n1, n 2 ,
ketma-ketlikning u(x)^{ x} hosil qiluvchi funksiyaga ega bo‘lamiz.

1 x x²

2-teorema.

Fibonachchi

soni

^un

( n 0,1,2,... )

uchun







n







n

1

1

5

1

5













tenglik o‘rinlidir.

un







^



5



2





2









Endi qo‘shiluvchilar tartibi e’tiborga olinmagan holda natural n sonning natural qo‘shiluvchilarga bo‘laklanishlari sonlaridan tashkil topgan

R(0), R(1), R(2), R(3),..., R(n),...

ketma-ketlikning hosil qiluvchi funksiyasi hisoblangan


r(x)R(n)xⁿ1 x 2x² 3x³ 5x⁴ 7x⁵12x⁶...
n0

darajali qatorni qaraymiz.

12. 
    Eyler (1 x)(1 x² )(1 x³ )...(1 xⁿ ) ko‘rinishdagi ko‘paytmalarni natural n uchun tekshirib,
    

			 3m^2m			3m^2m
(x)(1 x	n	)1(1)	^m^		 x		
				2		2
			 ^x				
n1		m1					

formulani isbotlagan edi. Bu formula Eyler ayniyati deb ataladi.

3-teorema.(x)r(x)1.