O'rin almashtirishlar

Bu nima va nega kerak

Kundalik hayotda biz turli elementlarni tartiblash va sanash bilan bog'liq vaziyatlarga tez-tez duch kelamiz: telefon parolini tanlash, musobaqa qatnashchilarini saflab qo'yish yoki kitoblarni javonga terish. Har bir variantni qog'ozda bittalab yozib sanash ko'p vaqt oladi va adashish xavfi yuqori.

To'plam elementlarini saralash, guruhlash va sanash qonuniyatlarini o'rganuvchi bo'lim kombinatorika deb ataladi. U dasturlashda, algoritmlar nazariyasida, axborot xavfsizligida va ehtimolliklar nazariyasida keng qo'llaniladi.

Ushbu darsda biz kombinatorikaning poydevori hisoblangan ko'paytirish qoidasi, faktorial va o'rin almashtirishlar bilan tanishamiz.

Asosiy g'oya

Kombinatorikaning asosiy qoidalari

1. Qo'shish qoidasi: Agar $A$ elementni $m$ xil usulda, $B$ elementni $n$ xil usulda tanlash mumkin bo'lsa va ularni bir vaqtda tanlab bo'lmasa, "$A$ yoki $B$" elementni $m + n$ xil usulda tanlash mumkin.
2. Ko'paytirish qoidasi: Agar $A$ elementni $m$ xil usulda, shundan so'ng $B$ elementni $n$ xil usulda tanlash mumkin bo'lsa, $(A, B)$ juftlikni $m \cdot n$ xil usulda tanlash mumkin.

Faktorial tushunchasi

1 dan $n$ gacha bo'lgan natural sonlar ko'paytmasi faktorial deyiladi va $n!$ kabi belgilanadi:

$n! = 1 \cdot 2 \cdot 3 \dots (n - 1) \cdot n$

Maxsus kelishuv: $0! = 1$ deb qabul qilingan.

Asosiy xossa: $n! = n \cdot (n - 1)!$. Dastlabki qiymatlar: $1! = 1$, $2! = 2$, $3! = 6$, $4! = 24$, $5! = 120$, $6! = 720$.

O'rin almashtirish (Permutatsiya)

Ta'rif. Faqat elementlarining joylashish tartibi bilan farq qiladigan, berilgan $n$ ta elementdan tuzilgan to'plamlar o'rin almashtirishlar deyiladi.

$n$ ta elementdan tuzilgan o'rin almashtirishlar soni $P_n$ belgisi bilan belgilanadi:

$P_n = n! = 1 \cdot 2 \cdot 3 \dots n$

Misol: 3 ta harf ($A, B, C$) berilgan. Ularning o'rnini almashtirib $P_3 = 3! = 6$ ta qator tuzish mumkin: $ABC, ACB, BAC, BCA, CAB, CBA$.

Takrorli o'rin almashtirishlar

Agar $n$ ta element orasida bir xillari bo'lsa, ya'ni 1-tur element $k_1$ marta, 2-tur $k_2$ marta, $\dots$, $m$-tur $k_m$ marta takrorlansa ($k_1 + k_2 + \dots + k_m = n$), takrorli o'rin almashtirishlar soni:

$P_n(k_1, k_2, \dots, k_m) = \frac{n!}{k_1! \cdot k_2! \dots k_m!}$

Yechilgan misollar

1-misol. Faktorialli ifodalarni hisoblash

Ifodalarni soddalashtiring: a) $\dfrac{8!}{6! \cdot 2!}$; b) $\dfrac{n!}{(n - 2)!}$.

Yechish: a) $8! = 8 \cdot 7 \cdot 6!$ ekanidan: $\frac{8!}{6! \cdot 2!} = \frac{8 \cdot 7 \cdot 6!}{6! \cdot 2} = \frac{56}{2} = 28.$

b) $n! = (n - 2)! \cdot (n - 1) \cdot n$ ekanidan: $\frac{n!}{(n - 2)!} = \frac{(n - 2)! \cdot (n - 1) \cdot n}{(n - 2)!} = n(n - 1) = n^2 - n.$

Javob: a) $28$; b) $n(n - 1)$.

2-misol. Oddiy o'rin almashtirish

5 nafar o'quvchini bir qatordagi 5 ta o'rindiqqa necha xil usulda o'tqazish mumkin?

Yechish: Barcha 5 nafar o'quvchi safda qatnashadi va o'rin tartibi muhim: $P_5 = 5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120.$

Javob: $120$.

3-misol. Shartli o'rin almashtirish

Javonga 6 ta turli kitob terilmoqda. Matematika va fizika kitoblari yonma-yon turishi sharti bilan ularni necha xil usulda joylashtirish mumkin?

Yechish:

1. Matematika va fizika kitoblarini bitta yaxlit blok deb hisoblaymiz.
2. Endi bizda ushbu blok va qolgan 4 ta kitob — jami 5 ta element bor. Ular $5! = 120$ xil usulda joylashadi.
3. Blok ichidagi 2 ta kitob ham o'zaro $2! = 2$ xil tartibda joylashishi mumkin.
4. Ko'paytirish qoidasiga ko'ra: $N = 5! \cdot 2! = 120 \cdot 2 = 240.$

Javob: $240$.

4-misol. Raqamlardan son tuzish

0, 1, 2, 3, 4 raqamlaridan ularni takrorlamasdan nechta turli besh xonali son tuzish mumkin?

Yechish: Besh xonali son 0 raqami bilan boshlana olmaydi.

• 1-raqam (bosh xona): 1, 2, 3, 4 (4 ta imkoniyat).
• Qolgan 4 ta o'ringa qolgan 4 ta raqam $4! = 24$ xil usulda joylashadi. Demak: $N = 4 \cdot 4! = 4 \cdot 24 = 96$.

