Kombinatorika

Z prvkov množiny $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 $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 $M_n$ sa nazýva $r$-variácia s opakovaním množiny $M_n$ . Počet všetkých $r$-variácií s opakovaním množiny $M_n$ budeme označovať symbolom $V'(n,r)$.

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

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

Veta. Pre počet všetkých $r$-variácií s opakovaním množiny $M_n$ platí vzťah
$V'(n,r)=n^r$
Dôkaz vety.
Dôkaz je výhodné urobiť pomocou matematickej indukcie. Pre $r=1,2$ je tvrdenie pravdivé, presvedčte sa o tom. Predpokladajme, že tvrdenie platí pre $r-1$. Teda
$V'(n,r-1)=n^{r-1}$
Všetky usporiadané $r$-tice s opakovaním množiny $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 $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
$V'(n,r)=n.V'(n,r-1)=n.n^{r-1}=n^r$.