# Matematyka Dyskretna - notatki
###### tags: `notatki` `mdl20`

****
### Symbol Newtona
$\binom{n}{k} = \frac{n!}{k! \cdot (n-k)!}$

Niech $n, k \in \mathbb{N}, 0 \leq k \leq n$. Wówczas:

$\binom{n}{k} = \binom{n}{n-k}$
$\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$

Dla $n \in \mathbb{N}$ zachodzi:
$(x+y)^n = \sum_{i=0}^{n}\binom{n}{i}x^{i}y^{n-i}$

****
### Liczby Catalana (problem nawiasowania)
$\begin{cases}
c_0 = 0 \\
c_n = \sum_{i=1}^{n}c_{i-1}c_{n-i}
\end{cases}$

****
### Zbiory
Niech $A$ i $B$ będą skończonymi zbiorami o odpowiednio $n$ i $m$ elementach.

- Liczba funkcji ze zbioru $A$ w zbiór $B$: $n^m$
- Liczba funkcji **różnowartościowych** za zbioru $A$ w zbiór $B$: $\frac{n!}{(n-m)!}$
- Liczba podzbiorów zbioru $A$: $2^n$
- Liczba permutacji zbioru $A$: $n!$
- Liczba $k$-elementowych podzbiorów zbioru $A$: $\binom{n}{k}$

****
### Anihilatory


****
### Funkcje tworzące

$A(x) = a_0 + a_1x + a_2x^2 + ... = \sum_{i = 0}^\infty a_ix^i$

#### Operacje

**Mnożenie przez skalar**

$\sum_{i=0}^\infty \alpha \cdot a_i x^i= \alpha \cdot \sum_{i=0}^\infty a_i x^i = \alpha \cdot A(x)$

**Przesunięcie w prawo**

idea:
{$a_0, a_1, a_2, ...$} $\to$ {$0, 0, 0, a_0, a_1, a_2, ...$}
przesuwamy o $t$ miejsc czyli dodajemy $t$ zer na początek

$A'(x) = 0 + 0\cdot x + 0\cdot x^2 + ... + 0\cdot x^{t-1} + a_0x^t + a_1x^{t+1} + a_2x^{t+2} + ...$
$= x^t(a_0 + a_1x + a_2x^2 + ...)$
$= x^tA(x)$

**Przesunięcie w lewo**

idea:
{$a_0, a_1, a_2, ...$} $\to$ {$a_t, a_{t+1}, a_{t+2}, ...$}
przesuwamy o $t$ miejsc czyli tracimy $t$ pierwszych wyrazów

$A'(x) = a_t + a_{t+1}x + a_{t+2}x^2 + ...$
$= \frac{A(x) - (a_0 + a_1x + ... + a_{t-1}x^{t-1})}{x^t}$
$= \sum_{i = 0}^\infty a_{i+t}x^i$

**Różniczkowanie**

$A'(x) = (a_0 + a_1x + a_2x^2 + a_3x^3+ ...)'$
$= a_1 + 2a_2x + 3a_3x^2 + 4a_4x^3 + ...$
$=\sum_{i=0}^\infty (i+1)a_{i+1}x^i$

funkcja tworząca ciągu:
{$a_1, 2a_2, 3a_3, ...$}

**Całkowanie**

$\int_0^xA(t)dt = \int_0^x(a_0 + a_1t + a_2t^2 + a_3t^3 + ...)dt$
$= 0 + a_0x + \frac{a_1}{2}x^2 + \frac{a_2}{3}x^3 + \frac{a_2}{4}x^4 + ...$
$= \sum_{i=0}^\infty \frac{a_{i-1}}{i}x^i$

funkcja tworząca ciągu:
{$0, a_0, \frac{a_1}{2}, \frac{a_2}{3}, ...$}

**Operacje na zmiennej x**

$A(\alpha \cdot x) = a_0 + a_1 \alpha \cdot x + a_2 \alpha^2 \cdot x^2 + a_3 \alpha^3 \cdot x^3 + ...$

