Věta: Inkluze a exkluze Nechť $A_{1}, A_{2}, \dots, A_{n}$ jsou konečné množiny. Potom

i = 1 ⋃ n A_{i} = k = 1 \sum n (- 1)^{k + 1} I \in (k { 1 , 2 , \dots , n }) \sum i \in I ⋂ A_{i}

také lze zapsat jako

i = 1 ⋃ n A_{i} = \emptyset \neq = I \subseteq {1, 2, \dots, n} \sum (- 1)^{∣ I ∣ + 1} i \in I ⋂ A_{i}

Důkaz: Hlavní otázka je kolikrát započteme prvek $x \in ⋃_{i = 0}^{n} A_{i}$ na pravé straně rovnosti. Nechť $k =$ počet $A_{i}$ ve kterých se vyskytuje $x$ . Vezmeme-li postupně $j = ∣ I ∣$ jedno po druhém, tak $j > k$ máme příspěvek $x$ nulový, ale pro $j \leq k$ máme $(j k)$ $j$ -tic obsahujících $x$ a celkem tedy přispějí $(- 1)^{j + 1} (j k)$ . Pozorování: Dle binomické věty máme $(1 - 1)^{k} = \sum_{i = 0}^{k} (i k) (- 1)^{i} = 1 + \sum_{i = 1}^{k} (i k) (- 1)^{i} = 1 - 1 = 0.$ Sečtením přes všechna $j$ máme

i = 1 \sum k (i k) (- 1)^{i + 1} = (- 1) i = 0 \sum k (i k) (- 1)^{i}

kde aplikujeme pozorování o $\sum_{i = 0}^{k} (i k) (- 1)^{i} = - 1$ a tedy

- 1 \cdot i = 0 \sum k (i k) (- 1)^{i} = (- 1) \cdot (- 1) = 1.

Problém šátnářky

Pravděpodobnostní prostor: $Ω = S_{n} := {π : {1, 2, \dots, n} \to {1, 2, \dots, n}}$ . $i$ dostal svůj kolobouk $\leftrightarrow$ $π (i) = i$ , neboli je to pevný bod Úloha: Jaká je pravděpodobnost, že náhodná permutace nemá žádný pevný bod?

P (= \overset{ˇ}{S} {π \in S_{n} ∣\forall i : π (i) \neq = i}) = \frac{∣ S ˇ ∣}{n !}

Pro spočtení pravděpodobnosti se můžeme zabývat doplňkem a sice, jaká je pravděpodobnost existence alespoň jednoho pevného bodu. Zadefinujeme $A = {π \in S_{n} : (\exists i) (π (i) = i)}$ a pomocné množiny $A_{i} = {π \in S_{n} : (π (i) = i)}$ pro všechna $i$ . Můžeme pozorovat, že $A = ⋃_{i = 0} A_{i}$ . Zároveň je vidět $\overset{ˇ}{S} = S_{n} ∖ A$ a stačí dosadit do principu inkluze a exkluze:

i = 1 ⋃ n A_{i} = k = 1 \sum n (- 1)^{k + 1} I \subseteq {1, 2, \dots, n} : I \neq = \emptyset \sum i \in I ⋂ A_{i}

Eulerova funkce

Definice Eulerova funkce $φ (n)$ značí pro přirozené $n$ počet $k \in {1, 2, \dots, n - 1}$ , nesoudělných s $n$ , tedy $NSD (k, n) = 1$ .

Počet surjekcí

Počet všech funkcí z $A$ do $B$ je $∣ B ∣^{∣ A ∣}$ ( $∣ A ∣ = n, ∣ B ∣ = k$ ) a mi chceme eliminovat ty, které nejsou na, tedy takové funkce, kde $\exists b \in B$ , které není obrazem žádného $a \in A$ . Pro každé $i \in B$ zavedeme

X_{i} = {f : A \to B ∣ i \neq \in Rng (f)} .

Takže počet surjekcí je

∣ B ∣^{∣ A ∣} - i = 1 ⋃ ∣ B ∣ X_{i} .

Ve vzorci inkluze–exkluze pro sjednocení $X_{1} \cup \dots \cup X_{k}$ platí:

X_{1} \cup \dots \cup X_{k} = m = 1 \sum k (- 1)^{m - 1} I \subseteq {1, \dots, k} ∣ I ∣ = m \sum i \in I ⋂ X_{i} .

Potřebujeme tedy spočítat:

X_{i_{1}} \cap \dots \cap X_{i_{m}} pro libovolnou mno \overset{z}{ˇ} inu I = {i_{1}, \dots, i_{m}} \subseteq B .

Podmínka $(f \in X_{i_{1}} \cap \dots \cap X_{i_{m}})$ znamená, že funkce $f$ nepoužije žádné z prvků $i_{1}, i_{2}, \dots, i_{m}$ . Tedy hodnotu $f (a)$ si ve skutečnosti vybírá jen z množiny

B ∖ {i_{1}, \dots, i_{m}},

která má $(k - m)$ prvků. Každý z $n$ prvků z $A$ může zvolit libovolný z těchto $(k - m)$ cílů, takže

X_{i_{1}} \cap \dots \cap X_{i_{m}} = (k - m)^{n} .

Z množiny $B$ o velikosti $k$ vybereme přesně $m$ prvků, které nebudou v obrazu. To lze udělat $(m k)$ způsoby.

Vložením do vzorce inkluze-exkluze za $∣ X_{i_{1}} \cap \dots \cap X_{i_{m}} ∣ = (k - m)^{n}$ a v úvahu, že existuje $(m k)$ možností, jak vybrat $m$ unikátních prvků z $B$ , dostaneme:

X_{1} \cup \dots \cup X_{k} = m = 1 \sum k (- 1)^{m - 1} (m k) (k - m)^{n} .

Proto je počet surjektivních funkcí

{surjekce f : A \to B} = k^{n} - m = 1 \sum k (- 1)^{m - 1} (m k) (k - m)^{n} .

Kde posunem a zařazením $k^{n}$ přepíše jako

m = 0 \sum k (- 1)^{m} (m k) (k - m)^{n} .

Tedy výsledná forma je:

∣ {f : A \to B ∣ f je surjekce (na)} ∣ = m = 0 \sum k (- 1)^{m} (m k) (k - m)^{n} .

Osobní stránka

Explorer

Princip inkluze a exkluze

Problém šátnářky

Eulerova funkce

Počet surjekcí

Graph View

Table of Contents

Backlinks