Kombinatorika asosiy masalalari. Guruhlash

Kombinatorika asosiy masalalari. Guruhlash

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.

Ta’rif. 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 masalalar kombinatorik masalalar deyiladi.
Kombinatorikada qo’shish va ko’paytirish qoidasi deb ataluvchi ikkita asosiy qoida mavjud.
Qo’shish qoidasi. Agar biror tanlovni usulda, tanlovni usulda amalga oshirish mumkin bo’lsa va bu yerda tanlovni ixtiyoriy tanlash usuli tanlovni ixtiyoriy tanlash usulidan farq qilsa, u holda “ yoki ” tanlovni amalga oshirish usullari soni formuladan topiladi.
Ko’paytirish qoidasi. Agar biror tanlovni usulda, tanlovni usulda amalga oshirish mumkin bo’lsa, u holda “ va ” tanlovni (yoki ( , ) juftlikni) amalga oshirish usullari soni formuladan topiladi.
Takrorlanmaydigan guruhlashlar.

Bizga tartiblanmagan takrorlanmaydigan ta elementi bo`lgan to‘plam berilgan bo`lsin. bilan ni taqqoslaymiz. Bilamizki, ta elementni ta usulda tartiblash mumkin, ya` ni

bo`ladi. Bundan

kelib chiqadi.


Misol 1. Har uchtasi bir to’g’ri chiziqda yotmagan n ta nuqta berilgan. Nuqtalarni ikkitalab tutashtirish natijasida nechta kesma o’tkazish mumkin?
Yechilishi: masala shartiga ko’ra chizmada qavariq n burchak hosil bo’ladi. U holda 1-nuqta (n-1) ta nuqta bilan, 2-nuqta (n-2) ta nuqta bilan va h.k., (n-1) – nuqta 1 ta nuqta bilan tutashtiriladi/ Bunda hosil bo’lgan to’g’ri chiziqlar soni

ga teng bo’ladi.
Teorema 1. ta elementi bo`lgan to‘plamning barcha tartiblanmagan elementli qism to‘plamlari soni

ga teng.
Teorema 2. Aytaylik k₁, k₂ ,..., k_m butun nomanfiy sonlar bo‘lib, va to‘plam ta elementdan iborat bo‘lsin. ni elementlari mos ravishda k₁, k₂ ,..., k_m ta bo‘lgan m ta qism to‘plamlar yigindisi ko‘rinishida ifodalash usullari soni

ta bo‘ladi.
sonlarga polinomial koeffitsiyentlar deyiladi.
Guruhlashning xossalari

1.

2.
3.
Ushbu xossalarni isbotlash uchun kombinatsiyalarni faktorial ko’rinishida yozib chiqish va hisoblash yetarli.
Teorema. elementli to‘plamning barcha qism to‘plamari soni ga teng va quyidagi tenglik o‘rinli:
.
Haqiqatdan ham, - elementli to‘plamning barcha elementli to‘plam ostilari soni bo‘lgani uchun, tushunarliki barcha to‘plam ostilar soni

yig‘indiga teng bo‘lib, ularning yig‘indisi ga teng bo‘ladi.