Войти Регистрация

Docx

  • Рефераты
  • Дипломные работы
  • Прочее
    • Презентации
    • Рефераты
    • Курсовые работы
    • Дипломные работы
    • Диссертациии
    • Образовательные программы
    • Инфографика
    • Книги
    • Тесты

Информация о документе

Цена 20000UZS
Размер 625.3KB
Покупки 0
Дата загрузки 09 Январь 2026
Расширение docx
Раздел Курсовые работы
Предмет Алгебра

Продавец

Navruz

Дата регистрации 03 Декабрь 2023

20 Продаж

Kombinatorika Asoslari

Купить
O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA
MAXSUS TA’LIM VAZIRLIGI ANDIJON DAVLAT
UNIVERSITETI FIZIKA VA MATEMATIKA
FAKULTETI
MATEMATIKA Kafedrasi
KOMBINATORIKA ASOSLARI Fanidan
KURS ISHI
MAVZU:  Bo’laklashlar kombinatorikasi
Bajardi: _______________
Andijon Kirish
  Mavzuning   dolzarbligi,   Ehtimollar   nazariyasi   va   matematik   statistika   –
bir-birga   uzviy   bog’liq   matematik   fanlar   hisoblanadi.   Hozirgi   paytda   bu   sohalar
bo’yicha   olingan   bilimlar   turli   kasb   mutaxassislariga   juda   ham   ham   zurur.   O’z
faoliyatini   maqsadini   aniqlay   olish   va   unga   erishish   uchun   shaxdam   qadamlar
qo’yish   –   kompetentli,   raqobatbardosh   qobiliyatli   mutaxassisning   xarakterli
xususiyati,   ehtimollar   nazariyasi   va   matematik   statistika   esa   har   qanday   fanga
qaraganda ko’proq shaxsning ijobiy o’zgarishlari uchun yordam beradi. Ommaviy
tasodifiy   jarayonlar   qonuniyatlarini   (ehtimollar   nazariyasi   fani)   va   kuzatishlar
natijalarini   qayta   ishlash   muhim   usul   va   yo’llarini   (matematik   statistika
o’rganadigan)   bilish   har   bir   kasbdagi   mutaxassis   uchun   amaliy   masalalarni
yechishda qo’l keladi.
      Ehtimollar   nazariyasi   va   matematik   statistikani   o’rganishni   esa   avvalo
kombinatorika asoslari bilan tanishmasdan mumkin bo’lmaydi. «Kombinatorika»
atamasi matematikaga Leybnits tomonidan kiritilgan bo’lib, uni 1666 yilda chop
etilgan   «Kombinatorika   san’ati   to’g’risida   mulohazalar»   nomli   kitobida   birinchi
marta   qo’llagan   edi.   Kombinatorik   masalalar   nafaqat   matematika   go’zalligini
ko’rsatishga,   balki   amaliy   matematik   masalarni   yechishda   yangi   kompyuter
texnoogiyalarining   imkoniyatlarini   ko’rsatishga   imkon   beradi.   Diskret
matematikaning   masalalaridan   hisoblangan   kombinatorik   masalalar   ko’pincha
ob’ektlarning turli kombinatorik konfiguratsiyalarini tanlashga va ular orasidan u
yoki bu masala shartigav nuqtai nazaridan eng yaxshisini tanlashga olib kelinadi.
Shuning   uchun   keng   tarqalgan   kombinatorik   konfiguratsiyalarni   hosil   qilish
algoritmlarini   bilish   masalani   butunlay   muvaffaqiyatli   yechishning   zarur   sharti
hisoblanadi.   Ushbu   kurs   ishida   matematika   o’qitishda   kombinatorika
elementlarini   o’rganish   samaradorligini   oshirish   maqsadida   kombinatorika
fanining asosiy 5 tushunchalari, kombinatorikani o’rganish xususiyatlari, o’qitish
jarayonida   kombinatorika   elementlarini   o’rgatish   bilan   birga   o’quvchilarning
ijodiy faolligini oshirish bo’yicha uslubiy tavsiyalar bayon etilgan. Reja:
1. Kombinatorika haqida umumiy tushuncha.
2. Bo’laklash kombinatorikasi.
3. Ferrers diagrammasi.
4. Bo’lakashlarning xossalari. Kombinatorika asoslari→
Kombinatorik masalalar va tartiblangan to’plamlar.
        Kombinatorika   predmeti   va   paydo   bo’lish   tarixi.   Matematikaning