Boshqa usul: Jami kombinatsiyalar $5! = 120$ ta. 0 bilan boshlanadiganlar $4! = 24$ ta. $N = 5! - 4! = 120 - 24 = 96.$

Javob: $96$.

5-misol. Takrorli o'rin almashtirish

"MAKTAB" so'zidagi harflar o'rnini almashtirib nechta turli olti harfli so'z hosil qilish mumkin?

Yechish: So'zda 6 ta harf bor, 'A' harfi 2 marta qatnashgan. Takrorli o'rin almashtirish formulasiga binoan: $P_6(2, 1, 1, 1, 1) = \frac{6!}{2!} = \frac{720}{2} = 360.$

Javob: $360$.

Mashq

Quyidagi masalalarni yeching:

1. Hisoblang: $\dfrac{7!}{5!}$.
2. Hisoblang: $\dfrac{10!}{8! \cdot 3!}$.
3. Tenglamani yeching: $\dfrac{(n + 1)!}{(n - 1)!} = 30$.
4. 4 nafar o'quvchi bitta qatorga necha xil usulda saf tortishi mumkin?
5. 1, 2, 3, 4, 5 raqamlaridan raqamlari takrorlanmaydigan nechta besh xonali son tuzish mumkin?
6. 0, 1, 2, 3 raqamlaridan raqamlari takrorlanmaydigan nechta to'rt xonali son tuzish mumkin?
7. 6 ta turli kitobdan 2 ta ma'lum kitob yonma-yon turmasligi sharti bilan kitoblarni javonga necha xil usulda terish mumkin?
8. "DARSLIK" so'zidagi harflarning barchasidan foydalanib nechta har xil so'z tuzish mumkin?
9. "QALAM" so'zidagi harflar o'rnini almashtirib nechta turli so'z hosil qilish mumkin?
10. 4 nafar o'g'il va 4 nafar qiz navbatma-navbat (o'g'il, qiz, o'g'il, ...) turishi sharti bilan bir qatorga necha xil usulda saf tortishi mumkin?

Javoblar va yechim yo'llari

1. $\dfrac{7!}{5!} = \dfrac{7 \cdot 6 \cdot 5!}{5!} = 42$. Javob: $42$.

2. $\dfrac{10!}{8! \cdot 3!} = \dfrac{10 \cdot 9}{6} = 15$. Javob: $15$.

3. $\dfrac{(n + 1)!}{(n - 1)!} = n(n + 1) = 30 \implies n = 5$. Javob: $n = 5$.

4. $P_4 = 4! = 24$. Javob: $24$.

5. $P_5 = 5! = 120$. Javob: $120$.

6. Birinchi raqam 0 bo'la olmaydi: $3 \cdot 3! = 3 \cdot 6 = 18$. Javob: $18$.

7. Jami joylashuvlar $6! = 720$. Yonma-yon bo'lgan hollar $5! \cdot 2! = 240$. Yonma-yon bo'lmaganlar: $720 - 240 = 480$. Javob: $480$.

8. Barcha 7 ta harf har xil: $P_7 = 7! = 5040$. Javob: $5040$.

9. 5 ta harf, 'A' harfi 2 marta: $\dfrac{5!}{2!} = \dfrac{120}{2} = 60$. Javob: $60$.

10. O'g'ildan boshlansa: $4! \cdot 4! = 576$. Qizdan boshlansa: $4! \cdot 4! = 576$. Jami: $576 + 576 = 1152$. Javob: $1152$.

Keng tarqalgan xatolar

1. $0! = 0$ deb xato hisoblash. ✗ $0! = 0$ deb olib, $\dfrac{4!}{0!}$ ifodani ma'noga ega emas deb hisoblash. ✓ Qoidaga ko'ra $0! = 1$. Demak, $\dfrac{4!}{0!} = \dfrac{24}{1} = 24$.

2. Faktoriallarni oddiy songa o'xshab qisqartirish yoki qo'shish. ✗ $\dfrac{6!}{3!} = 2! = 2$ yoki $2! + 3! = 5! = 120$. ✓ To'g'ri hisoblash: $\dfrac{6!}{3!} = \dfrac{720}{6} = 120$ hamda $2! + 3! = 2 + 6 = 8$.

3. Nol raqami qatnashganda bosh xonani e'tibordan chetda qoldirish. ✗ 0, 1, 2, 3 raqamlaridan tuzilgan to'rt xonali sonlar sonini $4! = 24$ deb olish. ✓ Son 0 bilan boshlanmaydi. Bosh xonaga 3 ta imkoniyat bor: $3 \cdot 3! = 18$.

4. Blok ichidagi elementlar tartibini unutish. ✗ 2 ta kitob yonma-yon turishi kerak bo'lganda faqat $5! = 120$ deb javob berish. ✓ Blok ichidagi kitoblar ham o'zaro o'rin almashadi ($2! = 2$). Natija: $120 \cdot 2 = 240$.

DTM uslubidagi test

Ushbu mavzu bo'yicha tayyorlangan 5 ta test savoli platformada interaktiv tarzda ishlaydi: yuqoridagi test blokida o'z javobingizni belgilang va to'liq tushuntirish bilan tanishing.

Keyingi qadam

Biz barcha $n$ ta element qatnashadigan o'rin almashtirishlarni o'rgandik.

Agar $n$ ta elementdan faqat bir qismini ($k$ tasini) tanlab olish kerak bo'lsa-chi? Tartib muhim bo'lgan holatlar bilan tartib muhim bo'lmagan tanlashlar qanday farqlanadi? Keyingi darsda kombinatorikaning muhim mavzusi — o'rinlashtirish va guruhlashni o'rganamiz.