Kombinatorika a pravděpodobnost

Note	Elementární kombinatorika (kombinace, permutace, variace), řešení jednoduchých kombinatorických úloh. Pravděpodobnost, podmíněná pravděpodobnost (Bayesova věta). MB101/MB201, MB103/MB203

Kombinatorika

Zabývá se počítáním prvků v množinách s nějakou strukturou.

Variace

Z množiny o $n$ prvcích vybírám $k$ prvků a záleží mi na pořadí.

V (k, n) = \frac{n !}{( n - k )!}

Variace s opakováním

Z množiny o $n$ prvcích vybírám $k$ prvků, záleží mi na jejich pořadí a mohou se opakovat.

V^{'} (k, n) = n^{k}

Permutace

Přeházím prvky v množině o $n$ prvcích. Je to speciální případ variace, kde $k = n$ .

P (n) = n!

Kombinace

Z množiny o $n$ prvcích vybírám $k$ prvků, ale nezáleží mi na jejich pořadí.

C (k, n) = (k n) = \frac{n !}{( n - k )! k !}

Kombinace s opakováním

Z množiny o $n$ prvcích vybírám $k$ prvků, nezáleží mi na jejich pořadí a mohou se opakovat.

C^{'} (k, n) = (k n + k - 1) = (n - 1 n + k - 1) = \frac{( n + k - 1 )!}{( n - 1 )! k !}

Princip oddělovačů: Vybereme $n - 1$ pozic, kam dáme oddělovač. Mějme třeba množinu ${A, B, C}$ , ze které chceme vybrat $k = 10$ prvků, pak

$[A A A ∣ B B B B B B ∣ C]$

kde $∣$ jsou oddělovače.

Pravděpodobnost

Zabývá se číselným popisem toho, jaká je šance, že je něco pravda.

Základní prostor $Ω$

Konečná množina možných jevů. Např ${1, 2, 3, 4, 5, 6}$ pro možné hody šestistěnkou.

Možný výsledek (elementární náhodný jev) $ω_{k}$

Prvek základního prostoru $Ω$ .

Náhodný jev (event) $A$

Podmnožina $A \subseteq Ω$ , která nás zajímá. Např. ,,Na šestistěnce padne sudé číslo.''.

Opačný jev $\overline{A}$ (nebo $A^{C}$ )

Jev, který nastane vždy, když $A$ nenestane. $Ω ∖ A$ . Např. opačný jev k tomu, že na šestistěnce padne sudé číslo, je ,,Na šestistěnce padne liché číslo.''.

Pravděpodobnost náhodného jevu $A$

$P (A) = \frac{∣ A ∣}{∣Ω∣}$ .

Náhodná veličina

Zobrazení z prostoru elementárních jevů do měřitelného prostoru $E$ (třeba $R$ ).

$X : Ω \to E$

Něco, co se dá u každého možného výsledku změřit.

Princip inkluze a exkluze

$P (A \cup B) = P (A) + P (B) - P (A \cap B)$

Podmínky pravděpodobnosti

$Ω$ je konečná množina.
Pokud $n \neq = m$ , pak $ω_{n}$ a $ω_{m}$ nemohou nastat najednou.
Všechny možné výsledky jsou stejně možné.

Pravděpodobností prostor

$(Ω, A, P)$ , kde

$P$ je nezáporná,
$P$ je aditivní — $A \cap B = \emptyset ⟹ P (A \cup B) = P (A) + P (B)$ ,
$P (Ω) = 1$ .

Stochastická nezávislost

Náhodné jevy $A$ a $B$ jsou stochasticky nezávislé, pokud $P (A \cap B) = P (A) \cdot P (B)$

Podmíněná pravděpodobnost

Pravděpodobnost, že nastane náhodný jev $A$ , pokud už nastal jev $B$ , kde $P (B) > 0$ .

$P (A ∣ B) = \frac{P ( A \cap B )}{P ( B )}$ .

Všimni si, že pokud jsou jevy stochasticky nezávislé, pak $P (A ∣ B) = P (A)$ .

Bayesova věta

Podmíněná pravděpodobnost souvisí s opačnou podmíněnou pravděpodobností.

P (A ∣ B) = \frac{P ( B ∣ A ) \cdot P ( A )}{P ( B )},

kde $P (B) > 0$ .