funkcja tworząca ciągu:
{$a_0, \alpha a_1, \alpha^2 a_2, ...$}

*przykład1:*
$A(x^2) = a_0 + a_1x^2 + a_2x^4 + a_3 x^6 + ...$
dostajemy:
{$a_0, 0, a_1, 0, a_2, 0, a_3, 0,...$}

*przykład2:*
$A(x^3) = a_0 + a_1x^3 + a_2x^6 + a_3 x^9 + ...$
dostajemy:
{$a_0, 0, 0, a_1, 0, 0, a_2, 0, 0, a_3, 0, 0,...$}

**Sumowanie**

$A(x)$ {$a_n$}
$B(x)$ {$b_n$}

$A(x) + B(x) = \sum_{i = 0}^\infty a_ix^i +\sum_{i = 0}^\infty b_ix^i = \sum_{i = 0}^\infty (a_i + b_i)x^i$

funkcja tworząca ciągu:
{$a_0 + b_0, a_1 + b_1, ...$}

**Mnożenie**

$A(x)$ {$a_n$}
$B(x)$ {$b_n$}

$A(x) \cdot B(x) = a_0(b_0 + b_1x + b_2x^2 + ...) + a_1(b_0 + b_1x + b_2x^2 + ...)x + a_2(b_0 + b_1x + b_2x^2 + ...)x^2 + ...$
$=a_0b_0 + (a_0b_1 + a_1b_0)x + (a_0b_2 + a_1b_1 + a_2b_0)x^2 + ...$
$=\sum_{k=0}^\infty[\sum_{i=0}^k a_ib_{k-i}]x^k$

jest funkcją tworzącą ciągu:
{$a_0b_0, a_1b_0 + a_0b_1, a_0b_2 + a_1b_1 + a_2b_0, ...$}

**Różnica**

$(1-x)A(x) = (1-x)a_0 + (1-x)a_1x + (1-x)a_2x^2 + ...$
$= a_0 -a_0x + a_1x - a_1x^2 + a_2x^2 - a_2x^3 + ...$
$= a_0 + (a_1 - a_0)x + (a_2 - a_1)x^2 + ...$
$= a_0 + \sum_{i=0}^\infty (a_i - a_{i-1}) x^i$

jest funkcją tworzącą ciągu:
{$a_0, a_1-a_0, a_2-a_1, ...$}

**Suma częściowa**

$\frac{A(x)}{(1-x)} = \sum_{i=0}^\infty [\sum_{k=0}^i a^k]x^i$

jest funkcją tworzącą ciągu:

{$a_0, a_0 + a_1, a_0 + a_1+a_2, ...$}
dowód: https://proofwiki.org/wiki/Generating_Function_for_Sequence_of_Partial_Sums_of_Series

**Kompozycja**

$A(B(x)) = a_0 + a_1(b_0 + b_1x + b_2x^2 + ...) + a_2(b_0 + b_1x + b_2x^2 + ...)^2 + a_3(b_0 + b_1x + b_2x^2 + ...)^3 + ...$
$= (a_0 + a_1b_0 + a_2b_0^2 + a_3b_0^3 + ...) + ...$

**Tabela przydatnych funkcji tworzących:**


****
### Grafy
#### Definicje
**Graf** $G$ to para zbiorów $(V, E)$, gdzie $E = \{\{u,v\}: u, v \in V\}$. $V$ to zbiór wierzchołów, $E$ to zbiór krawędzi.

Graf $G$ jest **prosty** jeżeli nie zawiera pętli ani krawędzi równoległych.

Krawędź $e$ jest **incydentna** do wierzchołka $v$, jeżeli jednym z jej końców jest $v$. Najwyższy stopień wierzchołka w $G$ oznaczamy jako $\Delta(G)$.

**Stopień** wierzchołka $v$, oznaczany jako $deg(v)$ równy jest liczbie krawędzi incydentnych do $v$.

$\sum_{v \in V} deg(v) = 2|E|$