kombinatorik tahlil, kombinatorik matematika, birlashmalar nazariyasi, qisqacha,
kombinatorika   deb   ataluvchi   bo’limida   chekli   yoki   muayyan   ma’noda   cheklilik
shartini   qanoatlantiruvchi   to’plamni   (bu   to’plamning   elementlari   qanday
bo’lishining   ahamiyati   yo’q:   harflar,   sonlar,   hodisalar,   qandaydir   predmetlar   va
boshqalar)   qismlarga   ajratish,   ularni   o’rinlash   va   o’zaro   joylash   ya’ni,
kombinatsiyalar,   kombinatorik   tuzilmalar   bilan   bog’liq   masalalar   o’rganiladi.
Hozirgi   davrda   kombinatorikaga   oid   ma’lumotlar   inson   faoliyatining   turli
sohalarida   qo’llanilmoqda.   Jumladan,   matematika,   kimyo,   fizika,   biologiya,
lingvistika,   axborot   texnologiyalari   va   boshqa   sohalar   bilan   ish   ko’ruvchi
mutaxassislar   kombinatorikaning   xilma-xil   masalalariga   duch   keladilar.
To’plamlar   nazariyasi   iboralari   bilan   aytganda,   kombinatorikada   kortejlar   va
to’plamlar,   ularning   birlashmalari   va   kesishmalari   hamda   kortejlar   va   qism
to’plamlarni turli usullar bilan tartiblash masalalari qaraladi. To’plam yoki kortej
elementlarining   berilgan   xossaga   ega   konfiguratsiyasi   bor   yoki   yo’qligini
tekshirish, bor bo’lsa, ularni tuzish va sonini topish usullarini o’rganish hamda 7
bu   usullarni   biror   parametr   bo’yicha   takomillashtirish   kombinatorikaning   asosiy
masalalari hisoblanadi. Kombinatorikaning ba’zi elementlari eramizdan oldingi II
asrda   hindistonliklarga   ma’lum   edi.   Ular   hozirgi   vaqtda   gruppalashlar   deb
ataluvchi   kombinatorik   tushunchadan   foydalanishgan.   Eramizning   XII   asrida
Bxaskara   Acharya   o’zining   ilmiy   tadqiqotlarida   gruppalash   va   o’rin
almashtirishlarni   qo’llagan.   Tarixiy   ma’lumotlarga   ko’ra,   hindistonlik   olimlar
kombinatorika   elementlaridan,   jumladan,   birlashmalardan   foydalanib,   she’riy
asarlar tarkibiy tuzilishining mukammalligini tahlil qilishga uringanlar. Umuman
olganda,   kombinatorikaning   dastlabki   rivoji   qimor   o’yinlarini   tahlil   qilish   bilan
bog’liq. Ba’zi atoqli matematiklar, masalan, fransuz matematigi B.Paskal (1623-
1662), sveytasriyalik matematik Ya.Bernulli (1654- 1705), L.Eyler (1707-1783),
rus matematigi P.L.Chebishev (1821-1894) turli o’yinlarda (tanga tashlash, soqqa tashlash, qarta o’yinlari va shu kabilarda) ilmiy jihatdan asoslangan qarorlar qabul
qilishda kombinatorikani qo’llashgan. XVII asrda kombinatorika matematikaning
alohida bir ilmiy yo’nalishi sifatida shakllana boshladi.
      Blez   Paskal   o’zining   “Arifmetik   uchburchak   haqida   traktat”   va   “Sonli
tartiblar   haqida   traktat”   (1665   y.)   nomli   asarlarida   hozirgi   vaqtda   binomial
koeffitsientlar   deb   ataluvchi   sonlar   haqidagi   ma’lumotlarni   keltirgan.   Fransuz
matematigi P.Ferma (1601-1665) esa figurali sonlar bilan birlashmalar nazariyasi
orasida bog’lanish borligini bilgan.
     Figurali sonlar quyidagicha aniqlanadi. Birinchi tartibli figurali sonlar: 1,
2, 3, 4, 5, … (ya’ni, natural sonlar); ikkinchi tartibli figurali sonlar: 1-si 1ga teng,
2-si   dastlabki   ikkita   natural   sonlar   yig’indisi   (3),   3-si   dastlabki   uchta   natural
sonlar   yig’indisi   (6)   va   hokazo   (1,   3,   6,   10,   15,   …);   uchinchi   tartibli   figurali
sonlar:   1-si   1ga   teng,   2-si   birinchi   ikkita   ikkinchi   tartibli   figurali   sonlarlar
yig’indisi (4), 3-si birinchi uchta ikkinchi tartibli figurali sonlarlar yig’indisi (10)
va hokazo (1, 4, 10, 20, 35, …); va hokazo. 1-misol. Tekislikda radiuslari o’zaro
teng  bo’lgan   aylanalar   bir-   biriga  uringan  holda  yuqoridan  1  -  qatorda  bitta,  2  -
qatorda ikkita, 3 – qatorda
uchta   va   hokazo,   joylashtirilgan   bo’lsin.   Masalan,   aylanalar   bunday
joylashuvining   dastlabki   to’rt   qatori   1   -   shaklda   tasvirlangan.   Bu   yerda qatorlardagi   aylanalar   sonlari   ketma-ketligi   birinchi   tartibli   figurali   sonlarni
tashkil   qiladi.   Bu   tuzilmadan   foydalanib,   ikkinchi   tartibli   figurali   sonlarni
quyidagicha hosil qilish mumkin. Dastlab 1 - qatordagi aylanalar soni (1), keyin
dastlabki   ikkita   qatordagi   aylanalar   soni   (3),   undan   keyin   dastlabki   uchta
qatordagi aylanalar soni (6), va hokazo.
      Kombinatorika   iborasi   nemis   matematigi   G.Leybnis   (1646-   1716)   ning
