Variace, permutace, kombinace

7.

Variace, permutace, kombinace

Kombinatorika – zabývá se vlastnostmi konečných množin

Kombinační pravidlo součtu – Jsou-li A1, A2,..., An konečné množiny, které mají po řadě p1, p2, ...., pn prvků, a jsou-li každé dvě disjunktní, pak počet prvků množiny A1∪A2∪... ∪An je roven p1+p2+...+pn.

Kombinační pravidlo součinu – Počet všech uspořádaných k-tic, jejichž první člen lze vybrat n1 způsoby, druhý člen po výběru prvního členu n2 způsoby atd.., až k-tý člen po výběru všech předcházejících členů nk způsoby, je roven n1.n2.....nk.

Př. Určete počet všech trojcigerných přirozených čísel, v jejichž dekadickém zápisu se každá číslice vyskytuje nejvýše jednou.

n1=9 č. (1,2,3,4,5,6,7,8,9) n1.n2.n3=9.9.8=648 možností

n2=9 č. (0,1,2,...)

n3=8 č.

VARIACE

Variace k-té třídy z n prvků bez opakování dané základní n-prvkové množiny je každá uspořádaná k-tice sestavená z těchto prvků tak, že záleží na pořadí prvků (a prvky se neopakují).

0!=1 1!=1 2!=2.1 3!=3.2.1 atd. n!=n(n-1)!=n(n-1)(n-2)!=n(n-1)(n-2)(n-3)!=...

Př. Výbor sportovního klubu tvoří šest mužů a čtyři ženy. Určete:

a) kolika způsoby z nich lze vybrat předsedu, místopředsedu, jednatele a hospodáře.

V(4,10)=

b) kolika způsoby z nich lze vybrat funkcionáře tak, aby ve funkci předsedy byl muž a ve funkci místopředsedy žena nebo obráceně.

předseda muž: 6

místopředseda žena: 4 6.4.8.7=1344 a obráceně .2=2688

jednatel: 8

hospodář: 7

c) kolika způsoby z nich lze vybrat funkcionáře tak, aby právě jedním z nich byla žena.

P – 4 P – 6 P – 6 P – 6

M – 6 M – 4 M – 5 M – 5 - žena

J – 5 J – 5 J – 4 J – 4

H – 4 H – 4 H – 4 H – 4

4.6.5.4 + 480 + 480 + 480 = 1920

PERMUTACE

Variace n-té třídy z n prvků, pokud n=k. Uspořádaná n-tice sestavená z prvků tak, že každý se v ní vyskytuje právě jednou.

Př. Určete, kolika způsoby se v šestimístné lavici může posadit šest hochů, jestliže:

a) dva chtějí sedět vedle sebe

2P (5)=5!=120

b) dva chtějí sedět vedle sebe a třetí chce sedět na kraji

2P (4)=4!= 24

KOMBINACE

K-členná kombinace z n prvků je neuspořádaná k-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje nejvýše jednou a na pořadí prvků nezáleží. Platí pro všechna nezáporná čísla, kde k≤ n

Př. Určete kolika způsoby je možno ze dvaceti osob vybrat deset, požadujeme-li, aby mezi vybranými:

a) nebyl pan A -> K(10,19)=

b) nebyli zároveň pánové A,B

c) byl alespoň jeden z pánů A,B k1(9,18); k2(8,18) k1+k2=

VARIACE S OPAKOVÁNÍM

K-členná variace s opakováním z n prvků je uspořádaná k-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje nejvýše k-krát.

Př. Kufřík má heslový zámek, který se otevře, když na každém z pěti kotoučů nastavíme správnou číslici; těchto číslic je na každém kotouči devět. Určete největší možný počet pokusů, které je nutno provést, chceme-li kufřík otevřít, jestliže jsme zapomněli heslo.