Kombinatorika

Definícia.
Nech $M_n$ označujeme akúkoľvek $n$-prvkovú množinu. Permutáciou množiny $\small  M_n$ nazývame jej bijektívne zobrazenie na seba.

Napríklad zobrazenie $\small   f: Z_4\rightarrow Z_4$ dané predpisom:
$\small   f\left(1\right)=2,f\left(2\right)=3,\ f\left(3\right)=4,\ f\left(4\right)=1$
je bijekcia množiny $\small   Z_4=\left\{1, 2, 3, 4\right\}$ na seba. Takúto permutáciu budeme symbolicky zapisovať pomocou matice
$\small   \left(\begin{matrix}1\\2\ \\\end{matrix}\begin{matrix}2\\3\\\end{matrix}\begin{matrix}3\\\ 4\ \\\end{matrix}\begin{matrix}4\\1\\\end{matrix}\right)$
alebo jednoducho ako postupnosť
$\small   \mathbf{2}\ \mathbf{3}\ \mathbf{4}\ \mathbf{1}$.

Príklad.
Nájdite všetky permutácie ľubovoľnej štvorprvkovej množiny $\small   M_4=\left\{a,b,c,d\right\}$.
Riešenie.
Nech $\small   f: M_4\rightarrow M_4$ je bijekcia. Potom obraz prvku a môže nadobúdať štyri rôzne hodnoty:
$\small  f\left(a\right)=a,\ f\left(a\right)=b,\ f\left(a\right)=c,\ f\left(a\right)=d$.
Ak $\small   f\left(a\right)=a$, tak obraz prvku $\small   b$ môže nadobúdať tri rôzne hodnoty
$\small   f\left(b\right)=b,\ f\left(b\right)=c,\ f\left(b\right)=d$
Ak už $\small   \ f\left(b\right)=b$, tak obraz prvku $\small   c$ môže nadobúdať dve rôzne hodnoty atď. Schematicky to môžeme znázorniť nasledovne

Pre $\small   f\left(a\right)=a$ sme dostali permutácie $\small   abcd, abdc, acbd, acdb,adcb,adbc$. Podobne budeme postupovať pre $\small   f\left(a\right)=b, f\left(a\right)=c, f\left(a\right)=d$. Všetky permutácie prehľadne zapíšeme pomocou nasledujúcej tabuľky.

Na základe postupu použitého v predchádzajúcom príklade môžeme dokázať tvrdenie uvedené vo vete 9, v ktorej je uvedený vzorec pre určenie počtu všetkých permutácii ľubovoľnej množiny $\small   M_n$.

Tvrdenie. 
Pre počet permutácií $\small   P\left(M_n\right)$ množiny $\small   M_n$ platí vzťah $\small   P(M_n)=n!$
Dôkaz tohto tvrdenia môžeme ľahko urobiť ak využijeme kombinatorické pravidlo súčinu.