**Marszruta** o długości $k$ to ciąg $\{v_0, v_1, \dots, v_k\}$ taki, że $\{v_i, v_{i+1}\} \in E$ dla $0 \leq i \lt k$

**Droga** to marszruta, w której krawędzie się nie powtarzają.

**Ścieżka** to marszruta, w której wierzchołki się nie powtzarzają.

**Cykl** to ścieżka, w której pierwszy i ostatni wierzchołek jest taki sam.

Graf $G=(V,E)$ jest **acykliczny**, jeśli nie zawiera żadnego cyklu.

Graf $G=(V,E)$ jest **spójny** jeżeli dla dowolnych wierzchołków $u, v \in V$ istnieje ścieżka pomiędzy nimi.

**Podgrafem** grafu $G=(V,E)$ jest dowolny graf $H=(V',E')$ taki, że $V' \subseteq V$ oraz $E' \subseteq E$.

Podgraf $H$ jest **właściwy**, jeśli $G \neq H$.

**Spójna składowa** grafu $G$ to dowolny podgraf spójny $H=(V_0,E_0)$ grafu $G$, który jest maksymalny ze względu na zawieranie tzn. taki, że nie istnieje podgraf spójny $H_0$, którego podgrafem właściwym jest $H$.

**Most** to krawędź, której usunięcie zwiększy liczbę spójnych składowych grafu.

Graf $G=(V,E)$ jest **dwudzielny** wtedy i tylko wtedy, gdy istnieje podział zbioru wierzchołków $V$ na zbiory $A$ i $B$ taki, że $\forall_{e \in E}$ jeden koniec $e$ należy do $A$, a drugi do $B$.

**Las** to acykliczny graf.

**Drzewo** to acykliczny graf spójny.

**Liść** to wierzchołek drzewa, którego stopień wynosi 1.

Niech $G=(V,E)$ będzie grafem spójnym. **Drzewo rozpinające** grafu $G$ to podgraf $T=(V,E_0)$, który jest drzewem. $T$ zawiera wszystkie wierzchołki $G$.

Niech $G=(V,E)$ będzie grafem niekoniecznie spójnym. **Las rozpinający** grafu $G$ to podgraf $F=(V,E_0)$, który jest lasem, którego liczba spójnych skłądowych jest taka sama jak liczba spójnych składowych $G$.

**Minimalne drzewo rozpinające** (MST) grafu $G$ to drzewo rozpinające $G$ o minimalnej wadze.

Niech $G=(V,E)$ będzie grafem spójnym. **Skojarzenie** grafu $G$ to dowolny podzbiór krawędzi $M \subseteq E$ taki, że żadne dwie krawędzie z $M$ nie mają wspólnego końca.

Ścieżka $P$ w grafie $G$ jest **alternująca** (względem $M$) jeśli krawędzie na $P$ na przemian należą i nie należą do $M$.

Ścieżka $P$ w grafie $G$ jest **powiększająca** (względem $M$), jeśli jest alternująca (wzgl. $M$) i jej końce są nieskojarzone (w $M$).

**Cykl alternujący** $C$ w grafie $G$ (względem $M$) to taki cykl, którego krawędzie na przemian należą i nie należą do $M$.

**Droga Eulera** $G$ to droga, która zawiera każdą krawędź $e \in E$.

**Cykl Eulera** grafu $G$ to droga zamknięta (wierzchołek startowy jest taki sam jak końcowy, wierzchołki mogą się powtarzać), która zawiera każdą krawędź $e \in E$.

**Ścieżka Hamiltona** $G$ to ścieżka (wierzchołki się nie powtarzają), która zawiera każdy wierzchołek $v \in V$.

**Cykl Hamiltona** grafu $G$ to cykl (wierzchołki się nie powtarzają), który zawiera każdy wierzchołek $v \in V$.

**Liczba chromatyczna** ($\chi(G)$) $G$ to najmniejsza liczba kolorów, jaką można pokolorować graf $G$.

