Avval o‘rganing: Natural sonlar va amallar
Kombinatorika «nechta usul bilan?» degan savolga javob beradi: nechta son tuzish mumkin, nechta guruh tanlash mumkin, nechta tartibda joylashtirish mumkin. Ehtimollik nazariyasi ham shu sanashga tayanadi. Asosiy qiyinchilik — formulani emas, qaysi formulani tanlashni bilish: tartib muhimmi, takrorlanish bormi?
Bu ikki qoida barcha formulalarning asosi.
Raqamlari har xil bo‘lgan nechta uch xonali son bor?
Raqamlar takrorlanishi mumkin bo‘lsa: 1, 2, 3, 4, 5 raqamlaridan to‘rt xonali sonlar soni 5⁴ = 625.
n ta har xil elementni bir qatorga joylashtirish usullari soni:
Pₙ = n! = 1·2·3·…·n, 0! = 1
Nega? Birinchi o‘ringa n ta, ikkinchisiga n − 1 ta, … oxirgisiga 1 ta tanlov — ko‘paytirish qoidasi.
Takrorli o‘rin almashtirish: elementlar orasida bir xillari bo‘lsa, ularning o‘zaro almashinuvi yangi tartib bermaydi:
P = n!/(n₁!·n₂!·…·nₖ!)
Masalan, MAMA so‘zidan 4!/(2!·2!) = 6 ta har xil «so‘z» tuziladi.
Doira bo‘ylab n kishini o‘tqazish: (n − 1)! (burilishlar bir xil hisoblanadi).
Javonga 5 ta har xil kitob qo‘yiladi, ikkitasi doim yonma-yon bo‘lishi kerak. Nechta usul bor?
n ta elementdan k tasini tanlaymiz.
O‘rinlashtirish (tartib muhim): Aₙᵏ = n!/(n − k)! = n(n − 1)…(n − k + 1)
Guruhlash (tartib muhim emas): Cₙᵏ = n!/(k!(n − k)!) = Aₙᵏ/k!
Nega k! ga bo‘linadi? Har bir guruh k! xil tartibda yozilishi mumkin, guruhlashda esa ularning hammasi bitta deb sanaladi.
Qanday ajratish kerak: tanlanganlarning «roli» yoki «o‘rni» farq qilsa (rais, o‘rinbosar; raqamlar joyi) — A; shunchaki «to‘plam» tanlansa (jamoa, guruh, qo‘l berib ko‘rishish) — C.
Cₙᵏ = Cₙⁿ⁻ᵏ, Cₙ⁰ = Cₙⁿ = 1, Cₙᵏ + Cₙᵏ⁺¹ = Cₙ₊₁ᵏ⁺¹, Cₙ⁰ + Cₙ¹ + … + Cₙⁿ = 2ⁿ
10 o‘quvchidan: a) 3 kishilik guruh; b) rais, o‘rinbosar va kotib nechta usulda tanlanadi?
O‘nburchakning nechta diagonali bor?
Umumiy formula: n(n − 3)/2.
Bir nechta guruhdan alohida tanlansa — ko‘paytiramiz. «Kamida bitta» shartida qarama-qarshi holatni ayirish qulay.
6 o‘g‘il va 5 qizdan 3 o‘g‘il va 2 qizdan iborat komissiya nechta usulda tuziladi?
Shu 11 kishidan 3 kishi tanlanadi, ular orasida kamida bitta qiz bo‘lishi kerak.
(a + b)ⁿ = Σ Cₙᵏ aⁿ⁻ᵏ bᵏ, umumiy had Tₖ₊₁ = Cₙᵏ aⁿ⁻ᵏ bᵏ
(2x − 1)⁵ yoyilmasida x³ oldidagi koeffitsiyentni toping.
(x + 1/x)⁶ yoyilmasidagi ozod hadni (x qatnashmaydigan hadni) toping.
Oldingi formulalar elementlar takrorlanmaydi degan farazga tayangan edi. Ammo PIN-kod, telefon raqami, avtomobil raqami kabi masalalarda bir xil raqam qayta-qayta ishlatilishi mumkin. Bunda har bir o‘rin uchun tanlov soni o‘zgarmaydi, va ko‘paytirish qoidasi darhol formulani beradi.
Takrorli o‘rinlashtirish: n turdagi elementdan k o‘rinli tartiblangan qatorlar soni nᵏ
Masalan, 0 dan 9 gacha raqamlardan to‘rt xonali PIN-kodlar soni 10⁴ = 10 000, chunki har bir xonaga 10 ta raqamdan istalgani qo‘yiladi.
Tartib muhim bo‘lmagan, lekin bir turdan bir necha marta olish mumkin bo‘lgan tanlovlar ham uchraydi: do‘kondan 4 xil muzqaymoqdan 3 tasini olish (bir xilini ikki marta olish ham mumkin). Bunday tanlovlar takrorli guruhlash deyiladi:
n turdan k ta element tanlash (takror mumkin, tartib muhim emas): C(n + k − 1, k)
Bu formulaning g‘oyasi: k ta «yulduzcha» (tanlangan narsalar) va turlarni ajratuvchi n − 1 ta «to‘siq» qatorini tuzamiz; n + k − 1 ta o‘rindan yulduzchalar uchun k tasini tanlash kifoya. Masalan, 4 xil muzqaymoqdan 3 tasi: C(6, 3) = 20 usul.
Formulani tanlash uchun ikki savolga javob bering: 1) tartib muhimmi? 2) takrorlanish mumkinmi? Shu ikki javob to‘rtta holatdan birini — Aₙᵏ, Cₙᵏ, nᵏ yoki C(n + k − 1, k) ni — belgilaydi.
To‘rt xonali PIN-kod 0–9 raqamlaridan tuziladi. Nechta kodda kamida bitta raqam takrorlanadi?