KOMBINATORIKA ELEMENTLARINI VIZULALLASHTIRISH
![KOMBINATORIKA ELEMENTLARINI VIZULALLASHTIRISH](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_1.png)
![Reja
Kirish
I. Kombinatorika haqida umumiy tushunchalar
1.1. Kombinatorika predmeti va paydo bo‘lish
1.2. Kombinatorikada ko‘p qo ‘llaniladigan usul va qoidalar .
II. Takroriy kambinatorika
2.1.Takroriy joylashuvlar.
2.2 Takroriy o‘rin almashishlar
2.3 Takrorlashlar bilan birikmalar
III. Qismlarning kombinatoriklari
III.1 Bo'limlarning kombinatoriklari
III.2 Kombinatorikaga oid masalalar yechish uchun tavsiyalar
Xulosa
Foydalanilgan Adabiyotlar](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_2.png)
![KIRISH
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.
Kombinatoriy masalalarni shakllantirish va yechish uchun kombinator
konfiguratsiyalarning turli modellari qo'llaniladi.
Kombinator konfiguratsiyalarga misollar:
n ta elementning k bo‘yicha joylashishi ba’zi n-elementlar to‘plamining k xil
elementidan iborat tartiblangan to‘plamdir.
n ta elementning almashtirilishi (masalan, 1, 2, ... n raqamlari) bu elementlarning
har qanday tartiblangan to‘plamidir. O'zgartirish, shuningdek, n ta elementning n ga
joylashishi.
n va k birikmasi berilgan n ta elementdan tanlab olingan k elementlar to‘plamidir.
Faqat elementlarning tartibida (lekin tarkibi bo'yicha emas) farq qiladigan to'plamlar
bir xil deb hisoblanadi; kombinatsiyalar joylashtirishdan shunday farq qiladi.
n sonining tarkibi musbat butun sonlarning tartiblangan yig'indisi sifatida n ning har
qanday ko'rinishidir.
n sonining bo'limi musbat butun sonlarning tartibsiz yig'indisi sifatida n ning
istalgan ko'rinishidir.](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_3.png)
![I. Kombinatorika haqida umumiy tushunchalar
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 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 Acharya2 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. O‘rta Osiyo va G‘arbiy Yevropada
yashab ijod qilgan olimlarning kombinatorikaga oid ishlari haqida ushbu bobning
3- paragrafida ma’lumot keltirilgan. Umuman olganda, kombinatorikaning
dastlabki rivoji qimor o‘yinlarini tahlil qilish bilan bog‘liq. Ba’zi atoqli
matematiklar, masalan, B. Paskal3, Yakob Bernulli4, L. Eyler5, P. L. Chebishev6
turli o‘yinlarda (tanga tashlash, soqqa tashlash, qarta o‘yinlari va shu kabilarda)
ilmiy jihatdan asoslangan qaror qabul qilishda kombinatorikani qo‘llashgan.
XVII asrda kombinatorika matematikaning alohida bir ilmiy yo‘nalishi sifatida
shakllana boshladi. B. 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. P. Ferma7
esa figurali sonlar bilan birlashmalar nazariyasi orasida bog‘lanish borligini bilgan.
Kombinatsiya — bu kombinatorikaning asosiy tushunchasi.](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_4.png)
![Bu tushuncha yordamida ixtiyoriy to‘plamning qandaydir sondagi elementlaridan
tashkil topgan tuzilmalar ifodalanadi. Kombinatorikada bunday tuzilmalaming о
‘rin almashtirishlar, о ‘rinlashtirishlar
va guruhlashlar, deb ataluvchi asosiy ko‘rinishlari o‘rganiladi.
. Kombinatorikada ko‘p qo‘llaniladigan usul va qoidalar.
Kombinatorika va graflar nazariyasida tasdiqlami isbotlashning samarali
usullaridan bin bo'lgan matematik induksiya usuli ko‘p qo‘llaniladi. Bu
usulning ketma-ket bajariladigan ikkita qismi bo‘lib, ular quyidagi
umumiy g‘oyaga asoslanadi. Faraz qilaylik, isbotlanishi kerak bo‘lgan
tasdiq birorta xususiy (masalan, i=1) uchun to‘g‘ri bo‘lsin (usulning bu
qismi baza yoki asos, deb ataladi). Agar bu tasdiqning istalgan
t=k>nQ uchun to‘g‘riligidan uning n=k+ 1 uchun to‘g‘riligi kelib :hiqsa, u
holda tasdiq istalgan natural n > k„ son uchun to‘g‘ri bo‘ladi ( induksion
o‘tish).
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.](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_5.png)
![Kombinator masalalarni yechish sxemasi
1. Namunalar
n ta xil elementdan iborat A = {a1, a2,..., an} to‘plamni ko‘rib chiqaylik, biz uni n-
to‘plam deb ataymiz.
yoki n hajmining umumiy populyatsiyasi. N-to'plamdan siz uning qismlarini (kichik
to'plamlarini) hosil qilishingiz mumkin.
Ta'rif. n to‘plamning m ta elementidan iborat bo‘lgan kichik to‘plam n-to‘plamning
m-to‘plami yoki ko- to‘plam deyiladi.
n ta elementning m ga birlashuvi yoki n o‘lchamli populyatsiyadan m o‘lchamdagi
namuna.
Tanlashning ikki yo'li mavjud:
1. O'zgartirishsiz tanlash, bunda tanlangan element bir marta populyatsiyadan
chiqariladi. Namuna](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_6.png)
![(ulanish) bu holda takroriy elementlarni o'z ichiga olmaydi.
2. Qaytish bilan tanlash, bunda tanlov har safar butun populyatsiyadan, ya'ni oldin
amalga oshiriladi
keyingi tanlov bilan avval tanlangan element populyatsiyaga qaytariladi. Namuna
(birikma) ichida
Bunday holda, takrorlashlar mavjud.
Bir xil hajmdagi qaysi namunalar har xil deb hisoblanadi va qaysi biri bir xil bo'lsa,
aralashmani tanlash qoidalariga bog'liq.
niya (quyi to'plamlar, namunalar).Ikki birikma bir-biridan farq qilishi mumkin: 1)
tarkibida kamida bitta turli element bo'lsa yoki
2) kiruvchi elementlarning tartibi.
Tanlash qoidalariga ko'ra, birikmalar uch turga bo'linadi: joylashtirishlar,
almashtirishlar, kombinatsiyalar. ga qarab tanlash usuli (qaytarmasdan yoki
qaytarish bilan), har bir ulanish turi takroriy yoki takroriy bo'lishi mumkin .
2. Takrorlashsiz va takroriy joylashuvlar.
Kombinatorikaning klassik muammosi - takrorlanmasdan joylashtirishlar soni
muammosi, uning mazmuni bo'lishi mumkin. savol bilan ifodalanadi: n ta turli
predmetdan m ni necha usulda tanlash va m xil joyga joylashtirish mumkin?
Shuningdek, kombinatorikaning klassik muammosi tarkibi takrorlanadigan
joylashtirishlar soni muammosidir. savol bilan ifodalanishi mumkin: n ta ob'ektdan
m ni necha xil usulda tanlash va m xil joyga joylashtirish mumkin?
qaysilari orasida bir xil?](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_7.png)
![2 Ta'rif. n-by-m tartibga solish bir-biridan farq qiladigan n-by-m bog'lanishdir
bir-biridan yoki ularning elementlari (tarkibi) bo'yicha yoki ularning joylashish
tartibi bo'yicha.
To‘plamlar nazariyasi tilida bu shunday eshitiladi: n ta elementning m ga ko‘ra
joylashishi tartibli hisoblanadi. n-to'plamning m-kichik to'plami (n o'lchamdagi
umumiy populyatsiyadan tartiblangan m-tanlama). "Buyurtma qilingan" atamasi
namunadagi elementlarning tartibi muhimligini bildiradi: bir xil elementlarga ega,
ammo har xil bo'lgan namunalar ularning tartibi boshqacha.
Vazifa. 4 ta harfdan iborat to'plam bo'lsin: {A B C D}. Ko'rsatilgan 4 ta harfning
barcha mumkin bo'lgan joylarini ikkiga yozing:
a) takrorlash yo'q
b) takrorlashlar bilan.
Yechim.
a) 12 ta shunday joylashtirish mavjud: (AB), (AC), (AD), (BC), (BD), (BA), (CA),
(CB), (CD), (DA), (DB). ), (DC). e'tibor bering, bu
joylashtirishlar o'zlarining tarkibiy elementlari va ularning tarkibi tartibida
farqlanadi. AB va BA joylashuvlarida bir xil harflar mavjud,
lekin ularning tartibi boshqacha.
b) 16 ta shunday joylashuv mavjud (a) ishi uchun berilganlarga
joylashtirishlar bir xil elementlarning (AA), (BB), (CC), (DD) joylashuvi bilan
o'shiladi.](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_8.png)
![Vazifa. 2 ta harfdan iborat to plam bo lsin: {A, B}. dan takrorlashlar bilan barchaʻ ʻ
mumkin bo'lgan joylashtirishlarni yozib oling
4 ta harf.
Yechim. 16 ta shunday joylashtirish mavjud: (AAAA), (BBBB), (AAAB), (AABA),
(ABAA), (BAAA), (AABB), (ABAB), (BABA), (BBAA), (ABBA),
(BAAB), (BBBA), (BBAB), (BABB), (ABBB).
Takrorlanmasdan turli xil tartibga solishlar soni Kombinatorikadagi barcha turdagi
birikmalar uchun formulalar
Anm - n ta elementdan iborat misollar bilan takroriy va
takroriy almashtirishlar va tartibga solishlar A
nm
= n !
( n − m ) ! qaytarilmasdan namuna
uchun. Takrorlashlar bilan tartibga solishlar soni Kombinatorikadagi barcha turdagi
birikmalar uchun formulalar
Anm - n ta elementdan m ga teng misollar bilan
almashtirishlar va takrorlashlar va tartibga solishlar. 2)
Anm= nm qaytarish bilan olib
kelish uchun.
Isbot . Buni isbotlash uchun biz ko'paytirish qoidasidan foydalanamiz.
Namunalarni almashtirmasdan ko'rib chiqing. Birinchi elementni tanlash uchun n ta
imkoniyat mavjud, ikkinchisi uchun (n - 1).
(ikkinchi tanlovdan oldin umumiy populyatsiyada (n –1) elementlar qolgan),..., (n –
m + 1) imkoniyatlarning m-tanlovi bilan.
Shunday qilib, ko'paytirish qoidasi bilan
A
nm
= n
( n − 1 )( n − 2 ) … . ( n − m + 1 )
Ifodani (m - n) ga ko'paytirish va bo'lish yo'li bilan qulayroq shaklda yozamiz!
Anm= (n−m)!(n−m+1)… .(n−2)(n−1)n
(n−m)!
=
n!
(n−m)! deb hisoblanadi . 0! = 1, bu
formuladan m = n holati uchun foydalanishga imkon beradi.
Qaytish bilan tanlovlarni ko'rib chiqing Birinchi elementni tanlash uchun n ta
imkoniyat, ikkinchisi uchun n ta imkoniyat mavjud (tanlashdan oldin
keyingi elementning rom, oldingi tanlangan element o'rnatiladi va umumiy
populyatsiyaga qaytariladi), m- bilan n ta imkoniyat ham mavjud. Shunday qilib
Anm
Vazifa. Ba'zi gazetalar 12 sahifadan iborat. Ushbu gazeta sahifalarida to'rtta
fotosuratni joylashtirish kerak.](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_9.png)
![Agar gazetaning hech bir sahifasida bir nechta fotosurat bo'lmasa, buni necha usul
bilan amalga oshirish mumkin?
Yechim. Ushbu muammoda umumiy aholi soni gazetaning 12 sahifasini tashkil
etadi va ulardan fotosuratlar uchun tanlangan 4 sahifani qaytarmasdan namuna.
Ushbu vazifada nafaqat qaysi sahifalar tanlanganligi, balki qanday tartibda
(fotosuratlarni tartibga solish uchun) ham muhimdir. Shunday qilib, muammo 12
elementdan 4 ta element bo'yicha takrorlashsiz joylashtirishlar sonini aniqlashning
klassik muammosiga qisqartiriladi:
A
nm
=12 !
(12 − 4)! =
12 !
(8)! =12∙11∙10∙9=11880
Shunday qilib, 12 sahifadagi 4 ta fotosuratni 11880 ta usulda joylashtirish mumkin.
Vazifa. Bolada stol o‘yinlari to‘plamidan 1, 3 va 7 raqamlari yozilgan shtamplar
bor edi.U shular yordamida qaror qildi.
markali barcha kitoblarga besh xonali raqamlarni qo'ying - katalog yarating. Qancha
turli besh xonali raqamlar bo'lishi mumkin
qo'ying bolami?
Yechim. Tajriba 3 ta raqamdan birining {1, 3, 7} qaytarilishi bilan 5 martalik
tanlovdan iborat deb taxmin qilishimiz mumkin. Shunday qilib, besh xonali
raqamlar soni 3 ta elementning takrorlanishi bilan 5 ta joylashtirish soni bilan
aniqlanadi:
A
35
=
3 5
=243](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_10.png)
![. Takrorlashlar bilan almashtirishlar
Tanlangan n ta element orasida bir xil (qaytib keladigan namuna) bo'lgan taqdirda,
takroriy almashtirishlar soni muammosi quyidagi savol bilan ifodalanishi mumkin: n
ta ob'ektni necha xil usulda qayta joylashtirishingiz mumkin.
n xil joy, agar n ta ob'ekt orasida k xil turdagi (k < n) bo'lsa, ya'ni bir xil ob'ektlar
mavjud.
Ta'rif. Takroriy almashtirishlar umumiy populyatsiyadan olingan birikmalar bo'lib,
ularning har biri n ta elementdan iborat bo'lib, ular orasida element ham bor.
a1 n1 marta takrorlanadi,](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_11.png)
![a2 n2 marta takrorlanadi,
. . . . . . . . . . . . . . . . . . .
nk marta takrorlanadi
n1 + n2 + ... + nk = n
va ular bir-biridan faqat turli elementlarning joylashish tartibi bilan farq qiladi.
Teorema . Takrorlashlar bilan almashtirishlar soni P
n (n
1 , n
2, …..n
k ) to’g’ri
P
n (n
1 , n
2, …..n
k )= n !
n 1 ! n 2 ! … . n k !
Isbot. Buning isboti aniq, chunki takroriy almashtirishda bir xil elementlarning
almashtirilishi yangi almashtirishni bermaydi.
Vazifa.
"Mississipi" so'zining harflaridan nechta turli harf birikmalarini yasash mumkin?
Yechim. 1 ta “m”, 4 ta “i”, 3 ta “c” va 1 ta “p” harfi, jami 9 ta harf bor.
Shuning uchun, takroriy almashtirishlar soni
P
9 (1
, 4
, 3
, 1)= 9 !
1 ! 3 ! 4 ! 1 ! =2520
6. Takrorlashlar bilan birikmalar](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_12.png)
![Ta'rif. Takroriy birikmalar n ta elementning m ga teng birikmalaridir (m
elementning qaytarilishi bilan tanlash), ular faqat tarkibi jihatidan farq qiladi va shu
bilan birga, alohida birikmalar takrorlanuvchi elementlarni o'z ichiga olishi mumkin.
Vazifa. 2 ta A harfi, 2 ta B harfi, 2 ta C harfi bor. Bu oltita harfdan ikkitasini nechta
usulda tanlash mumkin?
Yechim. Takroriy 6 ta harfdan 2 ta harfni tanlashning 6 ta usuli mavjud: (AA),
(AB), (AC), (BC), (BB), (CC). Quyidagilarning tartibi
harflar hisobga olinmaydi.
Teorema. Kombinatorikadagi barcha turdagi kombinatsiyalar uchun raqamlar
formulalari Cnm - takroriy va takroriy birikmalar misollari bilan almashtirishlar va
joylashtirishlar
Cnm
= Cn−m+1 m = ( n + m − 1 ) !
m !
( n − 1 ) !
Isbot. n xil turdagi ob'ektlar bo'lsin. Agar elementlarning tartibi hisobga olinmasa,
ulardan qancha m elementni bog'lash mumkin. Keling, har bir kombinatsiyadagi
elementlarni turlar bo'yicha tartibga solamiz (avval 1-turdagi barcha elementlar,
keyin 2-chi va boshqalar). Shundan so'ng biz kombinatsiyadagi barcha elementlarni
qayta raqamlaymiz, lekin ikkinchi turdagi elementlarning soniga 1 ni, uchinchi turga
2 ni qo'shamiz va hokazo.Keyin har bir takroriy birikmadan biz takrorlashsiz
kombinatsiyani olamiz, ular quyidagilardan iborat. 1, 2,..., n + m – 1 raqamlari va
har bir kombinatsiya m elementni o'z ichiga oladi.
Demak, bundan kelib chiqadi C
nm
= C
n − m + 1m
=
(n+m−1)!
m!(n−1)!
Kombinatorikadagi barcha turdagi birikmalar uchun formulalar - misollar bilan
takroriy va takroriy almashtirishlar va joylashtirishlar
Vazifa. Texnik kutubxonada matematika, fizika, kimyo va hokazo, jami 16 ta fan
sohasiga oid kitoblar mavjud. Yana 4 ta adabiyotga buyurtma oldi. Bunday
tartibning nechta varianti mavjud?
Yechim. 4 ta buyurtma qilingan kitoblar fanning bir xil bo'limidan va turli
bo'limlardan bo'lishi mumkinligi sababli, bo'limlarni tanlash tartibi muhim bo'lmasa-](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_13.png)
![da, tartib variantlari soni 16 elementning 4 ga takrorlanishi bilan kombinatsiyalar
soni bilan belgilanadi, ya'ni. C164 = C
16 − 4 + 14
= C
194
= ( 19 ) !
4 !
( 15 ) ! =
19 ∙18 ∙17 ∙16
1∙2∙3∙4 =3876
Vazifa. Qandolat do'konida 4 turdagi tortlar sotilgan: napoleonlar, eklerlar, pirojnoe
va puff. 7 ta tortni necha xil usulda sotib olish mumkin?
Yechim. Shubhasiz, keklarni tanlash tartibi muhim emas va kombinatsiyalar
takrorlanuvchi elementlarni o'z ichiga olishi mumkin (masalan, siz 7 ta ekler sotib
olishingiz mumkin). Shuning uchun, 7 ta kek sotib olish usullari soni 7 ta 4 ta
elementning takrorlanishi bilan kombinatsiyalar soni bilan belgilanadi, ya'ni.
C47
= C7+4−1 7 = C107= (10 )!
7!(3)! ==120
Bo'limlarning kombinatoriklari
Ushbu muammolar sinfidagi quyidagi ikkita muammoni ko'rib chiqing:
1. n xil ob’ekt va k turli guruh berilgan. Agar bo'sh guruhlarga ruxsat berilgan
bo'lsa, n xil elementni necha xil usulda k xil guruhga belgilash mumkin? Quyida
yo'llar soni k^n ga teng ekanligini ko'rsatamiz.
2. n xil ob’ekt va k turli guruh berilgan. Agar birinchi guruhda n1 ta, ikkinchi
guruhda n2 va k-da nk bo‘lsa, n1+n2+...+nk=n bo‘lsa, n xil ob’ektni necha xil
usulda k guruhga bo‘lish mumkin. Quyida biz yo'llar soni teng ekanligini
ko'rsatamiz](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_14.png)
![Keling, birinchi muammoning yechimini ko'rib chiqaylik. Umumiy aholi soni k turli
guruhlar {1, 2,..., k} bo lsin. Tajriba har bir mavzu uchun guruh raqamini qaytarishʻ
bilan n-katta tanlashdan iborat deb hisoblashimiz mumkin. E'tibor bering,
elementlar har xil bo'lganligi sababli, elementlar uchun faqat qaysi guruhlar
tanlanganligi emas, balki bu guruhlar qanday tartibda tanlanganligi ham muhimdir.
Shunday qilib, n ta turli ob'ektni k guruhga bo'lish usullari soni takroriy
joylashtirishlar soniga va k elementga n ga qarab aniqlanadi:
Keling, ikkinchi muammoning yechimini ko'rib chiqaylik.
n ta elementni k guruhga bo'lish quyidagicha amalga oshirilishi mumkin. Avval
barcha n ta elementni qatorga joylashtiramiz. Shundan so'ng biz birinchi n1
narsalarni olib, ularni birinchi guruhga, ikkinchi n2 narsalarni ikkinchi guruhga, ...,
oxirgi nk narsalarni k-guruhga qo'yamiz. Ob'ektlarning qatordagi o'rnini o'zgartirish
orqali ob'ektlarning barcha mumkin bo'lgan bo'limlarini olish mumkinligi aniq. n ta
elementning almashinish soni n! bo'lgani uchun ob'ektlarning qatordagi joylashuvi
soni n ga teng! Shu bilan birga, shuni ta'kidlaymizki, birinchi n1 ob'ektlarining har
qanday o'zgarishi hech narsani o'zgartirmaydi, shuningdek, ikkinchi n2, ... va oxirgi
nk. Mahsulot qoidasi tufayli biz n1!n2 ni olamiz!...nk! bo'lim natijasini
o'zgartirmaydigan ob'ektlarning almashtirishlari. Shunday qilib, guruhlarga bo'linish
usullari soni teng
Formula takroriy almashtirishlar soni formulasi bilan bir xil. Xuddi shu natijaga
boshqa yo'l bilan erishish mumkin. Birinchi n1 element n ta elementdan tanlanadi.
Tanlangan elementlarning tartibi befarq bo'lganligi sababli, u kombinatorikadagi
barcha turdagi birikmalar uchun Formulalarga ega - almashtirishlar va
joylashtirishlar takroriy va takroriy tanlovlar misollari bilan.
Shundan so'ng, qolgan n - n1 dan keyingi n2 element tanlanadi. Buni bajarish
mumkin Kombinatorikadagi barcha turdagi birikmalar uchun formulalar -](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_15.png)
![takroriy va takroriy takrorlashsiz almashtirishlar va joylashtirish usullari va
boshqalar.
Kombinatorikadagi barcha turdagi birikmalar uchun formulalar - misollar bilan
takroriy va takroriy almashtirishlar va joylashtirishlar
. Ko'rib turganimizdek, qismlarga ajratish muammolari allaqachon ma'lum bo'lgan
kombinatorik formulalarga olib keldi.
Ko'rib turganimizdek, qismlarga ajratish muammolari allaqachon ma'lum bo'lgan
kombinatorik formulalarga olib keldi.
Vazifa. 7 ta bir xil to'p tasodifiy ravishda 4 teshikka sochilgan (har qanday
miqdordagi to'plar bitta teshikka sig'ishi mumkin). 7 ta marmarni 4 ta teshikka
taqsimlashning necha xil usuli bor?
Yechim. Bizda 7 ta to'p bor, biz ularni 4 teshikka taqsimlaymiz (teshiklar bo'sh
bo'lishi mumkin), ya'ni bu birinchi bo'lim muammosiga to'g'ri keladi, yo'llar soni 4 ^
7 = 16348
Vazifa. Domino o'yinida 4 ta o'yinchi 28 ta zarni teng taqsimlaydi. Ular buni necha
usulda qilishlari mumkin?
Yechim. Bu 28 ta zarni 7 ta zardan 4 ta o'yinchiga bo'lish muammosi. Yuqorida
olingan formuladan foydalanib, bunday bo'linishning yo'llari soni (2-muammo)
mavjud 28 !
7 ! 7 ! 7 ! 7 ! ≈47∙10 15
Kombinatorikaga oid masalalar yechish uchun tavsiyalar
Kombinator masalalarni yechish yangi boshlanuvchilar uchun ma'lum
qiyinchilikdir. Ko'p sabablar bor, lekin ulardan biri aniq - kombinatorikaning
taqdimoti o'ziga xos terminologiyadan (umumiy populyatsiya, namuna, tanlash
qoidalari) foydalanadi. Vazifada bu atamalar, qoida tariqasida, mavjud emas - u
odatiy adabiy tilda tuzilgan va birlashtirilgan.](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_16.png)
![milliy tushunchalar unda yashirin shaklda mavjud. Shuning uchun, vazifaning
mazmunini o'zlashtirgandan so'ng, uni "tarjima qilish" kerak.
matematik tilga.
Buning uchun aniqlab olish kerak
1) umumiy aholi soni - u har doim topshiriqda mavjud bo'ladi, ya'ni kombinator
muammolari bog'liq.
ob'ektlarni tanlash bilan zany va bu tanlov biror narsadan (umumiy aholi) amalga
oshiriladi; generalning hajmi qancha
hajmi;
2) bir yoki bir nechta populyatsiya;
3) namuna nima va namuna hajmi qanday;
4) tanlash qoidalari: takrorlashga ruxsat beriladimi yoki yo'qmi, tanlangan
elementlarning tartibi muhimmi, kompozitsiyani o'zgartirish mumkinmi.
Shundan so'ng, muammoni populyatsiyalar va namunalar tilida qayta shakllantirish
foydalidir. qarab
vaziyatdan kerakli formulani tanlang (jadvalga qarang). Ba'zan murakkabroq
vazifalarda birgalikda foydalanish kerak
qancha formulalar
Xulosa qilib, sonlarning asosiy xossalarini keltiramiz.Kombinatorikadagi barcha
turdagi birikmalar uchun formulalar - takroriy va takroriy takrorlarsiz
almashtirishlar va joylashtirishlar misollar bilan. Avvalo, (3.11) formuladan
foydalanib, bunday raqamlar jadvalini tuzamiz.](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_17.png)
![Raqamlar jadvali Kombinatorikadagi barcha turdagi birikmalar uchun formulalar
- takroriy va takroriy misollar bilan almashtirishlar va joylashtirishlar
uchburchak shaklga ega va matematik Blez Paskal (1623-1662) nomi bilan Paskal
uchburchagi deb ataladi. Paskal uchburchagini tahlil qilib, sonlarning asosiy
xossalarini ko`rish oson.Kombinatorikadagi barcha turdagi birikmalar uchun
formulalar - o`rin almashish va joylashishlar takroriy va takroriy misollar
bilan.
1 - 2 xossalar kombinatsiyaning n ta elementga ega bo'lgan to'plamning m
elementini o'z ichiga olgan kichik to'plam sifatidagi ta'rifidan kelib chiqadi.
3 - 5 xossalar matematik induksiya bilan isbotlangan.
4-xususiyatga ko'ra, Paskal uchburchagini har qanday bosqichda osongina davom
ettirish mumkin. Kombinatorikadagi barcha turdagi birikmalar uchun formulalar -
misollar bilan takroriy va takroriy almashtirishlar va joylashtirishlar](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_18.png)
![Anjir Burjlar turini aniqlash va formulalarni tanlash sxemasi
Shuningdek qarang almashtirishlar, kombinatsiyalar, joylashtirishlar, takroriy
almashtirishlar, almashtirishlar, kombinatsiyalar, joylashtirishlar, Nyuton binomiali,
Barcha turdagi birikmalar uchun formulalar qisqacha mazmuni haqidagi maqola
sizga yoqdimi? Bunga izoh bering, umid qilamanki, endi siz barcha turdagi
birikmalar, kombinatoriklar, almashtirishlar, takroriy joylashtirishlar,
almashtirishlar, birikmalar, bog'lanishlar, Paskal uchburchagi uchun formulalarning
qisqacha mazmuni nima ekanligini va bularning barchasi nima uchun kerakligini va
agar kerak bo'lmasa, tushunasiz deb umid qilaman. tushuning, yoki sharhlar bor,
keyin sharhlarda yozing yoki so'rang, men mamnuniyat bilan javob beraman.
Chuqurroq tushunish uchun men sizga Diskret matematika toifasidagi barcha
a'lumotlarni o'rganishingizni qat'iy tavsiya qilaman. To'plam nazariyasi. Grafik
nazariyasi. Kombinatorika.
Xulosa](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_19.png)
![Men kambinatorika masalalarini ko’rib chiqdim .Kambinatorika vazifalarini
bog’lanish jarayonlarini ko’rdim. Bir qator amaliy masalalarni yechish uchun
berilgan to’plamdan uning qandaydir xossaga ega bo’lgan elementlarini tanlab olish
va ularni ma’lum bir tartibda joylashtirishga to’g’ri keladi.Shuning uchun Biror
chekli to’plam elementlari ichida ma’lum bir xossaga ega bo’lgan elementlaridan
iborat qism to’plamlarni tanlab olish yoki to’plam elementlarini ma’lum bir tartibda
joylashtirish bilan bog’liq masalalarni yechish uchun kombinatorikani bilish talab
etiladi. Bu shuni anglatadiki, kombinatoryal vazifalarni hal qilishda bolalar o'zlari
tomonidan yaratilgan to'plamlarning dastlabki to'plamini va bir qator xususiyatlarini
ajratish va o'zaro bog'lashni o'rganishlari kerak. Amalda, o'quvchilarning aksariyati
bu bilan ishlamaydi. Bolalar psixologlari va o'qituvchilarining fikriga ko'ra, maktab
o'quvchilarining kombinatoryal bilimlarini assimilyatsiya qilish darajasini
oshirishning bir usuli o'rganilayotgan materialni tasavvur qilishdir .
Foydalanilgan adabiyotlar
1. Kombinatorika va graflar nazariyasi H.To’rayev, I.azizov, S,Otaqulov
2. M.A.Sobirov mtematik fanlardan Ruscha-o’zbekcha lug’at
3. T.To’rayev matematik mantiq va diskret matematika
4. Н.Я.Виленкин Комбинаторика M “Наука” 1969
5. Moluch_119_ch2.Molodoy uchyonniy (mejdunarodniy nauchniy jurnal)](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_20.png)
![6. Драгныш.Н.В Визудизилатсия комбинаторных задач теория
вероятностей.](/data/documents/33857dd6-7a77-4a30-970f-8f2d57ad2e60/page_21.png)
KOMBINATORIKA ELEMENTLARINI VIZULALLASHTIRISH
Reja Kirish I. Kombinatorika haqida umumiy tushunchalar 1.1. Kombinatorika predmeti va paydo bo‘lish 1.2. Kombinatorikada ko‘p qo ‘llaniladigan usul va qoidalar . II. Takroriy kambinatorika 2.1.Takroriy joylashuvlar. 2.2 Takroriy o‘rin almashishlar 2.3 Takrorlashlar bilan birikmalar III. Qismlarning kombinatoriklari III.1 Bo'limlarning kombinatoriklari III.2 Kombinatorikaga oid masalalar yechish uchun tavsiyalar Xulosa Foydalanilgan Adabiyotlar
KIRISH 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. Kombinatoriy masalalarni shakllantirish va yechish uchun kombinator konfiguratsiyalarning turli modellari qo'llaniladi. Kombinator konfiguratsiyalarga misollar: n ta elementning k bo‘yicha joylashishi ba’zi n-elementlar to‘plamining k xil elementidan iborat tartiblangan to‘plamdir. n ta elementning almashtirilishi (masalan, 1, 2, ... n raqamlari) bu elementlarning har qanday tartiblangan to‘plamidir. O'zgartirish, shuningdek, n ta elementning n ga joylashishi. n va k birikmasi berilgan n ta elementdan tanlab olingan k elementlar to‘plamidir. Faqat elementlarning tartibida (lekin tarkibi bo'yicha emas) farq qiladigan to'plamlar bir xil deb hisoblanadi; kombinatsiyalar joylashtirishdan shunday farq qiladi. n sonining tarkibi musbat butun sonlarning tartiblangan yig'indisi sifatida n ning har qanday ko'rinishidir. n sonining bo'limi musbat butun sonlarning tartibsiz yig'indisi sifatida n ning istalgan ko'rinishidir.
I. Kombinatorika haqida umumiy tushunchalar 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 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 Acharya2 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. O‘rta Osiyo va G‘arbiy Yevropada yashab ijod qilgan olimlarning kombinatorikaga oid ishlari haqida ushbu bobning 3- paragrafida ma’lumot keltirilgan. Umuman olganda, kombinatorikaning dastlabki rivoji qimor o‘yinlarini tahlil qilish bilan bog‘liq. Ba’zi atoqli matematiklar, masalan, B. Paskal3, Yakob Bernulli4, L. Eyler5, P. L. Chebishev6 turli o‘yinlarda (tanga tashlash, soqqa tashlash, qarta o‘yinlari va shu kabilarda) ilmiy jihatdan asoslangan qaror qabul qilishda kombinatorikani qo‘llashgan. XVII asrda kombinatorika matematikaning alohida bir ilmiy yo‘nalishi sifatida shakllana boshladi. B. 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. P. Ferma7 esa figurali sonlar bilan birlashmalar nazariyasi orasida bog‘lanish borligini bilgan. Kombinatsiya — bu kombinatorikaning asosiy tushunchasi.
Bu tushuncha yordamida ixtiyoriy to‘plamning qandaydir sondagi elementlaridan tashkil topgan tuzilmalar ifodalanadi. Kombinatorikada bunday tuzilmalaming о ‘rin almashtirishlar, о ‘rinlashtirishlar va guruhlashlar, deb ataluvchi asosiy ko‘rinishlari o‘rganiladi. . Kombinatorikada ko‘p qo‘llaniladigan usul va qoidalar. Kombinatorika va graflar nazariyasida tasdiqlami isbotlashning samarali usullaridan bin bo'lgan matematik induksiya usuli ko‘p qo‘llaniladi. Bu usulning ketma-ket bajariladigan ikkita qismi bo‘lib, ular quyidagi umumiy g‘oyaga asoslanadi. Faraz qilaylik, isbotlanishi kerak bo‘lgan tasdiq birorta xususiy (masalan, i=1) uchun to‘g‘ri bo‘lsin (usulning bu qismi baza yoki asos, deb ataladi). Agar bu tasdiqning istalgan t=k>nQ uchun to‘g‘riligidan uning n=k+ 1 uchun to‘g‘riligi kelib :hiqsa, u holda tasdiq istalgan natural n > k„ son uchun to‘g‘ri bo‘ladi ( induksion o‘tish). 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.