Naučte se

Množinové principy

Násobící princip

Uvažujme množinu M počítaných objektů. Jestliže je M = M1 × M2, pak |M| = |M1|·|M2|.

Doplňkový princip

Uvažujme množinu M počítaných objektů. Pak pro M1 ⊆ |M| platí |M| - |M - M1|.

Sčítací princip

Podle sčítacího principu můžeme sečíst počty možností v disjunktních množinách.

Princip inkluze a exkluze, problém šatnářky

Průnik je docela jednoduchý operace (zmenšujeme množiny). Ale sjednocení je problematičtější, protože množina musí mít jen unikátní prvky.

Co když uvažované alternativy nejsou nutně disjunktní?

Nechť Ai pro i = 1, 2, . . . , n jsou konečné množiny, pak
$|\textstyle\cup_{i=1}^n| A_i$

 Důkaz

$ |\cup_{i=1}^n A_i| = \sum_{i=1}^{n} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - ... + (-1)^{n-1} |\textstyle\cup^n_{i=1}A_i|$

$\sum\limits_{k=1}^{n}\frac{(-1)^{k+1}n!}{k!}$

Princip holubníku

Neformální - jestliže n holubů vletí do k hnízd, přičemž k

VĚTA: Je-li N objektů umístěno do k krabiček, pak existuje krabička, která má alespoň $\lceil \frac{N}{k} \rceil$ objektů

Související