Graf $G$ jest **planarny**, gdy da się go narysować na płaszczyźnie w taki sposób, by żadne dwie krawędzie się nie przecinały.

#### Lematy i twierdzenia
Jeżeli dla $G=(V,E),\ |V|=n$ zachodzi:
- $G$ jest spójny i acykliczny
- $G$ jest spójny i $|E|=n-1$
- $G$ jest acykliczny i $|E|=n-1$
- $\forall_{u,v \in V}$ istnieje dokładnie jedna ścieżka pomiędzy $u$ i $v$

To $G$ jest drzewem. Powyższe stwierdzenia są równoważne.

Graf jest dwudzielny wtedy i tylko wtedy, gdy nie zawiera cyklu o nieparzystej dlugości.

Każda zamknięta marszruta o nieparzystej długości zawiera cykl nieparzystej długości.

Niech $G$ będzie grafem prostym, w którym każdy wierzchołek ma stopień przynajmniej $k$. Wówczas G zawiera scieżkę o długości $k$. Jeśli $k \geq 2$, to $G$ zawiera cykl o długości przynajmniej $k+1$.

Skojarzenie $M$ grafu $G$ jest największe wtety i tylko wtedy, gdy $G$ nie zawiera ścieżki powiększającej względem $M$.

Graf dwudzielny $G=(A \cup B, E)$ zawiera skojarzenie doskonałe wtedy i tylko wtedy, gdy spełniony jest w nim warunek Halla: dla każdego $A' \subseteq A$ zachodzi $|N(A')| \geq |A'|$ oraz dla każdego $B' \subseteq B$ zachodzi $|N(B')| \geq |B'|$, gdzie $N(W)$ oznacza zbiór sąsiadów $W$.

Spójny graf $G$ posiada drogę Eulera wtw, gdy zawiera $0$ lub $2$ wierzchołki o stopniu nieparzystym. Spójny graf $G$ posiada cykl Eulera wtw, gdy wszystkie jego wierzchołki mają stopień parzysty.

Twierdzenie Diraca:
Jeśli $G=(V,E)$ jest grafem prostym o co najmniej trzech wierzchołkach i minimalnym stopniu wierzchołka $deg(v) \geq \frac{|V|}{2}$, to $G$ zawiera cykl Hamiltona.

Twierdzenie Ore’a:
Jeśli $G=(V,E)$ jest grafem prostym o co najmniej trzech wierzchołkach i takim, że dla każdych dwóch wierzchołków $u$ i $v$ niepołączonych krawędzią zachodzi $deg(u) + deg(v ) \geq |V|$, to $G$ zawiera cykl Hamiltona.

Wzór Eulera:
Niech $G$ będzie spójnym grafem planarnym (niekoniecznie prostym) o $n$ wierzchołkach, $m$ krawędziach i $f$ ścianach. Wówczas $n−m+f=2$.

Niech $G$ będzie prostym grafem planarnym o $n \geq 3$ wierzchołkach. Wówczas liczba krawędzi $m$ tego grafu nie przekracza $3n − 6$. Jeśli dodatkowo, $G$ nie zawiera żadnego trójkąta, to $m \leq 2n-4$.

Twierdzenie Heawooda:
Każdy graf planarny jest $5$-kolorowalny.

$\chi(G) \leq \Delta(G)+1$. Ponadto jeżeli G nie jest kliką ani nieparzystym cyklem, to $\chi(G) \leq \Delta(G)$

****
### Przydatne algorytmy

#### BFS

#### DFS

#### Badanie spójności grafu

#### Euklides

#### Algorytm Dijkstry

****
### Przydatne linki
kurs dyskretnej:
https://www.cs.sfu.ca/~ggbaker/zju/math/
generating functions:
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_chap12.pdf
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/LRGF.html
https://aofa.cs.princeton.edu/30gf/
https://www.adamponting.com/some-basic-sequences-generating-functions-and-closed-forms/
algorytmy:
https://eduinf.waw.pl/inf/alg/001_search/index.php