Kombinatorika — nazariya, formulalar va misollar

Ushbu darsda kombinatorika — sanash san'ati haqida so'z yuritamiz. Ba'zan bizga "nechta usul bilan?" degan savol beriladi: parolni nechta usulda tuzish mumkin, sinfdan uch kishilik navbatchini nechta usulda tanlash mumkin? Kombinatorika ana shunday sanash masalalarini bir-bittalab sanamasdan, aqlli formulalar yordamida hal qiladi.

§1. Ko'paytirish qoidasi

Har qanday sanashning poydevori — ko'paytirish qoidasi. U juda tabiiy: agar bir ishni bir necha bosqichda bajarsak, umumiy usullar soni bosqichlardagi usullar sonining ko'paytmasiga teng.

Qoida. Agar birinchi amal $m$ usulda, undan mustaqil ravishda ikkinchi amal $n$ usulda bajarilsa, ikkala amal ketma-ket $m\cdot n$ usulda bajariladi.

Savol. Nega qo'shish emas, ko'paytirish? Chunki birinchi amalning HAR BIR usuli uchun ikkinchisining barcha usullari qaytadan ochiladi — usullar "shoxlanadi".

Misol. Menyuda 3 xil taom va 4 xil ichimlik bor. Bitta taom va bitta ichimlikdan tushlikni nechta usulda tanlash mumkin?
Yechish. Taomni tanlash — 3 usul, ichimlikni tanlash — 4 usul. Ko'paytirish qoidasi bo'yicha:

3\cdot 4 = 12

Javob. 12 usul.

§2. O'rin almashtirishlar va joylashtirishlar

Endi tartib muhim bo'lgan holni ko'ramiz. Avval faktorial tushunchasini kiritamiz.

Ta'rif. $n$ ta natural sonning ko'paytmasi $n! = 1\cdot 2\cdot 3\cdots n$ ga faktorial deyiladi. Kelishuv bo'yicha $0! = 1$ .

Ta'rif. $n$ ta turli elementni bir qatorga barcha mumkin bo'lgan tartiblarda joylashtirish — o'rin almashtirish deyiladi va ularning soni $P_n = n!$ ga teng.

Misol. 4 nafar o'quvchini bitta skameykaga nechta usulda o'tqazish mumkin?
Yechish. Birinchi joyga 4 nomzod, ikkinchisiga qolgan 3, keyin 2, keyin 1:

P_4 = 4! = 4\cdot 3\cdot 2\cdot 1 = 24

Javob. 24 usul.

Agar $n$ elementdan faqat $k$ tasini tartib bilan tanlasak, bu joylashtirish bo'ladi.

Qoida. $n$ elementdan $k$ tasini tartibli tanlash usullari soni:

A_n^k = \frac{n!}{(n-k)!} = n\cdot(n-1)\cdots(n-k+1)

Misol. 10 kishilik jamoadan sardor, uning o'rinbosari va kotibni nechta usulda saylash mumkin?
Yechish. Bu yerda lavozimlar turlicha, ya'ni tartib muhim, $n=10$ , $k=3$ :

A_{10}^3 = 10\cdot 9\cdot 8 = 720

Javob. 720 usul.

§3. Guruhlashlar (kombinatsiya)

Ba'zan tanlanganlarning tartibi ahamiyatsiz bo'ladi — masalan, uch kishilik delegatsiyada kim birinchi tanlangani muhim emas. Bunday tanlash guruhlash (kombinatsiya) deyiladi.

Qoida. $n$ elementdan $k$ tasini tartibsiz tanlash usullari soni:

C_n^k = \frac{n!}{k!\,(n-k)!}

Formulaning ma'nosi sodda: joylashtirishlarni ( $A_n^k$ ) olib, tartibning ortiqcha $k!$ hisoblanishini bo'lib tashlaymiz.

Misol. 12 nafar o'quvchidan 3 kishilik navbatchilar guruhini nechta usulda tuzish mumkin?
Yechish. Tartib muhim emas, $n=12$ , $k=3$ :

C_{12}^3 = \frac{12\cdot 11\cdot 10}{3\cdot 2\cdot 1} = \frac{1320}{6} = 220

Javob. 220 usul.

Eslatma. Masalada "tartib muhimmi?" degan savolni doim o'zingizga bering. Muhim bo'lsa — joylashtirish $A_n^k$ , muhim bo'lmasa — guruhlash $C_n^k$ . Bu farqni chalkashtirish eng ko'p uchraydigan xato.

§ Lug'at

Kombinatorika — combinatorics
Faktorial — factorial
O'rin almashtirish — permutation
Joylashtirish — arrangement
Guruhlash (kombinatsiya) — combination
Ko'paytirish qoidasi — multiplication rule

§1. Ko'paytirish qoidasi

§2. O'rin almashtirishlar va joylashtirishlar

§3. Guruhlashlar (kombinatsiya)

§ Lug'at

Bu mavzuni mashq qilib ko'ring