Množinové principy

Násobící princip

Uvažujme množinu M počítaných objektů. Jestliže je $M = M1 × M2$ , pak $|M| = |M_1|·|M_2|$ .

Uvažujme množinu M počítaných objektů. Pak pro $M_1 ⊆ |M|$ platí $|M| - |M - M_1|$ .

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

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ť A_i pro i = 1, 2, ... , n jsou konečné množiny, pak $|\textstyle\cup_{i=1}^n| A_i$

$|\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!}$

Neformální - jestliže n holubů vletí do k hnízd, přičemž $k < n$ , pak v některém hnízdě musí být nejméně dva holubi.

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ů