Kombinatorika

⭐ — imtihonda eng ko'p ishlatiladigan formulalar.

Asosiy qoidalar

• ⭐ Ko'paytirish qoidasi: birinchi tanlovni $m$, undan keyingisini $n$ usulda qilish mumkin bo'lsa, ketma-ket ikkalasini $m \cdot n$ usulda qilish mumkin. Bosqichlar ko'p bo'lsa, hammasi ko'paytiriladi.
  • Misol: $5$ ko'ylak, $4$ shim, $3$ juft poyabzal: $5 \cdot 4 \cdot 3 = 60$ xil kiyinish.
• ⭐ Qo'shish qoidasi: "yoki bu, yoki u" (birgalikda bo'lmaydigan) $m$ va $n$ variant bo'lsa, jami $m + n$ usul.
• ⚠️ Savolda "va" bo'lsa — ko'paytiring, "yoki" bo'lsa — qo'shing.

Faktorial

• ⭐ $n! = 1 \cdot 2 \cdot 3 \cdots n$, $\quad 0! = 1$, $\quad 1! = 1$.
• $3! = 6$, $\; 4! = 24$, $\; 5! = 120$, $\; 6! = 720$, $\; 7! = 5\,040$.
• $\dfrac{n!}{(n - 1)!} = n$. Kasrlarni qisqartirishda katta faktorialni kichigi orqali yozing: $\dfrac{8!}{6!} = 8 \cdot 7 = 56$.

Uch asosiy formula

• ⭐ O'rin almashtirish: $P_n = n!$. Masalan, $4$ ta bayroqni qatorga $4! = 24$ usulda osish mumkin.
• ⭐ O'rinlashtirish: $A_n^k = n(n - 1)\cdots(n - k + 1)$ ($k$ ta ko'paytuvchi). Masalan, $7$ ishtirokchidan $1$-, $2$-, $3$-o'rinlar egalari: $A_7^3 = 7 \cdot 6 \cdot 5 = 210$.
• ⭐ Guruhlash (kombinatsiya): $C_n^k = \dfrac{A_n^k}{k!}$. Masalan, $10$ kishidan $3$ kishilik guruh: $C_{10}^3 = \dfrac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120$.
• Qanday ajratish: tanlanganlarni o'rin almashtirsak natija o'zgaradimi? O'zgarsa (o'rinlar, raqamlar, lavozimlar) — o'rinlashtirish. O'zgarmasa (guruh, jamoa, to'plam) — guruhlash.

Guruhlashning xossalari

• ⭐ $C_n^k = C_n^{n - k}$ (tanlash = qoldirish). $C_{9}^{7} = C_9^2 = 36$.
• $C_n^0 = C_n^n = 1$, $\quad C_n^1 = n$.
• $C_n^k + C_n^{k + 1} = C_{n + 1}^{k + 1}$ (Paskal uchburchagining qoidasi).
• $C_n^0 + C_n^1 + \dots + C_n^n = 2^n$ ($n$ elementli to'plamning qism to'plamlari soni).

Takrorlanuvchi holatlar

• Takrorlash mumkin bo'lganda har o'rinda $n$ variant: $n^k$. Masalan, $0$–$9$ raqamlaridan $3$ xonali kod: $10^3 = 1000$.
• Takrorlanuvchi elementlar bilan o'rin almashtirish: bir xil elementlar $n_1, n_2, \dots$ ta bo'lsa

$\frac{n!}{n_1!\; n_2!\cdots}$

Masalan, "MAMA" harflaridan $\dfrac{4!}{2!\,2!} = 6$ xil so'z.

• Aylana atrofida $n$ kishini o'tqazish: $(n - 1)!$. Masalan, $5$ kishi: $4! = 24$.

Foydali usullar

• ⭐ "Kamida bitta" shartida: umumiy sondan "birortasi ham yo'q" holatni ayiring. Masalan, $6$ o'g'il va $4$ qizdan $3$ kishi, kamida bitta qiz bo'lsin: $C_{10}^3 - C_6^3 = 120 - 20 = 100$.
• Shart qo'yilganda avval cheklangan o'rinni to'ldiring. Masalan, $0, 1, 2, 3$ raqamlaridan takrorsiz $3$ xonali son: birinchi raqam $0$ bo'lmaydi, shuning uchun $3 \cdot 3 \cdot 2 = 18$.
• Ikki guruhdan tanlash: har guruhdan tanlanganlar soni ko'paytiriladi. $4$ o'g'il va $3$ qizdan $2$ o'g'il va $2$ qiz: $C_4^2 \cdot C_3^2 = 6 \cdot 3 = 18$.

Tipik xatolar

• ⚠️ Tartib muhim-muhim emasligini aralashtirish: jamoa tanlashda $A_n^k$ emas, $C_n^k$ ishlatiladi.
• ⚠️ Ko'paytirish o'rniga qo'shish (yoki aksincha).
• ⚠️ Raqamlardan son tuzishda birinchi raqamning $0$ bo'la olmasligini unutish.