|
Kombinatorika elementlari
|
| bet | 4/7 | | Sana | 13.12.2023 | | Hajmi | 340,5 Kb. | | #118021 |
Bog'liq kombinatorika elementlarida o\'rin almashish va guruhlashlar2. Yig’indi qoidasi. A va B chekli to’plamlar berilgan bo’lsin.
Agar bo’lsa,
n( ) = n(A)+n(B) bo’ladi.
Masalan, A = {1,2,3}, B = {a, b, c, d} bo’lsa n( ) = 3+4=7 bo’ladi.
2) Agar bo’lsa, n( ) = n(A)+n(B) – n( ) bo’ladi.
Masalan, A = {a, b, c, d, e}, B = {d, e, f, g} to’plamlar birlashmasi 7 ta elementdan tashkil topgan (9 ta elementdan emas). Buning sababi d, e elementlar ikkala to’plamda ham bor bo’lib to’plamda ular bir marta qatnashadi. Demak, 9 dan 2 ni ayirib tashlash kerak, y’ni
n( ) = n(A)+n(B) – n( ) = 5+4-2=7.
3. Ko’paytirish qoidasi. A = { , ,..., } va B = { , ,.., }
to’plamlar berilgan bo’lsin. Bu to’plamlar elementlaridan nechta ( , ) juftlik tuzish mumkinligini ko’rsatamiz. Barcha juftliklar quyidagicha joylashtrilishi mumkin:
( , ( ,…, (
( , ( , ,…, ( ,
( , ( ,…, (
Bu jadvalda n ta satr va m ta ustun bo’lib, ulardagi barcha juftliklar soni nm ga teng. Bu yerda
Ko’paytma qoidasi ko’rinishda yoziladi. Umuman isbotlash mumkinki
Ko’paytma qoidasiga oid kombinatorika masalasining umumiy ko’rinishi quidagidan iborat: Agar elementni m usul, y elementni n usul bilan tanlash mumkin bo’lsa, ) tartiblangan juftlikni usul bilan tanlash mumkin.
Masalan, 1dan 9gacha sonlardan nechta usul bilan turli raqamli ikki xonali son yozish mumkinligini topish talab qilingan bo’lsa, uni quyidagicha amalga oshirish mumkin. 1-raqamni 9 usul bilan, 2-raqamni ham 9 usul bilan tanlash mumkin. Demak, talab etilgan ikki xonali sonlar soni ta bo’ladi.
Endi asosiy kombinatorik masalalar va ularni echish usullari bian tanishamiz.
4.
to’zish mumkin?
Bu oldingi masaladan umumiyroq bo’lib, undan farqi shuki, tartiblash k-elementda tugatiladi. Ularning umumiy soni
m(m-1)(m-2)….(m-k+1)
ko’pytmaga teng. U bilan belgilanadi va m elementdan k tadan takrorlanmaydigan o’rinlashtirishlar soni deb ataladi:
o!=1deb qabul qilinadi. Misol. Auditoriyadagi 30 talabadan 3ta faol talabani necha xil usul bilan tanlash mumkin.
Yechish. Takrorlanadigan o’rinlashtrishlar. Masala elementli X to’plam elementlaridan tuzilgan k uzinlikdagi kortejlar sonini toping.
Bu masalani echish uchun dekarit ko’paytmadagi kortejlar sonini topish kerak. Bu dekarit ko’paytma k – uzunlikdagi kortejlardan tarkib topganligini hisobga olsak n (X)=m bo’lgani uchun ko’paytma qoidasiga ko’ra
Demak, m elimintli X to’plam elementlaridan to’zilgan k o’zunlikdagi kortejlar soni mk ga teng ekan. Kombinatorikda bo’nday kortejlarni m elementdan k tadan takhohlanadigan o’rinlashtirishlar deyiladi va deb belgilanadi Misol. 4 elimintli X={a,b,s,d} to’plamdan nechta uzunligi 2 ga teng kortejlar to’zish mumkin.
Echish. . Demak, 16 ta kortejlar to’zish mumkin. Bu kortejlar qo’yidagilardan iborat:
(a;a), (a;b), (a;c), (a;d)
(b;a), (b;b), (b;c), (b;d)
(c;a), (c;b), (c;c), (c;d)
(d;a), (d;b), (d;c), (d;d)
|
| |
