Элементы комбинаторики

Комбинаторный принцип сложения

Пусть $A$ и $B$  дисјунктни скупови и нека је $card\left( A \right) = m$ и $card\left( B \right) = n$. Број начина да се изабере један елеменат из скупа $A$ или скупа $B$ је $m + n$.

Комбинаторни принцип приозвода

Нека су $A$ и $B$ непразни коначни скупови и нека је $card\left( A \right) = m$ и $card\left( B \right) = n$.  Број начина да се изабере један елеменат из скупа $A$ или скупа $B$ је $m \cdot n$.

Варијације $k$-те класе без понављања

Варијације $k$-те класе без понављања скупа од $n$ елемената је савака уређена  $k$-торка (не обавезно различитих) елемената тог скупа.
Нека је $\overline V \left( {n,k} \right)$ број варијација $k$-те класе са понављањем скупа од $n$ елемената. Тада је

$\overline V \left( {n,k} \right) = {n^k}.$

Пермутације без понављања

Пермутације без понављања скупа од $n$ елемената је свака уређена $n$-торка различитих елемената тог скупа.
Пермутације без понављања скупа од $n$ елемената су, у ствари, варијације $n$-те класе понављања скупа од $n$ елемената, те зато, ако је $P\left( n \right)$ број пермутација без понављања скупа од елемената, онда је

$P\left( n \right) = n!$

Број кружних пермутација без понављања скупа од $n$ елемената је $\left( {n — 1} \right)!$

Пермутације са понављаем

Пермутације са понављањем скупа је свака $A = \left\{ {{a_1},{a_2},…,{a_r}} \right\}$ је свака уређена $n$-торка елемената из $А$ у којој се сваки елемент ${a_i}$ појављује ${k_i}$ пута, $i = 1,2,3,…,r$ и где је $n = {k_1} + {k_2} + {k_3} +  \cdot  \cdot  \cdot  + {k_r}$.

Ако је $P\left( {n;{k_1},{k_2},{k_3},…,{k_r}} \right)$ број пермутација са понављањем скуп од $r$ елемената у којима се $i$-ти елемент појављује ${k_i}$ пута, при чему $i = 1,2,3,…,r$ и ${k_1} + {k_2} + {k_3} +  \cdot  \cdot  \cdot  + {k_r} = n$, онда је

$P\left( {n;{k_1},{k_2},…,{k_r}} \right) = \frac{{n!}}{{{k_1}!{k_2}!{k_3}! \cdot  \cdot  \cdot {k_r}!}}$

Комбинације без понављања

Комбинација  $k$-те класе без понављања скупа од $n$  елемената, $k \leqslant n$, је сваки његов подскуп који садржи $k$ елемената.

Ако је $C\left( {n,k} \right)$ број комбинација $k$-те класе без понављања скупа од $n$ елемената, онда је

$C\left( {n,k} \right) = \left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right).$

Комбинација са понављањем

Комбинација  $k$-те класе са понављањем скупа од $n$ елемената је свака неуређена  $k$-торка (не обавезно различитих елемената) тог скупа. Две неуређене $k$-торке су једнаке ако и ско ако садрже исте елементе са истим бројем понављања сваког елемента.

Ако је $\overline C \left( {n,k} \right)$ број комбинација  $k$-те са понављањем скупа од $n$ елемената, онда је

$\overline C \left( {n,k} \right) = \left( {\begin{array}{*{20}{c}} {n + k — 1} \\  k \end{array}} \right).$