2024-09-26

Kombinatorik

Exempel: Mängden funktioner

$A = {1, 2, 3, 4, 5, 6}, B = {a, b, c}$

Hur många surjektiva funktioner $f : A \to B$ finns det?

Antalet funktioner $A$ till $B$ : $C = {f : A \to B}$
Antalet surjektiva funktioner $A$ till $B$ : $D$

$| C | = 3^{6}$
$| D | = | C | - (| C_{a} | + | C_{b} | + | C_{c} | - | C_{a} \cap C_{b} | - | C_{b} \cap C_{c} | - | C_{a} \cap C_{c} | + | C_{a} \cap C_{b} \cap C_{c} |)$
$= 3^{6} - 3 * 2^{6} - 3 * 1 + 0 = 540$

Generalisering

Hur många funktioner från $A$ till $B$ finns det om $| A | = n, | B | = m, m < n$

$C_{i} = {f : A \to B, ∄ x \in A där f (x) = B_{i}}$
$| D | = | C | - | ⋃_{i = 1}^{m} C_{i} |$

$| C | = m^{n}$

$| D | = m^{n} + \sum_{i = 1}^{m} (- 1)^{i} (\binom{m}{i}) (m - i)^{n}$

Formellt svar

Antalet funktioner $A \to B$ : $C$
Antalet surjektiva funktioner $A \to B$ : $D$

$n = | A |$
$m = | B |$

$m < n$

$| C | = m^{n}$

$C_{i} = {f : A \to B, ∄ x \in A där f (x) = B_{i}}$

$| D | = | C | - | ⋃_{i = 1}^{m} C_{i} |$

$| D | = m^{n} + \sum_{i = 1}^{m} (- 1)^{i} (\binom{m}{i}) (m - i)^{n}$

Test

$n = 6, m = 3$

$| D | = 3^{6} + \sum_{i = 1}^{3} (- 1)^{i} (\binom{3}{i}) (3 - i)^{6}$
$= 3^{6} - (- 1)^{1} (\binom{3}{1}) (3 - 1)^{6} + (- 1)^{2} (\binom{3}{2}) (3 - 2)^{6} + (- 1)^{3} (\binom{3}{3}) (3 - 3)^{6}$
$= 3^{6} - (\binom{3}{2}) 2^{6} + (\binom{3}{3}) 1^{6} - (\binom{3}{4}) 0^{6}$
$= 729 - 3 * 64 + 3 * 1 - 1 * 0$
$= 540$ ✔

$n = 2, m = 2$

$| D | = 2^{2} + \sum_{i = 1}^{2} (- 1)^{i} (\binom{2}{i}) (2 - i)^{2}$
$= 4 + (- 1)^{1} (\binom{2}{1}) (2 - 1)^{2} + (- 1)^{2} (\binom{2}{2}) (2 - 2)^{2}$
$= 4 - 2 (1)^{2} + 1 (0)^{2}$
$= 4 - 2 + 0$
$= 2$ ✔

Misslyckad experimentering

$| ⋃_{i = 1}^{m} C_{i} | = | ⋃_{i = 1}^{n} A_{i} | = \sum_{i = 1}^{n} | A_{i} | - \sum_{i, j; i < j} | A_{i} \cap A_{j} | + \sum_{i, j, k; i < j < k} | A_{i} \cap A_{j} \cap A_{k} | - \dots \pm \sum_{i,} \dots$
$= \sum_{i = 1}^{m} (- 1)^{(i + 1)} (m - i)^{n}$

$| D_{1} | = \sum_{i = 0}^{m} (- 1)^{i} (m - i)^{n}$
$| D_{2} | = \sum_{i = 0}^{m} (- 1)^{i} (\binom{m}{i + 1}) (m - i)^{n}$

$n = 6, m = 3$
$| D_{1} | = \sum_{i = 0}^{3} (- 1)^{i} (3 - i)^{6}$
$= (- 1)^{0} (3 - 0)^{6} + (- 1)^{1} (3 - 1)^{6} + (- 1)^{2} (3 - 2)^{6} + (- 1)^{3} (3 - 3)^{6}$
$= 3^{6} - 2^{6} + 1^{6} - 0^{6}$
$= 729 - 64 + 6 - 0 = 671$ ❌

$| D_{2} | = \sum_{i = 0}^{3} (- 1)^{i} (\binom{3}{i + 1}) (3 - i)^{6}$
$= (- 1)^{0} (\binom{3}{0 + 1}) (3 - 0)^{6} + (- 1)^{1} (\binom{3}{1 + 1}) (3 - 1)^{6} + (- 1)^{2} (\binom{3}{2 + 1}) (3 - 2)^{6} + (- 1)^{3} (\binom{3}{3 + 1}) (3 - 3)^{6}$
$= (\binom{3}{1}) 3^{6} - (\binom{3}{2}) 2^{6} + (\binom{3}{3}) 1^{6} - (\binom{3}{4}) 0^{6}$
$= 3 * 729 - 3 * 64 + 1 * 1 - 0 * 0 = 1996$ ❌

Grafteori

Vad är en graf?

En graf består av en mängd noder och en mängd kanter mellan noder.

Formellt: En graf är $G = (V, E)$

$V$ mängden noder (vertices)
$E$ mängden kanter (edges)

${x, y} \in E, x, y \in V$ är en kant mellan noderna $x$ och $y$

I denna kurs gäller:

Det finns bara en möjlig kant mellan 2 noder
En nod kan inte ha en kant med sig själv ( ${x, y} \notin E$ )

Sammanhängande graf

En graf kallas sammanhängande om det finns en väg mellan alla par av noder $u, v \in V$

Vägar

En väg mellan två noder $u, v$ är en följd av noder $v_{0}, v_{1}, \dots, v_{n}$ där:

v_{0} = u, v_{n} = v, {v_{i}, v_{i + 1}} \in E, i \in {0, 1, \dots, n}

En cykel är en väg där ingen kant upprepas som börjar och slutar i samma nod, d.v.s. $u = v$ .

En enkel väg är en väg utan upprepande noder.

Isomorfa grafer

Graferna $G, \tilde{G}$ är "samma graf" om vi kan byta "namn" på noderna för att få samma mängd av kanter.

Formell definition

$G$ och $\tilde{G}$ är isomorfa om det finns en bijektion $f : V \to \tilde{V}$ så att ${x, y} \in E ⟺ {f (x), f (y)} \in \tilde{E}$

$f$ inducerar en bijektion mellan $G$ och $\tilde{G}$ .

Metod för att se om två grafer är isomorfa

Vi har graferna $G_{1}, G_{2}$ som vi vill undersöka om de är isomorfa:

Börja med en nod $v_{0}$ i $G_{1}$ med ett unikt antal kanter.
Om det finns exakt en nod $u_{0}$ med lika många kanter i $G_{2}$ så måsta dessa vara samma nod. D.v.s. $f (v_{0}) = u_{0}$

Delgrafer

Låt $G = (V, E), \tilde{G} = (\tilde{V}, \tilde{E})$ vara två grafer.

$\tilde{G}$ är en delgraf till $G$ om $\tilde{V} \subseteq V$ och $\tilde{E} \subseteq E$
$\tilde{G}$ är en inducerad delgraf till $G$ om $\tilde{G}$ är en delgraf och om $x, y \in \tilde{V} \land {x, y} \in E$ gäller ${x, y} \in \tilde{E}$ . D.v.s. att vi inte tar bort fler kanter än nödvändigt.