Комбинаторика

⭐ — имтиҳонда энг кўп ишлатиладиган формулалар.

Асосий қоидалар

• ⭐ Кўпайтириш қоидаси: биринчи танловни $m$, ундан кейингисини $n$ усулда қилиш мумкин бўлса, кетма-кет иккаласини $m \cdot n$ усулда қилиш мумкин. Босқичлар кўп бўлса, ҳаммаси кўпайтирилади.
  • Мисол: $5$ кўйлак, $4$ шим, $3$ жуфт поябзал: $5 \cdot 4 \cdot 3 = 60$ хил кийиниш.
• ⭐ Қўшиш қоидаси: "ёки бу, ёки у" (биргаликда бўлмайдиган) $m$ ва $n$ вариант бўлса, жами $m + n$ усул.
• ⚠️ Саволда "ва" бўлса — кўпайтиринг, "ёки" бўлса — қўшинг.

Факториал

• ⭐ $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$. Касрларни қисқартиришда катта факториални кичиги орқали ёзинг: $\dfrac{8!}{6!} = 8 \cdot 7 = 56$.

Уч асосий формула

• ⭐ Ўрин алмаштириш: $P_n = n!$. Масалан, $4$ та байроқни қаторга $4! = 24$ усулда осиш мумкин.
• ⭐ Ўринлаштириш: $A_n^k = n(n - 1)\cdots(n - k + 1)$ ($k$ та кўпайтувчи). Масалан, $7$ иштирокчидан $1$-, $2$-, $3$-ўринлар эгалари: $A_7^3 = 7 \cdot 6 \cdot 5 = 210$.
• ⭐ Гуруҳлаш (комбинация): $C_n^k = \dfrac{A_n^k}{k!}$. Масалан, $10$ кишидан $3$ кишилик гуруҳ: $C_{10}^3 = \dfrac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120$.
• Қандай ажратиш: танланганларни ўрин алмаштирсак натижа ўзгарадими? Ўзгарса (ўринлар, рақамлар, лавозимлар) — ўринлаштириш. Ўзгармаса (гуруҳ, жамоа, тўплам) — гуруҳлаш.

Гуруҳлашнинг хоссалари

• ⭐ $C_n^k = C_n^{n - k}$ (танлаш = қолдириш). $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}$ (Паскал учбурчагининг қоидаси).
• $C_n^0 + C_n^1 + \dots + C_n^n = 2^n$ ($n$ элементли тўпламнинг қисм тўпламлари сони).

Такрорланувчи ҳолатлар

• Такрорлаш мумкин бўлганда ҳар ўринда $n$ вариант: $n^k$. Масалан, $0$–$9$ рақамларидан $3$ хонали код: $10^3 = 1000$.
• Такрорланувчи элементлар билан ўрин алмаштириш: бир хил элементлар $n_1, n_2, \dots$ та бўлса

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

Масалан, "МАМА" ҳарфларидан $\dfrac{4!}{2!\,2!} = 6$ хил сўз.

• Айлана атрофида $n$ кишини ўтқазиш: $(n - 1)!$. Масалан, $5$ киши: $4! = 24$.

Фойдали усуллар

• ⭐ "Камида битта" шартида: умумий сондан "бирортаси ҳам йўқ" ҳолатни айиринг. Масалан, $6$ ўғил ва $4$ қиздан $3$ киши, камида битта қиз бўлсин: $C_{10}^3 - C_6^3 = 120 - 20 = 100$.
• Шарт қўйилганда аввал чекланган ўринни тўлдиринг. Масалан, $0, 1, 2, 3$ рақамларидан такрорсиз $3$ хонали сон: биринчи рақам $0$ бўлмайди, шунинг учун $3 \cdot 3 \cdot 2 = 18$.
• Икки гуруҳдан танлаш: ҳар гуруҳдан танланганлар сони кўпайтирилади. $4$ ўғил ва $3$ қиздан $2$ ўғил ва $2$ қиз: $C_4^2 \cdot C_3^2 = 6 \cdot 3 = 18$.

Типик хатолар

• ⚠️ Тартиб муҳим-муҳим эмаслигини аралаштириш: жамоа танлашда $A_n^k$ эмас, $C_n^k$ ишлатилади.
• ⚠️ Кўпайтириш ўрнига қўшиш (ёки аксинча).
• ⚠️ Рақамлардан сон тузишда биринчи рақамнинг $0$ бўла олмаслигини унутиш.