O'rinlashtirish va guruhlash

Bu nima va nega kerak

Oldingi darsda barcha $n$ ta element qatnashadigan o'rin almashtirishlarni o'rgandik. Ammo amaliyotda ko'pincha elementlarning hammasini emas, faqat bir qismini tanlab olishga to'g'ri keladi.

Masalan, 15 nafar o'quvchisi bor sinfni olaylik:

1. Sinfdan bitta sardor va bitta yordamchi saylashda tartib muhim: Ali sardor, Vali yordamchi bo'lishi — Vali sardor, Ali yordamchi bo'lishidan farq qiladi.
2. Xuddi shu sinfdan navbatchilikka 2 nafar o'quvchi tanlashda tartib muhim emas: Ali va Vali — bitta guruh.

Matematikada bu ikki holat ajratiladi:

• Tartib muhim bo'lgan tanlashlar — o'rinlashtirish (размещение);
• Tartib muhim bo'lmagan tanlashlar — guruhlash (сочетание).

Bu tushunchalar DTM testlarida va ehtimollar nazariyasida asosiy vosita hisoblanadi.

Asosiy g'oya

1. O'rinlashtirishlar (Tartib muhim!)

Ta'rif. Berilgan $n$ ta turli elementdan $k$ tadan tanlab tuzilgan va bir-biridan yoki tarkibi, yoki joylashish tartibi bilan farq qiladigan guruhlar o'rinlashtirishlar deyiladi.

O'rinlashtirishlar soni $A_n^k$ formulasi bilan hisoblanadi ($k \le n$):

$A_n^k = n(n - 1)(n - 2) \dots (n - k + 1) = \frac{n!}{(n - k)!}$

Mohiyat: $k$ ta o'ringa elementlarni ketma-ket joylashtiramiz: 1-o'ringa $n$ ta, 2-o'ringa $n-1$ ta, $\dots$, $k$-o'ringa $n-k+1$ ta imkoniyat.

Xususiy hol: $k = n$ bo'lsa, $A_n^n = P_n = n!$.

2. Guruhlashlar (Tartib muhim emas!)

Ta'rif. Berilgan $n$ ta turli elementdan $k$ tadan tanlab tuzilgan va bir-biridan faqat tarkibi bilan farq qiladigan guruhlar guruhlashlar deyiladi.

Guruhlashlar soni $C_n^k$ formulasi bilan hisoblanadi:

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

Nega $k!$ ga bo'lamiz? Tanlangan $k$ ta element o'zaro $k!$ xil tartibda joylashishi mumkin. Guruhlashda bu tartiblar bitta guruh hisoblangani uchun $k!$ ga bo'linadi.

3. Guruhlashning asosiy xossalari

1. Simmetriya xossasi: $C_n^k = C_n^{n - k}$. Misol: $C_{10}^8 = C_{10}^2 = \dfrac{10 \cdot 9}{2} = 45$.
2. Chegara qiymatlari: $C_n^0 = 1$, $C_n^n = 1$, $C_n^1 = n$.
3. Paskal qoidasi: $C_n^k + C_n^{k + 1} = C_{n + 1}^{k + 1}$.
4. Barcha qism to'plamlar soni: $C_n^0 + C_n^1 + \dots + C_n^n = 2^n$.

Yechilgan misollar

1-misol. Formulalarni qo'llash va hisoblash

$A_7^3$ va $C_7^3$ qiymatlarini hisoblang hamda ularning nisbatini toping.

Yechish:

1. O'rinlashtirish: $A_7^3 = 7 \cdot 6 \cdot 5 = 210.$
2. Guruhlash: $C_7^3 = \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = \frac{210}{6} = 35.$
3. Ularning nisbati: $\frac{A_7^3}{C_7^3} = \frac{210}{35} = 6 = 3!$

Javob: $A_7^3 = 210$, $C_7^3 = 35$, nisbat $6$.

2-misol. Sardorlar va jamoa tanlash

Sinfda 12 nafar o'quvchi bor. a) Sardor va uning o'rinbosarini necha xil usulda saylash mumkin? b) Musobaqaga 2 nafar o'quvchini necha xil usulda tanlash mumkin?

