Kombinatorika tarixi

Kombinatorika tarixi. Kombinatorika so`zi lotincha "combinare" so`zidan olingan bo`lib, "birlashtirish" degan ma'noni bildiradi. Kombinatorika, kombinator analiz, kombinator matematika - matematikaning chekli to`plamlar ustida bajariladigan amallarni o`rganadigan bo`limi. Kombinatorikaning kombinator geometriya deb ataladigan bo`limida el- ementlari soni cheksiz ko`p bo`lgan ba'zi to`plamlar (geometrik guralar) ham o`rganiladi. Masalan, tekislikda yotuvchi chegaralangan qavariq gu -ralar berilgan bo`lib, ulardan har uchtasi umumiy nuqtaga ega bo`lsa, shu guralarning barchasiga tegishli nuqta ham mavjud bo`ladi (J. Xelli teore- masi).
Kombinatorika elementlari. Biror qoida bo`yicha chekli sondagi elementlardan tuzilgan to`plamning mumkin bo`lgan barcha turli xil kombi- natsiyalarini hisoblashga doir masalalar kombinatorika masalalari deyiladi. Matematikaning bunday masalarini yechish bilan shug`ullanadigan bo`limi kombinatorika deyiladi.
Qo`shish qoidasi. Agar A ob'ekt m ta usul bilan, B ob'ekt esa boshqa n ta usul bilan tanlanishi mumkin bo`lsa, u holda A yoki B tanlov m + n ta usul bilan tanlanishi mumkin.
1.1-misol. Savatda 5 ta olma va 3 ta nok bor. Savatdan bitta meva tanlashni necha usulda amalga oshirish mumkin?
Yechish. Bu yerda A savatdagi olmalar, B esa noklar to`plami. Demak m = 5 va n = 3. Qo`shish qoidasiga ko`ra savatdan bitta mevani m + n = 5 + 3 = 8 xil usulda tanlash mumkin.
Ko`paytirish qoidasi. Agar A ob'ekt m ta usul bilan tanlansa va shunday tanlashdan so`ng B ob'ekt n ta usul bilan tanlanishi mumkin bo`lsa, u holda A va B tanlov m*n ta usul bilan tanlanishi mumkin.
1.2-misol. Maktab oshxonasida oq non, qora non va uch xil kolbasa bor.
Ulardan necha xil buterbrod tayyorlash mumkin?
Yechish. Bunda A oshxonadagi nonlar to`plami, B esa oshxonadagi kol- basalar to`plami. Ya'ni m = 2 va n = 3. Ko`paytirish qoidasiga ko`ra buterbrod tayyorlash uchun bir bo`lak non va bir bo`lak kolbasani mn = 2 · 3 = 6 usulda tanlash mumkin.
O`rinlashtirishlar. n ta elementdan tuzilgan chekli to`plam berilgan bo`lsin. n ta turli elementdan k tadan o`rinlashtirishlar deb, berilgan n ta elementdan olingan k ta elementni o`z ichiga olgan barcha mumkin bo`lgan shunday gruppalarga aytiladiki, ular bir-birlaridan yo elementlarining tarkibi, yo tartibi bilan farq qiladi. n ta elementdan k tadan tuzilgan o`rinlashtirishlar soni A^k_n orqali belgilanadi.

formula bo`yicha aniqlanadi. (1.1) formulani quyidagicha ham yozish mumkin:


Endi o`rinlashtirishlarga doir ba'zi misollarni qaraymiz.
1.3-misol. 1) 10 ta elementdan 8 tadan tuzilgan; 2) n + 6 ta elementdan n − 4 tadan tuzilgan o`rinlashtirishlar sonini toping.

1.4-misol. Agar natural sonning yozuvida faqat toq sonlar qatnashsa, bunday sonni "yoqimtoy" son deymiz. Nechta to`rt xonali "yoqimtoy" son mavjud?
Yechish. Toq raqamlar 5 ta, ya'ni 1, 3, 5, 7, 9. Bu misolni yechishda (1.3) formuladan foydalanamiz. Demak jami to`rt xonali "yoqimtoy" sonlar
A = 5⁴ = 625 ta bo`ladi.
O`rin almashtirishlar. n ta turli elementdan tuzilgan o`rin almashtirish- lar deb, n ta elementdan tuzilgan va bir-biridan faqat elementlarining tartibi bilan farq qiladigan mumkin bo`lgan barcha gruppalarga aytiladi.
O`rin almashtirishlar soni Pn orqali belgilanadi.
n ta turli elementdan takrorlamasdan o`rin almashtirishlar soni
P_n = n! (1.4) formula bo`yicha aniqlanadi.
1.5-misol. 4 xil fanni dars jadvaliga necha xil usulda joylashtirish mumkin?
Yechish. Bu misolni yechishda (1.4) formuladan foydalanamiz:
P<sub>4</sub> = 4! = 1 · 2 · 3 · 4 = 24.
Demak 4 xil fanni dars jadvaliga 24 xil usulda joylashtirish mumkin.
m ta turli elementdan takrorlash bilan, chunonchi birinchi tipdagi k1 ta elementdan, ikkinchi tipdagi k2 ta elementdan va hokazo n tipdagi kn ta elementdan tuzilishi mumkin bo`lgan o`rin almashtirishlar soni
1.5
formula bilan aniqlanadi, bu yerda k<sub>1</sub> + k<sub>2</sub> + · · · + k<sub>n</sub> = m.
1.6-misol. Bir egatga 5 ta atirgul va 4 ta lolani necha xil usulda ekish mumkin.
Yechish. Ushbu misolda k1 = 5 ta (atirgul) birinchi tip elementdan, k2 = 4 ta (lola) ikkinchi tip elementdan takrorlanadigan o`rin almashtirishlar sonini topish talab qilingan. (1.5) formulaga ko`ra

Gruppalashlar. n ta turli elementdan k tadan tuzilgan gruppalash deb, berilgan n ta elementdan olingan k ta elementni o`z ichiga olgan va bir biridan kamida bitta elementi bilan farq qiladigan barcha mumkin bo`lgan birlashmalarga aytiladi.
n ta elementdan k tadan tuzilgan gruppalashlar soni C_n^k orqali belgilanadi.

1.7-misol. Guruhda 25 nafar talaba bor. Fan olimpiadasida qatnashish uchun 3 nafar talabadan iborat jamoani necha xil usulda tanlab olish mumkin?
Yechish. Bu masalani yechishda (1.7) formuladan foydalanamiz: