Kombinatorika Asoslari - Алгебра - Курсовые работы

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

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

Продавец

Navruz

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

25 Продаж

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

Купить

Похожие документы
To’plamlar va ular ustida amallar. To’plamda akslantirishlar 26
Tekislikda kordinatalar metodi 26
Sonli qatorlar 26
Sonli qatorlar 2-variant
Sonlar ketma-ketligi va uning xossalari 26