Yechish: a) Rollar turlicha (tartib muhim). O'rinlashtirish formulasi: $A_{12}^2 = 12 \cdot 11 = 132.$

b) Har ikki o'quvchi teng huquqli (tartib muhim emas). Guruhlash formulasi: $C_{12}^2 = \frac{12 \cdot 11}{2} = 66.$

Javob: a) $132$; b) $66$.

3-misol. Kombinatorik tenglamalarni yechish

Tenglamalarni yeching: a) $A_x^2 = 56$; b) $C_x^2 = 21$.

Yechish: a) $A_x^2 = x(x - 1) = 56$ (bu yerda $x \ge 2, x \in \mathbb{N}$). $x^2 - x - 56 = 0 \implies (x - 8)(x + 7) = 0.$ Natural son bo'lgani uchun $x = 8$.

b) $C_x^2 = \dfrac{x(x - 1)}{2} = 21$ (bu yerda $x \ge 2, x \in \mathbb{N}$). $x(x - 1) = 42 \implies x^2 - x - 42 = 0 \implies (x - 7)(x + 6) = 0.$ Natural ildiz: $x = 7$.

Javob: a) $x = 8$; b) $x = 7$.

4-misol. Murakkab tanlov (ko'paytirish qoidasi bilan)

Qutida 6 ta oq va 4 ta qora shar bor. Tavakkaliga 3 ta shar olindi. Ulardan 2 tasi oq va 1 tasi qora bo'lishi usullari sonini toping.

Yechish:

1. 6 ta oq shardan 2 tasini tanlash tartibga bog'liq emas: $C_6^2 = \frac{6 \cdot 5}{2 \cdot 1} = 15.$
2. 4 ta qora shardan 1 tasini tanlash: $C_4^1 = 4.$
3. Ikkala shart bir vaqtda bajarilishi kerak ("va" bog'lovchisi), shuning uchun ko'paytirish qoidasiga ko'ra: $N = C_6^2 \cdot C_4^1 = 15 \cdot 4 = 60.$

Javob: $60$ xil usulda.

5-misol. Geometriyada guruhlash

Bir tekislikda yotgan 8 ta nuqtaning hech qaysi uchtasi bir to'g'ri chiziqda yotmaydi. a) Bu nuqtalar orqali jami nechta turli to'g'ri chiziq o'tkazish mumkin? b) Uchlari shu nuqtalarda bo'lgan nechta turli uchburchak yasash mumkin?

Yechish: a) Ikkita ixtiyoriy nuqta bitta to'g'ri chiziqni aniqlaydi. Nuqtalarning tartibi chiziqni o'zgartirmaydi ($AB$ va $BA$ bitta to'g'ri chiziq): $C_8^2 = \frac{8 \cdot 7}{2 \cdot 1} = 28.$

b) Har qanday 3 ta nuqta (bir to'g'ri chiziqda yotmagani sababli) bitta uchburchak hosil qiladi: $C_8^3 = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = 56.$

Javob: a) $28$ ta; b) $56$ ta.

Mashq

Quyidagi masalalarni yeching:

