Комбинаторика: санап чыгуу эрежелери

Кошуу жана көбөйтүү эрежелери

Тандоону бири-бирин жокко чыгарган варианттардын бири менен жасаса болсо, варианттардын саны кошулат. Тандоо бир нече кадамдан турса, ар бир кадамдагы варианттардын саны көбөйтүлөт.

Мисалы, цифралары ар башка болгон үч орундуу сандар: биринчи цифра $9$ жол менен ($0$ болбойт), экинчиси $9$, үчүнчүсү $8$ — бардыгы $9 \cdot 9 \cdot 8 = 648$.

Орун алмаштыруулар жана айкалыштар

$n$ ар башка нерсени катарга $n! = 1 \cdot 2 \cdots n$ жол менен тизсе болот.

$n$ нерсенин ичинен тартибине карабай $k$ нерсени тандоонун саны:

$$C_n^k = \dfrac{n!}{k!\,(n - k)!}.$$

Мисалы, $15$ адамдын ар бири бири-бири менен кол алышса, кол алышуулардын саны $C_{15}^2 = 105$.

«Шарлар жана тосмолор»

$x_1 + x_2 + \cdots + x_k = n$ теңдемесинин терс эмес бүтүн чечимдеринин саны $C_{n + k - 1}^{k - 1}$. Себеби: $n$ шарды $k - 1$ тосмо менен $k$ топко бөлөбүз.

Тордогу жолдор

$m \times n$ тордо сол төмөнкү бурчтан оң жогорку бурчка оңго жана өйдө гана жүрүп барган жолдордун саны $C_{m + n}^{m}$: $m + n$ кадамдын кайсы $m$и оңго экенин тандайбыз.