“Kombinatorik   san’at   haqidagi   mulohazalar”   nomli   asarida   birinchi   bor   1665-
yilda   keltirilgan.   Bu   asarda   birlashmalar   nazariyasi   ilmiy   jihatdan   ilk   bor
asoslangan.   O’rinlashtirishlarni   o’rganish   bilan   birinchi   bo’lib   Yakob   Bernulli
shug’ullangan   va   bu   haqdagi   ma’lumotlarni   1713   -   yilda   bosilib   chiqqan   “Ars
conjectandi”   (Bashorat   qilish   san’ati)   nomli   kitobining   ikkinchi   qismida   bayon
qilgan.   Hozirgi   vaqtda   kombinatorikada   qo’llanilayotgan   belgilashlar   XIX   asrga
kelib shakllandi.
        Kombinatorik   masalalar   va   ularni   yechishda   qo’llaniladigan
qoidalar.
        Ko’plab   kombinatorik   masalalarni   yechishda   qo’shish   va   ko’paytirish
qoidalari qo’l keladi: a) qo’shish qoidasi: agar X to’plam m elementli, Y to’plam
esa n elementli bo’lsa va ular o’zaro kesishmasa, X UY to’plamning elementlari
soni n    m ga teng, ya’ni agar X   Y       bo’lsa, n(X UY)    n(X)    n(Y) bo’ladi. 
   Umuman ixtiyoriy ikki X va Y to’plamlar uchun n(X UY)    n(X)    n(Y)  
n(X   Y) o’rinli bo’ladi.  2-misol. A shahardan B shaharga uchta yo’l, B dan C ga esa  2 ta yo’l olib
boradi. A shahardan C shaharga necha xil usul bilan borish mumkin? Yechish. A
dan B ga  1-, 2-  va 3-yo’llar  olib boradi. B  shahardan C  shaharga a va b yo’llar
olib boradi.
U holda A dan C ga qo’yiladigan usullar bilan borish mumkin: (1,a), (1,b),
(2,a), (2,b), (3,a), (3,b). Buni boshqacha usul bilan ham hal qilsa bo’ladi. A va B
gacha boradigan yo’llarki, tanlash usuli 3 ta, B dan C gacha boradigan yo’llarni
tanlash usuli esa 2 ta. Bunda ko’paytma qoidasiga ko’ra, yo’llarning tartiblangan
juftliklarini   3  2=6   usul   bilan   tanlash   mumkinligi   ko’rinib   turibdi.   Quyida
kombinatorik   masalalardan   o’rin   almashtirishlar,   takrorlanmaydigan   o’rin
almashtirishlar,   takrorlanmaydigan   o’rinlashtirishlar   va   guruhlashlarni   ko’rib
chiqamiz.
Takrorsiz o’rin almashtirishlar.
Agar   chekli   X   to’plamning   elementlari   qandaydir   yo’l   bilan   raqamlangan
bo’lsa, uni tartiblangan to’plam deymiz: { , ,..., }. 1 2 n X    { x
1 , x
2 , … , x
n	} . Kortej
tushunchasidan   farqli   o’laroq   tartiblangan   to’plam   elemetlari   orasida   o’zaro
tenglari   bo’lmaydi.   Masalan,   (2,3,2,4,5)   kortej   tartiblangan   to’plam   emas,
(2,3,4,5)   esa   tartiblangan   to’plam   bo’ladi.   Bitta   to’plamni   turlicha   tartiblash mumkin. m elementli  X to’plamni necha xil usul  bilan tartiblash mumkin degan
masalani qaraymiz. Har bir tartiblash quyidagicha amalga oshiriladi. To’plamning
qaysi bir elementini 1-nomer bilan, qaysi birini 2-nomer bilan va hokazo qaysi bir
elementini   m   nomer   bilan   belgilaymiz.   Agar   birinchi   element   tanlangan   bo’lsa,
ikkinchi elementni tanlash (m–1) ta elementning ichidan olinadi. Demak, birinchi
element m usul bilan, ikkinchisi esa (m–1) usul bilan tanlanadi. Uchinchi element
(m–2) usul bilan va hokazo oxirgi element m-o’rinni egallaydi. Masalan, {5,6,7}
elementli   to’plam   quyidagicha   tartiblanadi   567,   657,   756   –   birinchi   element   3
usul   bilan   olindi.   657,   756   –   ikkinchi   element   2   usul   bilan   tanlandi.   Oxirgi
tartiblash   765   bo’ladi.   Umumiy   holda   ko’paytirish   qoidasiga   asosan   tartiblash
usulining umumiy soni Pm =m (m-1)...1 m! ga teng bo’ladi. 
Bunday   tartiblash   m   elementdan   takrorlanmaydigan   o’rin   almashtirish
deyiladi. Bunda har bir tartiblangan to’plamning elementlari turlicha bo’ladi.
  Takrorsiz o’rinlashtirishlar.
