Kombinatorika
Permutácie a variácie
Variácie s opakovaním
Z prvkov množiny
je možné vytvoriť skupiny po
prvkov najvoľnejšie tak, že na každé miesto v tejto skupine umiestnime ľubovoľný prvok množiny
. Takto vzniknutým skupinám budeme hovoriť variácie s opakovaním. V závere predchádzajúcej kapitoly sme v rámci cvičenia vytvárali takéto skupiny - farebné zostavy. Farby sa mohli opakovať a zároveň záležalo na poradí.
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
Definícia. Usporiadaná
-tica prvkov množiny
sa nazýva
-variácia s opakovaním množiny
. Počet všetkých
-variácií s opakovaním množiny
budeme označovať symbolom
.
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![V'(n,r) V'(n,r)](https://lms.umb.sk/filter/tex/pix.php/af0d42e5df373c20fc46a8a8971e3caa.png)
Príklad. Utvorte všetky 3-variácie s opakovaním množiny
.
Riešenie.
Postupne vytvárajme
-variácie s opakovaním množiny
.
![M_2=\left\{1,\ 2\right\} M_2=\left\{1,\ 2\right\}](https://lms.umb.sk/filter/tex/pix.php/a1ef8409a2d5bbcb4fc96d8b24f8d093.png)
Riešenie.
Postupne vytvárajme
![1,\; 2 ,\; 3 1,\; 2 ,\; 3](https://lms.umb.sk/filter/tex/pix.php/fcc0de8ae11d4475cc0a5d28d68f7d06.png)
![M_2 M_2](https://lms.umb.sk/filter/tex/pix.php/b62752675ac6d21b4fe23b787d16c18f.png)
Veta. Pre počet všetkých
-variácií s opakovaním množiny
platí vzťah
Dôkaz vety.
Dôkaz je výhodné urobiť pomocou matematickej indukcie. Pre
je tvrdenie pravdivé, presvedčte sa o tom. Predpokladajme, že tvrdenie platí pre
. Teda
Všetky usporiadané
-tice s opakovaním množiny
možno vytvoriť z
-tíc tak, že ku každej dodáme na koniec po jednom každý prvok množiny
. Preto z každej
-tice získame
rôznych
-tíc. Využitím indukčného predpokladu dostaneme
.
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![V'(n,r)=n^r V'(n,r)=n^r](https://lms.umb.sk/filter/tex/pix.php/c62ffcfef6881b6e85cc518bc68f721d.png)
Dôkaz vety.
Dôkaz je výhodné urobiť pomocou matematickej indukcie. Pre
![r=1,2 r=1,2](https://lms.umb.sk/filter/tex/pix.php/a1f6318add3560f84d2dc63812c6cf0b.png)
![r-1 r-1](https://lms.umb.sk/filter/tex/pix.php/884b04b62c377f0efc6f93bb99df5194.png)
![V'(n,r-1)=n^{r-1} V'(n,r-1)=n^{r-1}](https://lms.umb.sk/filter/tex/pix.php/0561b2c70aedd1a7346879e6772ab4c2.png)
Všetky usporiadané
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![(r-1) (r-1)](https://lms.umb.sk/filter/tex/pix.php/467f914e5a4a7eab32d6892e81c8a564.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![(r-1) (r-1)](https://lms.umb.sk/filter/tex/pix.php/6b81f7af5482940d29b22671a83ea194.png)
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![V'(n,r)=n.V'(n,r-1)=n.n^{r-1}=n^r V'(n,r)=n.V'(n,r-1)=n.n^{r-1}=n^r](https://lms.umb.sk/filter/tex/pix.php/63202d45ae45c56752201ffa99019823.png)