Елементи комбинаторике
Комбинаторни принцип суме
Нека су $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).$