M - Kombinatorika 02 (teorie)

I.) Pravidlo kombinatorického součinu

Počet uspořádaných k-tic, jejichž první člen lze vybral n1 způsoby, druhý člen n2 způsoby, až k-tý člen po výběru všech předcházejících členů nk způsoby je roven: n = n1 . n2 … nk

II.) Variace

K-členná variace z „n“ prvků (variace z n prvků k-té třídy) je uspořádaná k-tice, sestavená z těchto prvků tak, že každý se v ní vyskytuje nanejvýš jednou.

V (k, n) … počet všech k-členných variací z „n“ prvků

k < nebo = n

V (k, n) = n . (n – 1) . (n – 2) … (n – k +1)

III.) Permutace

Permutace je zvláštní případ variace, kde k = n. To znamená, že ze zadaných prvků postupně vybereme všechny. Každá permutace tedy odpovídá nějakému pořadí zadaných prvků: každý prvek se v pořadí musí objevit, ale žádný tam nemůže být dvakrát.

Permutace z n prvků je každá n-členná variace z těchto prvků.

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

Počet P(n) všech permutací z n prvků je: P(n) = n . (n − 1) . (n − 2) … 3 . 2 . 1

IV.) Faktoriál

Pro každé přirozené číslo n definujeme: n! = 1 . 2 . 3 … (n − 1) . n

symbol n! čteme "n faktoriál"

Počet P(n) všech permutací z n prvků můžeme pomocí faktoriálu zapsat takto: P(n) = n!

0! = 1

(n + 1)! = (n +1) . n!

V.) Vztahy mezi vedlejšími faktoriály

n! / (n + 1)!=n! /(n+1) . n!=1 / (n+1)

D = N₀

(n + 1)! - n!= (n + 1) . n! - n! = n! . (n + 1 – 1) = n! . n

D = N₀

VI.) Kombinace

K-členná kombinace z „n“ prvků (kombinace z n prvků k-té třídy) je k-prvková podmnožina

n-prvkové množiny (nezávisí na pořadí).

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.

K (k, n) = V (k, n) / P (k) = n . (n – 1) … (n – k + 1) / k!

VII.) Kombinační číslo

Kombinační číslo je symbol, který označuje počet k-členných kombinací z n prvků.

(n nad k) … kombinační číslo

(n nad k) = n! / k! . (n – k)!

K (k, n) = (n nad k)

(n nad n) = 1, n náleží N0

VIII.) Doplňková kombinace

(n nad k) = (n nad n – k); k je rovno nebo menší než n

(n nad k) + (n nad k + 1) = (n + 1 nad k + 1)