Endi  m  elementli  X to’plam elementlaridan nechta k elementli  tartiblangan
to’plamlar   tuzish   mumkin   degan   masalani   qaraymiz.   Bu   masalaning   yuqoridagi
masaladan farqi shundaki, bu yerda k elementli tartiblangan to’plamni tuzish k ta
elementni   olish   bilan   tugallanadi.   Bunday   tartiblangan   to’plamlarning   sonini
topish uchun k ta m, m–1, m–2, …, m–k+1 sonlarni ko’paytirish yetarli (chunki
{m, m–1, m–2,…,m–k+1} to’plamda k ta element mavjud).
  Shunday qilib, X to’plamdagi k elementli tartiblangan to’plamlar soni 	
Amn
   m(m    1)(m      2)...(m      k    1) n m ga teng bo’ladi. Bunday tartiblangan
to’plamlarni m elementdan k tadan takrorlanmaydigan o’rinlashtirishlar deyiladi.
A
mn
  ning   ifodasini   1    2...(m      k)   ga   ko’paytirib   va   bo’lib,   uning   ko’rinishini
o’zgartirish mumkin:
Bunda  	
Amn  P
m     m! bo’ladi, bu yerda 0!=1 deb olinadi.    Takrorsiz guruhlashlar.
Endi   biz   kombinatorikaning   quyidagi   masalasini   qaraymiz:   m   elementli   X
elementlaridan nechta har biri k elementli qism to’plamlar tuzish mumkin?
Bunday   qism   to’plamlar   m   elementdan   k   tadan   takrorlanmaydigan
guruhlashlar deyiladi. Ularning soni  C
mk
  bilan belgilanadi. Ko’rsatish mumkinki,
bo’ladi.
  → Bo’laklashlar ta’rifi.  
Kombinatorikada   o’rin   almashtirishlar,   o’rinlashtirishlar   va   gruppalashlar
tushunchalari   yordamida   yechiladigan   masalalar   bilan   bir   qatorda
bo’laklashlar ga  doir masalalar ham qaraladi. Bunday masalalar turli vaziyatlarda
paydo   bo’lishlari   mumkin.   Masalan,   qutiga   predmetlarni   joylashda,   axborotni
uzatishda,   pulni   maydalashda,   ko’phad   formulasidan   foydalanish   uchun   daraja
ko’rsatkichini bo’laklashda va hokazo.
Bo’laklashlarga   doir   masalalar   orasida   natural   sonlarni   natural   yoki
manfiymas   butun   qo’shiluvchilar   yig’indisi   sifatida   tasvirlash   masalasi   alohida
o’rin tutadi. Bu masalaning mohiyati quyidagidan iborat.
Berilgan   natural  	
n   sonni  	a1,a2,...,ak   natural   s onlar   yig’indisi   ko’rinishda
ifodalash imkoniyatlari qancha?
Bu masala turli shartlarda qaralishi mumkin. Masalan:
- qo’shiluvchilar tartibi e’tiborga olinishi yoki olinmasligi mumkin;
- bo’laklashlarda   faqat   juft   yoki   toq   sondagi   qo’shiluvchilar
qatnashish sharti qo’yilishi mumkin;
- qo’shiluvchilar   bir-biridan   farqli   yoki   ixtiyoriy   deb   hisoblanishi
mumkin va hokazo.
Tabiiyki,   bo’laklashlarga   doir   kombinatorik   masalalarni   yechishda,
bo’laklanayotgan   son   o’rniga   undan   kichikroq   son(lar)ni   bo’laklash   yoki  qaralayotgan   bo’laklashni   kamroq   sondagi   qo’shiluvchilari   bo’lgan   bo’laklashga
keltirish usuli qo’llanilishi maqsadga muvofiqdir.
Natural  n   sonni   ixtiyoriy  	k ta   (	k   –   natural   son,  	k≤n )  	a1,a2,...,ak   natural
sonlar   yig’indisi,   ya’ni  	
n=	a1+a2+...+ak   ko’rinishda   tasvirlashga  	n   sonni  	k ta
qo’shiluvchilarga bo’laklash  (qisqacha,  bo’laklash ) deb ataladi.
Yuqorida   ta’kidlaganimizdek,   bo’laklash   masalasini   ikki   vaziyatda,   ya’ni
qo’shiluvchilar tartibi e’tiborga olingan yoki olinmagan hollarda qarash mumkin.
Kombinatorik nuqtai nazardan olganda ikkala hol ham qiziqarlidir.
Bo’laklash   masalasini,   avvalo,   qo’shiluvchilar   tartibi   e’tiborga   olingan
holda qaraymiz.
Bu   holda   natural  	
n   sonning  	k ta   qo’shiluvchilarga   bo’laklanishlari   sonini	
B(n,k)
  bilan va shu sonning barcha bo’laklanishlari sonini  	B(n)   bilan belgilasak,
