Kombinatorika

Obsah kombinatoriky

Kombinatorika ve středoškolské matematice se zabývá vytvářením skupin o určitém počtu prvků k vybíraných z množiny o n prvcích a určováním počtu těchto skupin. Při tomto vyhledávání skupin prvků jde o tyto zásadní odlišnosti:

- ve skupině prvků na jejich pořadí buď záleží, nebo nezáleží,

- ve skupině prvků se prvky opakovat buď mohou, nebo nemohou

Základní kombinatorická pravidla

Kombinatorické pravidlo součinu: Počet všech uspořádaných k-tic, jejichž první člen lze vybrat n₁ způsoby, druhý člen
 n₂ způsoby atd. až k-tý člen po výběru všech předcházejících členů n_k způsoby, je roven  n₁.n₂. ... n_k .

Příklad:

Z města A do města B vedou čtyři cesty, z města B do města C vedou dvě cesty. Určete počet cest, které vedou z A do C a procházejí přitom městem B.

Řešení:

Pro cestu z A do B můžeme zvolit jednu z a = 4 cest. Pro každou z těchto cest existují b = 2 možnosti pokračování do C. Pro počet cest p z  A do C tedy platí:

p = a.b, a tedy p = 4.2 = 8.

Kombinatorické pravidlo součtu: Jsou-li A₁, A₂, ....., A_n konečné množiny, které mají po řadě p₁, p₂, ... , p_n prvků, a jsou-li každé dvě množiny disjunktní, pak počet prvků množiny A₁A₂.... A_n  je roven p₁ + p₂ + ... + p_n.

Příklad:

Urči počet všech dvojciferných čísel, v jejichž dekadickém zápisu se každá číslice vyskytuje nejvýše jednou.

Řešení:

Užijeme pravidla o součtu. Všechna dvojciferná čísla rozdělíme na dvě disjunktní množiny tak, že v první jsou dvojciferná čísla s různými číslicemi a ve druhé dvojciferná čísla se stejnými číslicemi. Je zřejmé, že všech dvojciferných čísel je 90, dvojciferných čísel s číslicemi stejnými je 9 (11, 22, 33, …99). Bude-li p počet všech dvojciferných čísel s různými číslicemi, platí p + 9 = 90, tedy p = 81.

Při použití pravidla o součinu uvažujeme takto: Na místě desítek může stát libovolná z devíti číslic 1, 2, …, 9 ( na tomto místě nesmí být 0). Na místě jednotek může stát nula a jakákoliv číslice, která již nebyla umístěna na místo desítek. Máme tedy opět devět možností. Platí tedy: p = 9.9 = 81.

Množiny A, B nazýváme disjunktní, je-li AB = .

Při výpočtech kombinatorických úloh se s výhodou používá n!. Tento symbol nazýváme n faktoriál a je definován takto:

n! = n.(n – 1).(n – 2). . . 5.4.3.2.1

Příklad:

Na vrchol hory vedou čtyři turistické trasy a lanovka. Určete počet způsobů, kterými je možno se dostat

a) na vrchol a zpět;

b) na vrchol a zpět tak, aby zpáteční cesta byla jiná než cesta na vrchol;

c) na vrchol a zpět tak, aby aspoň jednou byla použita lanovka;

d) na vrchol a zpět tak, aby lanovka byla použita právě jednou.

Řešení:

a) 5.5 = 25, b) 5.4 = 4.5 = 20, c) 1.4 + 4.1 +1.1 = 9, d) 1.4 + 4.1 = 8

Variace bez opakování

Příklad:

Mějme dáno n různých prvků a přirozené číslo . Dokažte, že pro počet všech k - členných variací z n prvků V (k,n)  (variací k-té třídy z n prvků) platí:

V (k,n) = n.(n-1).(n-2)......n-k+1.

Jestliže vybíráme 1. člen  k - tice, pak máme  n  možností výběru

                          2. člen                                n-1

                          3. člen                                n-2

                        ..................................................

                       k-1. člen                               n - (k-1)

                          k. člen                               n - (k-1) = n - k + 1

Podle pravidla součinu je počet těchto uspořádaných k-tic roven součinu  n.(n-1).(n-2)......n-k+1.

k-členná variace z n prvků je uspořádaná k-tice sestavená z těchto prvků tak, že každý prvek se v ní vyskytuje nejvýše jednou (na pořadí prvků v k-tici tedy záleží).

Pro výpočet počtu variací k-té třídy z n prvků můžeme odvodit vztah:

V(k,n) = n.(n-1).(n-2)......(n-k+1) = 

nebo

Permutace bez opakování

Permutace z n prvků je uspořádaná n-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje pouze jednou.

Počet těchto permutací se určí jako:

P(n) = V(n,n) = n.(n-1).(n-2).........(n-n+1)

nebo

P(n) = n.(n-1).(n-2)...........1 = n!

Kombinace bez opakování

Kombinace k-té třídy z n prvků je každá k-prvková podmnožina množiny určené těmito n prvky.

Pro stručnější zápisy kombinatorických úloh byl zaveden symbol , který čteme „n nad k“, nazýváme kombinační číslo a je definován takto:

 pro

Vlastnosti kombinačních čísel

Pascalův trojúhelník - ilustruje vlastnosti kombinačních čísel

1

1           1

1             2            1

1             3                3            1

      …..…….………………………

Shodná čísla v každém řádku jsou umístěna souměrně vzhledem k ose souměrnosti tohoto trojúhelníku.

Součet libovolných dvou čísel je roven číslu, které se nachází v řádku pod nimi.

Dále platí:

Binomická věta

Pro všechna čísla a,b a každé přirozené číslo n je

Jednotlivé sčítance v tomto binomickém rozvoji  výrazu (a+b)ⁿ nazýváme členy binomického rozvoje. Pro každý k-tý člen platí:

.

 Kombinační čísla  se nazývají binomické koeficienty. Tyto koeficienty tvoří n-tý řádek Pascalova trojúhelníku.

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. Počet všech k-členných variací s opakováním z n prvků označujeme . Platí:

.

Permutace s opakováním

k-členná permutace 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 alespoň jednou. Počet všech permutací s opakováním z n prvků, v nichž se jednotlivé prvky opakují k₁ krát, k₂ krát, … , k_n krát, se označuje  P´(k₁,  k₂, ... , k_n).

Platí:

Kombinace s opakováním

k-členná kombinace s opakováním z n prvků je neuspořádaná k-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje nejvýše k-krát. Počet všech k-členných kombinací s opakováním se označuje C´(k, n).

Platí: