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
.
Usporiadaná
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![\small M_n \small M_n](https://lms.umb.sk/filter/tex/pix.php/00cee01a69aebc07ff0ee38576f3a70c.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![\small M_n \small M_n](https://lms.umb.sk/filter/tex/pix.php/00cee01a69aebc07ff0ee38576f3a70c.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![\small M_n \small M_n](https://lms.umb.sk/filter/tex/pix.php/00cee01a69aebc07ff0ee38576f3a70c.png)
![\small V'(n,r) \small V'(n,r)](https://lms.umb.sk/filter/tex/pix.php/29f26a8001d993c3a7d2d3bb59f56e19.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
.
Utvorte všetky 3-variácie s opakovaním množiny
![\small M_2=\left\{1,\ 2\right\} \small M_2=\left\{1,\ 2\right\}](https://lms.umb.sk/filter/tex/pix.php/4251a8bc2018a7218f49dac9aa6e0cf1.png)
Riešenie.
Postupne vytvárajme
![1,\; 2 ,\; 3 1,\; 2 ,\; 3](https://lms.umb.sk/filter/tex/pix.php/fcc0de8ae11d4475cc0a5d28d68f7d06.png)
![\small M_2 \small M_2](https://lms.umb.sk/filter/tex/pix.php/90dc18adf304afaa42381e6f163781c7.png)
Veta.
Pre počet všetkých
-variácií s opakovaním množiny
platí vzťah
Dôkaz.
Použitím 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
.
Pre počet všetkých
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![\small M_n \small M_n](https://lms.umb.sk/filter/tex/pix.php/00cee01a69aebc07ff0ee38576f3a70c.png)
![\small V'(n,r)=n^r \small V'(n,r)=n^r](https://lms.umb.sk/filter/tex/pix.php/99d96b424546882851abf8ac89eec551.png)
Dôkaz.
Použitím 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)
![\small V'(n,r-1)=n^{r-1} \small V'(n,r-1)=n^{r-1}](https://lms.umb.sk/filter/tex/pix.php/361d8c9ecd3a4418b5c84a4094cbde02.png)
Všetky usporiadané
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![\small M_n \small M_n](https://lms.umb.sk/filter/tex/pix.php/bc20dea0783de7178216591827290b39.png)
![(r-1) (r-1)](https://lms.umb.sk/filter/tex/pix.php/467f914e5a4a7eab32d6892e81c8a564.png)
![\small M_n \small M_n](https://lms.umb.sk/filter/tex/pix.php/bc20dea0783de7178216591827290b39.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)
![\small V'(n,r)=n.V'(n,r-1)=n.n^{r-1}=n^r \small V'(n,r)=n.V'(n,r-1)=n.n^{r-1}=n^r](https://lms.umb.sk/filter/tex/pix.php/d90bd72f140a98af270c9d705c580616.png)
Urobte dôkaz využitím kombinačného pravidla súčinu.