1. Hisoblang: $A_6^2$ va $C_6^2$.
2. Hisoblang: $C_{10}^8$.
3. Tenglamani yeching: $A_n^2 = 72$.
4. Tenglamani yeching: $C_n^2 = 36$.
5. 15 nafar ishchidan 3 kishilik navbatchilik guruhini necha xil usulda tuzish mumkin?
6. 10 ta jamoadan iborat chempionatda oltin, kumush va bronza medallari (1-, 2- va 3-o'rinlar) necha xil usulda taqsimlanishi mumkin?
7. Qutida 5 ta qizil va 6 ta ko'k qalam bor. Ulardan 2 ta qizil va 2 ta ko'k qalamni necha xil usulda tanlab olish mumkin?
8. Bir to'g'ri chiziqda yotmaydigan 7 ta nuqta berilgan. Uchlari shu nuqtalarda bo'lgan nechta uchburchak mavjud?
9. Shaxmat turnirida har bir ishtirokchi qolgan barcha ishtirokchilar bilan bir martadan o'ynadi. Jami 45 ta partiya o'ynalgan bo'lsa, turnirda nechta shaxmatchi qatnashgan?
10. $C_7^3 + C_7^4$ ifodani Paskal xossasidan foydalanib hisoblang.

Javoblar va yechim yo'llari

1. $A_6^2 = 6 \cdot 5 = 30$, $C_6^2 = \dfrac{6 \cdot 5}{2} = 15$. Javob: $30$ va $15$.

2. Simmetriya xossasiga ko'ra: $C_{10}^8 = C_{10}^2 = \dfrac{10 \cdot 9}{2} = 45$. Javob: $45$.

3. $A_n^2 = n(n - 1) = 72 \implies n = 9$ ($9 \cdot 8 = 72$). Javob: $n = 9$.

4. $C_n^2 = \dfrac{n(n - 1)}{2} = 36 \implies n(n - 1) = 72 \implies n = 9$. Javob: $n = 9$.

5. Tartib muhim emas: $C_{15}^3 = \dfrac{15 \cdot 14 \cdot 13}{3 \cdot 2 \cdot 1} = 455$. Javob: $455$.

6. O'rinlar turlicha (tartib muhim): $A_{10}^3 = 10 \cdot 9 \cdot 8 = 720$. Javob: $720$.

7. Qizil qalamlar: $C_5^2 = 10$. Ko'k qalamlar: $C_6^2 = 15$. Jami: $10 \cdot 15 = 150$. Javob: $150$.

8. Uchburchaklar soni: $C_7^3 = \dfrac{7 \cdot 6 \cdot 5}{6} = 35$. Javob: $35$.

9. Har bir partiya 2 kishi orasida o'ynaladi: $C_n^2 = \dfrac{n(n - 1)}{2} = 45 \implies n(n - 1) = 90 \implies n = 10$. Javob: $10$.

10. Paskal xossasiga ko'ra $C_7^3 + C_7^4 = C_8^4 = \dfrac{8 \cdot 7 \cdot 6 \cdot 5}{4 \cdot 3 \cdot 2 \cdot 1} = 70$. Javob: $70$.

Keng tarqalgan xatolar

1. O'rinlashtirish va guruhlashni chalkashtirish. ✗ 10 kishidan 3 kishilik qo'mita tuzishda $A_{10}^3 = 720$ deb hisoblash. ✓ Qo'mitada a'zolarning lavozimi yo'q (tartib muhim emas), shuning uchun guruhlash formulasi qo'llaniladi: $C_{10}^3 = 120$.

2. Maxrajdagi $k!$ ni unutib qoldirish. ✗ $C_7^3 = 7 \cdot 6 \cdot 5 = 210$ deb yozish. ✓ Bu $A_7^3$ ning qiymati. Guruhlashda maxrajda albatta $3! = 6$ bo'lishi shart: $C_7^3 = \dfrac{210}{6} = 35$.

3. Simmetriya xossasini ishlatmasdan hisoblashni murakkablashtirish. ✗ $C_{20}^{18}$ ni hisoblash uchun 18 ta ko'paytuvchini yozib chiqish. ✓ Simmetriya xossasidan foydalanilsa, bir zumda yechiladi: $C_{20}^{18} = C_{20}^2 = \dfrac{20 \cdot 19}{2} = 190$.

4. Ko'p bosqichli masalalarda amallarni adashtirish. ✗ Qutidan 2 ta oq va 3 ta qora shar tanlashda $C_6^2 + C_4^3$ deb qo'shib yuborish. ✓ Ikkala shart birgalikda bajarilishi kerak bo'lganda ("va" bog'lovchisi) usullar soni ko'paytiriladi: $C_6^2 \cdot C_4^3$.

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

Kombinatorikaning asosiy formulalari — $P_n$, $A_n^k$ va $C_n^k$ yordamida har qanday murakkab guruhlarni sanashni o'zlashtirdik.

Endi bu bilimlar yordamida matematikaning eng qiziqarli va hayotiy sohasiga qadam qo'yamiz. Tasodifiy tajribalarda biror hodisaning ro'y berish imkoniyati qanday baholanadi? Tanga yoki zar tashlanganda, lotereya chiptasi olganda yutish imkoniyati qancha? Keyingi darsda ehtimollik asoslari bilan tanishamiz.