ravshanki, 	
B(n)=∑k=1
n	
B(n,k)  tenglik o’rinli bo’ladi.
1-  m i s o l .  Faqat bir yo’nalishda harakatlanganda besh pog’onali zinapoyani
hatlab o’tish imkoniyatlari sonini aniqlash talab etilgan bo’lsin.
Tabiiyki, har bir qadamda faqat bittadan pog’onani bosib o’tib, zinapoyani 5
qadamda   hatlab   o’tish   mumkin.   Bu   harakatni   5   sonning  	
5=1+1+1+1+1
ko’rinishda   bo’laklanishi   kabi   ifodalab,  	
B(5,5	)=1   ekanligini   qayd   etamiz.
Zinapoyani   4   qadamda   ham   hatlab   o’tish   mumkin,   bu   ishning  	
B(5,4	)=4
imkoniyati   bor:  	
5=	2+1+1+1 ,  	5=1+2+1+1 ,  	5=1+1+2+1   va  	5=1+1+1+2 .   Shu
usulda davom etib, 3 qadam uchun 	
B(5,3	)=6 ta – 	5=3+1+1 , 	5=1+3+1 , 	5=1+1+3
,  	
5=	2+2+1 ,  	5=	2+1+2 ,  	5=1+2+2   hamda 2 qadam uchun  	B(5,2	)=4 ta –	5=4+1 ,	
5=3+2
,  	5=	2+3 ,  	5=1+4   tengliklarni   yozamiz.   Endi   barcha   pog’onalarni   bir
qadamda   hatlab   o’tishga  	
B(5,1	)=1   imkoniyat   va  	5=5   tenglik   mos   kelishini
e’tiborga olsak, mumkin bo’lgan barcha imkoniyatlarni bayon qilgan bo’lamiz.
Shunday   qilib,   faqat   bir   yo’nalishda   harakatlanganda   besh   pog’onali
zinapoyani hatlab o’tish imkoniyatlari soni	
B(5)=B(5,1	)+B(5,2	)+B(5,3	)+B(5,4	)+B(5,5	)=16 bo’ladi.  ■
Endi  B(n,k)   va  	B(n)   miqdorlarni   hisoblash   formulalarini   topish   bilan
shug’ullanamiz.
Dastlab  	
n=1   bolgan holni qaraymiz. Tabiiyki, birni natural sonlar yig’indisi
qilib   bo’laklash   haqida   gap   bo’lishi   mumkin   emas.   Shunday   bo’lishiga
qaramasdan, birni faqat bitta qo’shiluvchidan iborat deb qarab, yuqorida berilgan
ta’rifga  mos  keluvchi  	
B(1,1	)=1=C00=C1−10	=Cn−10 ta  bo’laklashga  ega   bo’lamiz.  Jami
bo’laklashlar soni 	
B(1)=B(1,1	)=Cn−10	=2n−1  bo’ladi 1
.	
n=2
  bo’lgan holda  	k=1   qo’shiluvchili  	B(2,1	)=1=C10=C2−10	=Cn−1	0 ta (	2=2 ) va	
k=2
  qo’shiluvchili  	B(2,2	)=1=C11=C2−11	=Cn−1	1 ta   (	2=1+1 )   bo’laklashlarga   ega
bo’lamiz. Bu hol uchun jami bo’laklashlar soni	
B(2)=	B(2,1	)+B(2,2	)=Cn−1	0	+Cn−1	1	=2n−1
.
Agar  	
n=3   bo’lsa,   u   holda  	k=1   qo’shiluvchili  	B(3,1	)=1=C20=C3−10	=Cn−10 ta   (	
3=3
),  	k=2   qo’shiluvchili  	B(3,2	)=2=C21=C3−1	1	=Cn−1	1 ta   (	3=	2+1=1+2 )   va  	k=3
qo’shiluvchili  	
B(3,3	)=1=C22=C3−12	=Cn−12 ta   (	3=1+1+1 )   bo’laklashlar   bor.   Bu   holda
jami bo’laklashlar soni uchun	
B(3)=B(3,1	)+B(3,2	)+B(3,3	)=Cn−1	0	+Cn−1	1	+Cn−1	2	=2n−1
tenglik o’rinlidir.
Shunday   davom   etib,   “istalgan  	
n   natural   sonning  	k ta   qo’shiluvchilarga
bo’laklanishlari   soni   (	
n−1 ) ta   elementdan   (	k−1 ) talab   gruppalashlar   soniga   teng,
ya’ni  	
B(n,k)=Cn−1k−1 ”   degan   farazga   kelish   mumkin.   Agar   bu   faraz   tasdiqlansa ,
binomial   koeffitsientlarning   yig’indisi   haqidagi   xossasiga   ko’ra,	
B(n)=∑i=0
n−1
Cn−1i	=2n−1
 bo’ladi.  
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  (	n−1 ) ta elementdan  (	
k−1
) talab gruppalashlar soniga  teng, ya’ni 	B(n,k)=Cn−1k−1 .
1
. 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 	
2n−1 ga teng, ya’ni 	B(n)=2n−1 .
I s b o t i .  Natural 	
n  sonning barcha bo’laklanishlari to’plamini 	S(n)  deb, shu	
n
  sonning   birinchi   qo’shiluvchisi  	i ga   (	i=1,2	,...,n )   teng   bo’lgan   bo’laklanishlari
