Kombinatorika

Z prvkov množiny $\small  M_n$ je možné vytvoriť skupiny po $r$ prvkov najvoľnejšie tak, že na každé miesto v tejto skupine umiestnime ľubovoľný prvok množiny $\small  M_n$ . 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í.

Definícia.
Usporiadaná $r$-tica prvkov množiny $\small M_n$ sa nazýva $r$-variácia s opakovaním množiny $\small M_n$ . Počet všetkých $r$-variácií s opakovaním množiny $\small M_n$ budeme označovať symbolom $\small V'(n,r)$.

Príklad.
Utvorte všetky 3-variácie s opakovaním množiny $\small M_2=\left\{1,\ 2\right\}$.
Riešenie.
Postupne vytvárajme $1,\; 2 ,\; 3$-variácie s opakovaním množiny $\small M_2$ .

• $1$-variácie s opakovaním množiny $\small M_2$ sú dve: $1,\; 2$. Ich počet je $\small V'(2,1)=2=2^1$ .
• $2$-variácie s opakovaním množiny $\small M_2$ sú štyri: $11, \;12, \;21, \;22$. Ich počet je $\small V'(2,2)=4=2^2$
• $3$-variácii s opakovaním množiny $\small M_2$ je osem:$111,\; 112,\; 121,\; 122,\; 211,\; 212,\; 221,\; 222$. Pre ich počet platí:$\small V'(2,3)=8=2^3$ .

Veta.
Pre počet všetkých $r$-variácií s opakovaním množiny $\small M_n$ platí vzťah $\small V'(n,r)=n^r$.

Dôkaz.
Použitím matematickej indukcie. Pre $r=1,2$ je tvrdenie pravdivé, presvedčte sa o tom dosadením do vzťahu $\small V'(n,r)=n^r$. Predpokladajme, že tvrdenie platí pre $r-1$. Teda 
$\small V'(n,r-1)=n^{r-1}$
Všetky usporiadané $r$-tice s opakovaním množiny $\small M_n$ možno vytvoriť z$(r-1)$-tíc tak, že ku každej dodáme na koniec po jednom každý prvok množiny $\small M_n$ . Preto z každej $(r-1)$-tice získame $n$ rôznych $r$-tíc. Využitím indukčného predpokladu dostaneme
$\small V'(n,r)=n.V'(n,r-1)=n.n^{r-1}=n^r$.

Urobte dôkaz využitím kombinačného pravidla súčinu.