Variace (kombinatorika)

Variace k-té třídy z n prvků je každá uspořádaná k-tice vytvořená z celkového počtu n prvků, přičemž při výběru záleží na pořadí jednotlivých prvků. Rozlišujeme variace s opakováním a bez opakování. Pro výpočet hodnoty je používán faktoriál.

Variace bez opakování

Variace bez opakování je k-členná skupina utvořená z daných n prvků tak, že v nich záleží na pořadí a žádný z daných prvků se v ní neopakuje. * Počet k-členných variací z n prvků: V(k,n)=n(n-1)(n-2). +more(n-k+1) = \frac{n. }{(n-k). } pro k \leq n * například: 2členná variace ze 3 prvků a, b, c: (ab), (ba), (ac), (ca), (bc), (cb) = \frac{3. }{(3-2). }=6.

Variace s opakováním

Variace s opakováním je uspořádaná k-tice z n prvků sestavená tak, že každý se v ní vyskytuje nejvýše k-krát. Opět záleží na pořadí. +more * Počet k-členných variací s opakováním z n prvků: V'(k,n) = n^k platí i pro k * například: 2členná variace s opakováním ze 3 prvků a, b, c: (aa), (ab), (ac), (ba), (bb), (bc), (ca), (cb), (cc) = 3^2= 9.

Příklady

Příklad 1

Kolik trojciferných čísel je možné sestavit z číslic 1, 2, 3, 4, jestliže:

a) se v čísle každá cifra může vyskytovat nejvýše jednou :V(3,4)=\frac{4!}{(4-3)!}=\frac{4!}{1!} = 4 \cdot 3 \cdot 2 = 24

b) se v čísle cifry mohou opakovat :V'(3,4) = 4^3=64

Příklad 2

Kolik je možností pro obsazení 1., 2. a 3. místa v závodě s 20 účastníky? :V(3,20)=\frac{20!}{(20-3)!}=\frac{20!}{17!}=\frac{20 \cdot 19 \cdot 18 \cdot 17!}{17!}=20 \cdot 19 \cdot 18=6840

Příklad 3

Posádka lodi potřebuje k dorozumívání vytvořit 50 různých signálů. Budou jim k tomu stačit 4 různobarevné praporky. +more * jednopraporkové signály: V(1,4)=4 * dvoupraporkové signály: V(2,4)=\frac{4. }{2. }=4 \cdot 3=12 * třípraporkové signály: V(3,4)=\frac{4. }{1. }=4. =4 \cdot 3 \cdot 2=24 * čtyřpraporkové signály: V(4,4)=P(4)=4. =24 :celkem lze vytvořit: 4+12+24+24=64 signálů.

:Na vytvoření 50 signálů budou 4 různobarevné praporky stačit.

Příklad 4

Kolika způsoby můžete nastavit šestimístný číselný kód trezoru? :V'(6,10) = 10^6=1 000 000

Algoritmus

Algoritmus pro nalezení všech variací znaků (s opakováním, v jazyku Java)

public static List variaceSOpakovanim(int trida, String pouzitelneZnaky) { List list = new ArrayList((int) Math.pow(pouzitelneZnaky.length, trida)/*(1)*/);

if (trida == 0) { list. add(""); /*(2)*/ } else { List l = variaceSOpakovanim(trida - 1, pouzitelneZnaky); for (char c : pouzitelneZnaky. +moretoCharArray) { /*(3)*/ for (String s : l) { list. add(c + s); /*(4)*/ } } } return list; }.

#Počet variací s opakováním je dán jako počet použitelných prvků umocněný na třídu variace. #Variace nulté třídy je právě jedna: prázdná množina. +more #Variace s opakováním se dá vnímat jako kartézský součin množiny použitelných prvků s množinou variací ze stejných použitelných prvků, ale s třídou o jednu menší. Z toho vyplývá použití rekurze. #Přidá do výstupního (vraceného) seznamu příslušný prvek, vzniklý spojením jednoho (každého) prvku s jednou (každou) variací nižší třídy.

Literatura

Související články

Permutace * Kombinace

Kategorie:Kombinatorika