to’plamini  esa  	
Si(n)   bilan belgilaymiz. Tushunarliki,  	S(n)=	¿i=1
n
Si(n)   bo’ladi. Agar	
Si(n)
 to’plam elementlari sonini 	Qi(n)  deb belgilasak, yuqoridagi tenglikka asosan	
B(n)=∑i=1
n
Qi(n)
  bo’ladi. Endi  	Qi(n)=B(n−i)   (	i=1,2	,...,n−1 ) va  	Qn(n)=1   tengliklarni
hisobga olib,	
B(n)=∑i=1
n−1
B(n−i)+1=1+∑i=1
n−1
B(i)
tenglikka   ega   bo’lamiz.   Bu   tenglik   ixtiyoriy  	
n   natural   son   uchun   to’g’ri.
Shuning uchun, bu tenglikdagi 	
n ni (	n+1 )ga almashtirib,	
B(n+1)=1+∑i=1
n−1
B(i)+B(n)=B(n)+B(n)=2B(n)
,
ya’ni  	
B(n+1)=2B(n)   (	n=1,2	,... )   ko’rinishdagi   rekurrent   munosabatni   hosil
qilamiz. Bu rekurrent  munosabat  ketma-ket  qo’llanilsa,  	
B(n)=2n−1   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.
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 	
7=	3+4  ko’rinishdagi bo’laklash mos keladi va hokazo.
2- teoremadan foydalanib, yettining barcha bo’laklanishlari soni 	
27−1=26=64
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,  	k≤n )  	a1,a2,...,ak
qo’shiluvchilarga   bo’laklanishini   qandaydir   shartlarga,   masalan,  	
a1≥	a2≥...≥ak
yoki 	
a1≤	a2≤...≤ak  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  	
R(n,k)   bilan,   uning   barcha
bo’laklanishlari sonini esa 	
R(n)  bilan belgilaymiz.
Bundan   keyin,   bo’laklash   deganda   qo’shiluvchilar   tartibi   e’tiborga
olinmagan holdagi bo’laklashni nazarda tutamiz.
Tabiiyki, quyidagi tenglik o’rinlidir:	
R(n)=∑k=1
n	
R(n,k)
.
Osonlik bilan ko’rish mumkinki, 	
R(1)=1 , 	R(2)=2 , 	R(3)=3 , 	R(4)=5 , 	R(5)=7
, 	
R(6)=11 , 	R(7)=15 . 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:R(8)=	∑k=1
8	
R(8,k)=1+4+5+5+3+2+1+1=	22
.
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.   11-   ma’ruzada  	
R(n) ning   qiymatini   hisoblash   uchun
boshqacha yo’l borligi ko’rsatilgan.
1- jadval
Qo’
shi-
luvchilar
soni Bo’laklanishlar Bo’lakla
nishlar soni
1 8=8	
R(8,1)=1
2 8=7+1=6+2=5+3=4+4	
R(8,2)=4
3 8=6+1+1=5+2+1=4+3+1=4+2+2=3+3+2	
R(8,3)=5
4 8=5+1+1+1=4+2+1+1=3+3+1+1=3+2+2+1
=2+2+2+2	
R(8,4)=5
5 8=4+1+1+1+1=3+2+1+1+1=2+2+2+1+1	
R(8,5)=3
6 8=3+1+1+1+1+1=2+2+1+1+1+1	
R(8,6)=2
7 8=2+1+1+1+1+1+1	
R(8,7)=1
8 8=1+1+1+1+1+1+1+1	
R(8,8)=1
  →
Ferrers 2
 diagrammasi.  
Natural  	
n   sonni  	k ta  	a1,a2,...,ak   natural   qo’shiluvchilarnung   yig’indisi   qilib
bo’laklashga   mos   Ferrers   diagrammasi  	
k ta   qatordan   tashkil   topgan   bo’lib,
2
 Ferrers (Norman Makleod, 1829 – taxminan 1894 yildan so‘ng vafot etgan) – ingliyz matematigi. uning   (yuqoridan   nastga   qarab   hisoblaganda)  i -   qatorida  	ai ta   nuqta   mavjud
