Kombinatorika
Permutácie a variácie
Definícia.
Nech
označujeme akúkoľvek
-prvkovú množinu. Permutáciou množiny
nazývame jej bijektívne zobrazenie na seba.
Nech
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
Napríklad zobrazenie
dané predpisom:
je bijekcia množiny
na seba. Takúto permutáciu budeme symbolicky zapisovať pomocou matice
alebo jednoducho ako postupnosť
.
![f: Z_4\rightarrow Z_4 f: Z_4\rightarrow Z_4](https://lms.umb.sk/filter/tex/pix.php/55c7a6b7d686890e60321b2315e8dd67.png)
![f\left(1\right)=2,f\left(2\right)=3,\ f\left(3\right)=4,\ f\left(4\right)=1 f\left(1\right)=2,f\left(2\right)=3,\ f\left(3\right)=4,\ f\left(4\right)=1](https://lms.umb.sk/filter/tex/pix.php/c29ade1cd01335683d87c1dcb68d3deb.png)
je bijekcia množiny
![Z_4=\left\{1, 2, 3, 4\right\} Z_4=\left\{1, 2, 3, 4\right\}](https://lms.umb.sk/filter/tex/pix.php/41ccc1daa27cfe08f7e389c293a77c69.png)
![\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) \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)](https://lms.umb.sk/filter/tex/pix.php/a44c6a673749e9d52e26e6eef10c9814.png)
alebo jednoducho ako postupnosť
![\mathbf{2}\ \mathbf{3}\ \mathbf{4}\ \mathbf{1} \mathbf{2}\ \mathbf{3}\ \mathbf{4}\ \mathbf{1}](https://lms.umb.sk/filter/tex/pix.php/b474312f0c529f2f9a7a90f80b80773c.png)
Príklad.
Nájdite všetky permutácie ľubovoľnej štvorprvkovej množiny
.
Riešenie.
Nech
je bijekcia. Potom obraz prvku a môže nadobúdať štyri rôzne hodnoty:
.
Ak
, tak obraz prvku
môže nadobúdať tri rôzne hodnoty
Ak už
, tak obraz prvku
môže nadobúdať dve rôzne hodnoty atď. Schematicky to môžeme znázorniť nasledovne
Pre
sme dostali permutácie
. Podobne budeme postupovať pre
. Všetky permutácie prehľadne zapíšeme pomocou nasledujúcej tabuľky.
![](https://lms.umb.sk/pluginfile.php/387410/mod_book/chapter/9113/Sn%C3%ADmka2.PNG)
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
.
Nájdite všetky permutácie ľubovoľnej štvorprvkovej množiny
![M_4=\left\{a,b,c,d\right\} M_4=\left\{a,b,c,d\right\}](https://lms.umb.sk/filter/tex/pix.php/1ed708fe6cede687180badb7ffd7158d.png)
Riešenie.
Nech
![f: M_4\rightarrow M_4 f: M_4\rightarrow M_4](https://lms.umb.sk/filter/tex/pix.php/6e854f12fb73b415b1f8d93e0fa7e736.png)
![f\left(a\right)=a,\ f\left(a\right)=b,\ f\left(a\right)=c,\ f\left(a\right)=d f\left(a\right)=a,\ f\left(a\right)=b,\ f\left(a\right)=c,\ f\left(a\right)=d](https://lms.umb.sk/filter/tex/pix.php/45412e8735f0e4264f8299bec8fbf82c.png)
Ak
![f\left(a\right)=a f\left(a\right)=a](https://lms.umb.sk/filter/tex/pix.php/fa3490401f8abc9afd6334ff4a815ae8.png)
![b b](https://lms.umb.sk/filter/tex/pix.php/301d251459701f60c27be3229f1c4122.png)
![f\left(b\right)=b,\ f\left(b\right)=c,\ f\left(b\right)=d f\left(b\right)=b,\ f\left(b\right)=c,\ f\left(b\right)=d](https://lms.umb.sk/filter/tex/pix.php/a002d4e597eafa9042265b57f2350083.png)
Ak už
![\ f\left(b\right)=b \ f\left(b\right)=b](https://lms.umb.sk/filter/tex/pix.php/fa778fff68b91cb2c7b0eae4f8e9fa68.png)
![c c](https://lms.umb.sk/filter/tex/pix.php/2b8412805efd6ae2233444f7704e9684.png)
Pre
![f\left(a\right)=a f\left(a\right)=a](https://lms.umb.sk/filter/tex/pix.php/fa3490401f8abc9afd6334ff4a815ae8.png)
![abcd, abdc, acbd, acdb,adcb,adbc abcd, abdc, acbd, acdb,adcb,adbc](https://lms.umb.sk/filter/tex/pix.php/93b3d75cc0c0b26c0bee867d65a859da.png)
![f\left(a\right)=b, f\left(a\right)=c, f\left(a\right)=d f\left(a\right)=b, f\left(a\right)=c, f\left(a\right)=d](https://lms.umb.sk/filter/tex/pix.php/7d86ff426190389b0112796c4a0eb294.png)
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
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
Tvrdenie. Pre počet permutácií
množiny
platí vzťah ![P(M_n)=n! P(M_n)=n!](https://lms.umb.sk/filter/tex/pix.php/19737a10b615e3c90dd10c8cefda4ffa.png)
Dôkaz tohto tvrdenia môžeme ľahko urobiť ak využijeme kombinatorické pravidlo súčinu.
![P\left(M_n\right) P\left(M_n\right)](https://lms.umb.sk/filter/tex/pix.php/4df6d11d8e91349f5245d1230c515373.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![P(M_n)=n! P(M_n)=n!](https://lms.umb.sk/filter/tex/pix.php/19737a10b615e3c90dd10c8cefda4ffa.png)
Dôkaz tohto tvrdenia môžeme ľahko urobiť ak využijeme kombinatorické pravidlo súčinu.