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í.
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 .
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 .
Riešenie.
Postupne vytvárajme -variácie s opakovaním množiny .
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
.
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
.