bo’ladi.
Ferrers   diagrammasi   tushunchasiga   asoslangan   diagrammali   usul   deb
ataluvchi   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’shmaydigan,   ya’ni  	
a1≥	a2≥...≥ak   shart   bajariladigan   (yoki,
kamaymaydigan   ya’ni  	
a1≤	a2≤...≤ak   shart   bajariladigan )   tartibga   rioya   qilinadi.
Bundan tashqari, qatorlardagi nuqtalar diagrammaning vertikal ustunlarini tashkil
etadigan   qilib   tuziladi.   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.   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 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.  ■
 → 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  	b1,b2,...,bp   toq   qo’shiluvchilarga
bo’laklanishlaridan ixtiyoriy birini qaraymiz:	
n=b1+b1+...+b1	⏟	
r1	
+b2+b2+...+b2	⏟	
r2	
+...+bp+bp+...+bp	⏟	
rp
,
bu   yerda   har   bir  	
bi   (	i=1,p )   qo’shiluvchi   bo’laklanishda  	ri   (	1≤ri≤n )   marta
qatnashadi.  	
ri   sonning   ikkilik   sanoq   sistemasidagi  	ri=	2qi1+2qi2+...+2qis
tasvirlanishini yozamiz, bunda 	
qi1>qi2>...>qis≥0  qandaydir (	s ta) butun sonlar .
Qaralayotgan  	
n   sonning yuqoridagi bo’laklanishida  	ri ta  	bi   qo’shiluvchilarni
bir-biridan   farqli  	
bi2qi1,bi2qi2,...,bi2qis   qo’shiluvchilarga   almashtiramiz.   Tabiiyki,
bunday   almashtirish  	
ri ta  	bi   qo’shiluvchilar   yig’indisining   qiymatini
o’zgartirmaydi.   Shu   jarayonni   barcha  	
i=1,2	,...,p   qiymatlar   uchun   takrorlab   va
qo’shiluvchilarning   mos   qiymatlarini   yozib,  	
n   sonning   har   xil   qo’shiluvchilarga
bo’laklanishlaridan   birini   hosil   qilamiz,   chunki  	
bi ,  	bj   sonlarning   toqligi   tufayli	
bi2ql≠bj2qj
 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.  ■ 2- shakl
