Kombinatorika va graflar nazariyasi
Ushbu uslubiy qo'llanma "Amaliy matematika va Informatika", "Informatika va axborot texnologiyalari" va “Axborot xavfsizligi” bakalavriat ta'lim yo'nalishlari talabalari uchun mo'ljallangan bo'lib, “Kombinatorika va graflar nazariyasi” fanining birinchi bobi hisoblangan kombinatorikaga doir nazariyani o'z ichiga oladi. Qo'llanmada kombinatorikaga doir nazariy bilimlar bayon qilinib, har bir mavzuga doir misollar yechimlari berilgan va mustaqil yechish uchun masalalar keltirilgan. Qo'llanma O'zbekiston Milliy universiteti Matematika fakultetida "Kombinatorika va graflar nazariyasi” fani bo'yicha o'qilgan ma'ruzalar va olib borilgan amaliy mashg'ulotlar asosida tayyorlangan bo'lib, O'zbekiston Respublikasi Oliy va o'rta maxsus ta'lim vazirligi tomonidan tasdiqlangan Davlat ta'lim standartlariga mos keladi.
Asosiy mavzular
- To'plamlar va ular ustida amallar. Akslantirishlar: Ushbu bobda to'plam deganda biror umumiy xususiyatga ega bo'lgan narsalar majmuasi, yig'ilmasi tushuniladi. Toʻplamni tashkil etuvchilari shu toʻplamning elementlari deb ataladi. To'plamni tashkil etuvchi elementlar soni chekli yoki cheksiz boʻlishi mumkin. Toʻplamlarni odatda, lotin alifbosining bosh harflari {A, B, C, ...}, uning elementlarini esa alifboning kichik harflari {a, b, c, ...} orqali belgilanadi. Birlik va ko'plik elementlari o'zaro munosabatlari, ya'ni akslantirishlar va ularning turlari, shuningdek, kombinatorikaning asosiy elementlari, kombinatsiyalar, gruppalashlar, o'rin almashtirishlar va boshqa mavzularni o'z ichiga oladi.
- Kombinatorikaning asosiy elementlari: Ushbu paragrafda kombinatorikaning asosiy obyektlari, tushunchalari va formulalari haqida gap boradi. Dastlab kombinatorikaning asosiy metodlaridan biri bo'lgan matematik induksiya metodiga doir misol keltiriladi. Shuningdek, faktorial, oʻrinlashtirishlar soni, gruppalashlar soni kabi asosiy elementlar ko'rib chiqiladi.
- Asosiy kombinatsiyalar: Ushbu paragrafda kombinatorikaning asosiy formulalarini keltiramiz. Xususan, A to'plamni B to'plamga akslantiruvchi akslantirishlar soni, inyektiv akslantirishlar soni, qismiy akslantirishlar soni, shuningdek, multito'plam tushunchasi va uning xossalari bilan tanishib chiqamiz.
- Binar munosabatlar va ekvivalentlik munosabatlari soni: Binar munosabat tushunchasi to'plamlar nazariyasi, diskret matematika, kombinatorika va graflar nazariyasining asosiy tushunchalardan biri hisoblanadi. Ushbu bobda binar munosabatlarning turlari, xususan, refleksiv, simmetrik, tranzitiv va ekvivalentlik munosabatlari hamda ularning soni keltirilgan.
- Kiritish va chiqarish qoidasi: Ushbu paragrafda kombinatorikaning asosiy formulalarini keltiramiz. Xususan, A to'plamning r ta shartini qanoatlantiruvchi elementlari soni va birlashmalarning umumiy qoidasi kiritish va chiqarish qoidasi deb nomlanadi. Shuningdek, surektiv akslantirishlar soni uchun formula keltirilgan.
- Rekurrent munosabatlar metodi va Fibonachchi sonlari: Kombinatorikaning ba'zi masalalari rekurrent munosabatlar deb nomlanuvchi, n ta elementli to'plam yoki munosabatlar uchun qo'yilgan masala elementlar soni n dan kichikroq to'plam yoki munosabatlar uchun qo'yilgan masalaning yechimi orqali ifodalanuvchi metod yordamida yechiladi. Fibonachchi sonlari ham shu metod yordamida aniqlanadi.
- Hosil qiluvchi funksiyalar va Katalan sonlari: Ushbu bobda darajali qatorlar, hosil qiluvchi funksiyalar va Katalan sonlari tushunchalari hamda ularning xossalari ko'rib chiqiladi. Fibonachchi sonlari va Katalan sonlarini hosil qiluvchi funksiyalar yordamida aniqlash usullari keltirilgan.