2- расм 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
qo’shiluvchili va toq qo’shiluvchili barcha bo’laklanishlari orasidagi bir qiymatli
moslikni ko’rsatish mumkin.
Haqiqatdan ham,8=7+1=	7⋅1+1⋅1=	7⋅20+1⋅20=	7+1
,	
8=	5+3=	5⋅1+3⋅1=	5⋅20+3⋅20=	5+3
,	
8=5+1+1+1=5⋅1+1⋅3=5⋅20+1⋅(21+20)=	
¿5⋅20+1⋅21+1⋅20=5+2+1,	
8=	3+3+1+1=	3⋅2+1⋅2=	3⋅21+1⋅21=	6+2
,	
8=3+1+1+1+1+1=3⋅1+1⋅5=3⋅20+1⋅(22+20)=	
¿3⋅20+1⋅22+1⋅20=3+4+1,	
8=1+1+1+1+1+1+1+1=1⋅8=1⋅23=8
.  ■
Diagrammali   usul   yordamida   bo’laklashlarning   turli   xossalarini   osonlik
bilan isbotlash mumkin. Quyida shunday xossalardan ikkitasini ifodalovchi 4- va
5- teoremalarni keltiramiz.
4-   t e o r e m a .   Ixtiyoriy  	
n   natural   sonni  	k ta   natural   qo’shiluvchilarga
bo’laklashlar   soni   shu  	
n   sonning   eng   katta   qo’shiluvchisi  	k ga   teng   bo’lgan
bo’laklanishlari soniga teng.
I s b o t i .   Ferrers   diagrammasining   transpozitsiyasi   tushunchasi   yordamida
natural  	
n   sonning  	k ta natural   qo’shiluvchilarga  bo’laklanishlari  va  shu  sonining
eng   katta   qo’shiluvchisi  	
k ga   teng   bo’lgan   bo’laklanishlari   orasida   bir   qiymatli
moslik   o’rnatish   mumkin.   Bu   bir   qiymatli   moslikka   ko’ra   teoremaning   nasdig’i
to’g’ridir.  ■
7-   m i s o l .   3-   misoldan   ma’lumki,   8   uchun   uchta   qo’shiluvchili   beshta
bo’laklash   mavjud,   bu   son   uchun   qo’shiluvchilarning   eng   kattasi   uchga   teng
bo’lgan  bo’laklashlar  ham   beshtadir.  2-  jadvalda  bu bo’laklashlar   bir-biriga mos
ravishda ikki ustun qilib keltirilgan. 5-   t e o r e m a .   Ixtiyoriy  n   natural   sonning   hech   bir   qo’shiluvchisi  	k dan
oshmaydigan   bo’laklanishlari   soni   (	
n+k )   sonining  	k ta   qo’shiluvchilarga
bo’laklanishlar soniga teng.
I s b o t i .   Birinchidan,   shuni   ta’kidlash   lozimki,   Ferrers   diagrammasining
transpozitsiyasi  	
n   sonning   hech   bir   qo’shiluvchisi  	k dan   oshmaydigan
bo’laklanishlari   bilan   shu   sonning  	
k tadan   oshmaydigan   qo’shiluvchilarga
bo’laklanishlari   orasida   o’zaro   bir   qiymatli   moslik   o’rnatadi.   Bu   bir   qiymatli
moslik   asosida  	
n   sonning   hech   bir   qo’shiluvchisi  	k dan   oshmaydigan   barcha
bo’laklanishlari   soni   shu  	
n   sonning  	k tadan   oshmaydigan   qo’shiluvchilarga
bo’laklanishlari soniga teng deb xulosa qilish mumkin.
Ikkinchi   tomondan,  	
n   sonning  	k tadan   oshmaydigan   qo’shiluvchilarga
bo’laklanishiga mos Ferrers diagrammasi 
n ta nuqtadan tashkil topgan bo’lib, ular	
k
tadan   oshmaydigan   qatorlarda   joylashgan   bo’ladi.   Bunday   diagrammalarning
har biriga 	
k ta nuqtadan tuzilgan ustunni chap tomondan joylashtirsak, 	k ta qatorga
va (	
n+k )ta nuqtali diagrammaga ega bo’lamiz. Aksincha, (	n+k )ta nuqtali har bir
Ferrers   diagrammasidan  	
k ta   qatorga   ega   birinchi   ustunni   olib   tashlasak,  	n ta
nuqtadan   tashkil   topgan   va   qatorlari   soni  	
k tadan   ko’p   bo’lmagan   diagrammani
hosil qilamiz.
Ko’rsatilgan   bu   ikki   turdagi   diagrammalar   orasidagi   o’zaro   bir   qiymatli
moslik 	
n  sonni qo’shiluvchilari 	k tadan oshmaydigan bo’laklashlar soni 	R(n+k,k)
ifodaga tengligini tasdiqlaydi. 2- jadval
8 sonining 3ta qo‘shiluvchili
bo‘laklanishlari 8 sonining eng katta
qo‘shiluvchisi 3ga teng
bo‘laklanishlari
6+1+1 3+1+1+1+1+1
5+2+1 3+2+1+1+1
4+3+1 3+2+2+1
4+2+2 3+3+1+1
3+3+2 3+3+2  Xulosa
      Xulosa   qilib   shuni   aytish   mumkinki,   Kombinatorik   masalalar   nafaqat
matematika   go’zalligini   ko’rsatishga,   balki   amaliy   matematik   masalarni
yechishda   yangi   kompyuter   texnoogiyalarining   imkoniyatlarini   ko’rsatishga
imkon   beradi.   Diskret   matematikaning   masalalaridan   hisoblangan   kombinatorik
masalalar   ko’pincha   ob’ektlarning   turli   kombinatorik   konfiguratsiyalarini
tanlashga   va   ular   orasidan   u   yoki   bu   masala   shartigav   nuqtai   nazaridan   eng
yaxshisini   tanlashga   olib   kelinadi.   Shuning   uchun   keng   tarqalgan   kombinatorik
konfiguratsiyalarni   hosil   qilish   algoritmlarini   bilish   masalani   butunlay
muvaffaqiyatli yechishning zarur sharti hisoblanadi. Foydalanilgan adabiyotlar va elektron saytlar:
1. Kombinatorika elementlari (uslubiy qo’llanma) Samarqand-2020 Xalikulov 
S.I., Quljonov O’., Ostonov Q. Kombinatorika elemementlari.  Uslubiy qo’llanma.
- Samarqand: SamDU nashri, 2020. - 78 bet
2.   https://uz.wikipediya.org  sayti Kombinatorika haqida
3.   https://fayllar.org  sayti Bo’laklashlar kombinatorikasi
Купить
  • Похожие документы

  • Ekonometrika asoslari fanidan testlar
  • Haqiqiy Yevklid fazosida chiqizli almashtirishlar
  • Funksiyaning integralinuvchanlik mezoni
  • Ekstirimal masalalar kurs ishi
  • Tenglama va tengsizliklar yechishda integral va hosilani qo’llash

Подтвердить покупку

Да Нет

© Copyright 2019-2026. Created by Foreach.Soft

  • Инструкция по снятию с баланса
  • Контакты
  • Инструкция использования сайта
  • Инструкция загрузки документов
  • O'zbekcha