Dyskretna – Wzory – Sesja

🔢 INDUKCJA MATEMATYCZNA

Suma ciągu arytmetycznego (1+2+…+n)

\[1 + 2 + \dots + n = \frac{n(n+1)}{2}\]

Podstawowy wzór dowodzony indukcyjnie

Suma kwadratów liczb naturalnych

\[1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}\]

Zadanie 1 z prezentacji – do dowodu indukcyjnego

Suma ciągu geometrycznego (o a ≠ 1)

\[a + a^2 + a^3 + \dots + a^n = \frac{a(a^n – 1)}{a – 1}\]

Dla każdego a ≠ 1

Suma sześcianów liczb naturalnych

\[1^3 + 2^3 + \dots + n^3 = \left(\frac{n(n+1)}{2}\right)^2\]

Zadanie 6 z prezentacji

Nierówność potęgowa

\[2^n > 2n + 1 \quad \text{dla } n > 2\]

Zadanie 1 z nierówności

Nierówność Bernoulliego

\[(1 + a)^n \geq 1 + an \quad \text{dla } a \geq -1\]

Zadanie 2 z nierówności

Podzielność przez 2

\[2 \mid (n^2 – n)\]

Zadanie 4 z podzielności

Podzielność przez 6

\[6 \mid (n^3 – n)\]

Zadanie 5 z podzielności

Suma ciągu geometrycznego dla a=3

\[1 + 3^1 + 3^2 + \dots + 3^n = \frac{3^{n+1} – 1}{2}\]

Zadanie 2 z prezentacji

Suma ciągu arytmetycznego (4+10+…)

\[4 + 10 + 16 + \dots + (6n – 2) = n(3n + 1)\]

Zadanie 3 z prezentacji

Suma ułamków

\[\frac{1}{2\cdot5} + \frac{1}{5\cdot8} + \frac{1}{8\cdot11} + \dots + \frac{1}{(3n-1)(3n+2)} = \frac{n}{2(3n+2)}\]

Zadanie 4 z prezentacji

🎲 KOMBINATORYKA

Wariacje z powtórzeniami

\[\bar{V}_n^k = n^k\]

Wybieramy k-wyrazowy ciąg z n-elementowego zbioru, elementy mogą się powtarzać

Przykład: Liczba liczb czterocyfrowych z 10 cyfr: 10⁴

Wariacje bez powtórzeń

\[V_n^k = \frac{n!}{(n-k)!}\]

Wybieramy k-wyrazowy ciąg, elementy nie mogą się powtarzać (k ≤ n)

Permutacje bez powtórzeń

\[P_n = n!\]

Szczególny przypadek wariacji gdy k = n

Permutacje z powtórzeniami

\[P_n(k_1, k_2, \dots, k_m) = \frac{n!}{k_1! k_2! \dots k_m!}\]

k₁, k₂, …, kₘ to liczby powtórzeń poszczególnych elementów

Przykład: Permutacje słowa „matematyka”: 10!/(3!2!2!)

Kombinacje bez powtórzeń

\[C_n^k = \binom{n}{k} = \frac{n!}{k!(n-k)!}\]

k-elementowy podzbiór ze zbioru n-elementowego

Przykład: Wybór 3 osób z 30: C₃₀³ = 30!/(3!27!)

Kombinacje z powtórzeniami

\[\overline{C_n^k} = \binom{n + k – 1}{k} = \frac{(n + k – 1)!}{k!(n – 1)!}\]

k-elementowy podzbiór, elementy mogą się powtarzać

Rekurencja dla kolorowania kul

\[f(n, k) = f(n – 1, k) + f(n, k – 1)\]

f(n,k) – liczba pokolorowań k kul n kolorami

Warunki początkowe: f(1,k)=1, f(n,1)=n

Prawdopodobieństwo klasyczne

\[P(A) = \frac{|A|}{|\Omega|}\]

Klasyczna definicja prawdopodobieństwa

Ω – zbiór wszystkich zdarzeń elementarnych
|A| – liczba zdarzeń sprzyjających A

📈 DWUMIAN NEWTONA I REKURENCJE

Wzór Newtona (dwumianowy)

\[(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}\]

Podstawowy wzór dwumianowy

Szczególny przypadek wzoru Newtona

\[(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k\]

Dla x=1: \(\sum_{k=0}^{n} \binom{n}{k} = 2^n\)

Uogólniony wzór Newtona

\[(x_1 + \dots + x_m)^n = \sum_{t_1+\dots+t_m=n} \binom{n}{t_1, \dots, t_m} x_1^{t_1} \dots x_m^{t_m}\]

\(\binom{n}{t_1, \dots, t_m} = \frac{n!}{t_1! \dots t_m!}\) – współczynnik wielomianowy

Liczba permutacji (rekurencja)

\[a_n = n \cdot a_{n-1}, \quad a_0 = 1\]

Rozwiązanie: \(a_n = n!\)

Wieże Hanoi (rekurencja)

\[a_n = 2a_{n-1} + 1, \quad a_1 = 1\]

Rozwiązanie: \(a_n = 2^n – 1\)

Proste na płaszczyźnie (rekurencja)

\[a_n = a_{n-1} + n, \quad a_0 = 1, \quad a_1 = 2\]

Rozwiązanie: \(a_n = 1 + \frac{n(n+1)}{2} = 1 + \binom{n}{2}\)

Liczby Fibonacciego – rekurencja

\[F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0, \quad F_1 = 1\]

Podstawowy wzór rekurencyjny

Liczby Fibonacciego – wzór jawny

\[F_n = \frac{1}{\sqrt{5}} \left( \frac{1+\sqrt{5}}{2} \right)^n – \frac{1}{\sqrt{5}} \left( \frac{1-\sqrt{5}}{2} \right)^n\]

Rozwiązanie rekurencji metodą równania charakterystycznego

Równanie charakterystyczne: \(x^2 = x + 1\)

Metoda równania charakterystycznego

Dla \(a_n = Aa_{n-1} + Ba_{n-2}\)
Równanie: \(x^2 = Ax + B\)
Jeśli α,β różne pierwiastki: \(a_n = c_1\alpha^n + c_2\beta^n\)
c₁, c₂ z warunków początkowych

Ogólna metoda rozwiązywania liniowych rekurencji rzędu 2

🌀 FUNKCJE TWORZĄCE

Zwykła funkcja tworząca

\[f(x) = \sum_{i=0}^{\infty} a_i x^i\]

Reprezentacja ciągu jako szeregu potęgowego

Wykładnicza funkcja tworząca

\[f(x) = \sum_{i=0}^{\infty} a_i \frac{x^i}{i!}\]

Dla szybko rosnących ciągów (np. \(a_i = i!\))

Funkcja tworząca ciągu Fibonacciego

\[f(x) = \frac{x}{1-x-x^2}\]

Zwykła funkcja tworząca dla liczb Fibonacciego

Rozwinięcie funkcji tworzącej Fibonacciego

\[\frac{x}{1-x-x^2} = \frac{1}{\sqrt{5}} \left( \frac{\alpha_1}{1-\alpha_1x} – \frac{\alpha_2}{1-\alpha_2x} \right)\]

Gdzie \(\alpha_1 = \frac{1+\sqrt{5}}{2}\), \(\alpha_2 = \frac{1-\sqrt{5}}{2}\)

Przykład: an = n·an-1

f(x) = 1 + xf(x)
f(x) = \(\frac{1}{1-x}\) = \(\sum_{n=0}^{\infty} x^n\)
Stąd: \(a_n = n!\)

Przykład użycia funkcji tworzącej do rozwiązania rekurencji

📊 TEORIA GRAFÓW

Graf: Para G = (V(G), E(G)) gdzie V – zbiór wierzchołków, E – zbiór krawędzi
Graf prosty: Bez pętli i krawędzi wielokrotnych
Graf ogólny: Dopuszcza pętle i krawędzie wielokrotne

Stopień wierzchołka: Liczba krawędzi incydentnych z wierzchołkiem
Wierzchołek izolowany: Stopień = 0
Graf pełny Kₙ: Wszystkie wierzchołki połączone
Graf regularny: Wszystkie wierzchołki tego samego stopnia

Twierdzenie Eulera o cyklu Eulera

Cykl Eulera istnieje ⇔ graf spójny i wszystkie stopnie parzyste
Ścieżka Eulera istnieje ⇔ graf spójny i dokładnie 2 stopnie nieparzyste

Graf eulerowski – ma cykl Eulera
Graf półeulerowski – ma ścieżkę Eulera

Twierdzenie Cayleya

\[N = n^{n-2}\]

Liczba drzew na oznaczonych n wierzchołkach

N(2)=1, N(3)=3, N(4)=16, N(5)=125, N(6)=1296

Wzór Eulera dla grafów planarnych

\[|V| + |S| – |E| = 2\]

V – wierzchołki, S – ściany, E – krawędzie

Twierdzenie Kuratowskiego

Graf jest planarny ⇔ nie zawiera podgrafu homeomorficznego z K₅ lub K₃,₃

K₅ – graf pełny 5-wierzchołkowy
K₃,₃ – graf dwudzielny pełny (3+3)

Drzewo: Graf spójny i acykliczny
Równoważne definicje:
1. G jest drzewem
2. Każde 2 wierzchołki połączone dokładnie 1 drogą prostą
3. Graf spójny, ale usunięcie 1 krawędzi powoduje niespójność
4. Graf acykliczny, ale dodanie dowolnej krawędzi tworzy cykl

Graf dwudzielny: Wierzchołki można podzielić na 2 grupy, krawędzie tylko między grupami
Pełny graf dwudzielny Kₘ,ₙ: Każdy wierzchołek jednej grupy połączony z każdym drugiej grupy

Twierdzenie Halla (o małżeństwach)

Problem małżeństw jest rozwiązywalny ⇔ każdy podzbiór k panien akceptuje ≥ k kawalerów

Warunek istnienia skojarzenia doskonałego w grafie dwudzielnym

Ścieżka (droga): Ciąg krawędzi między dwoma wierzchołkami
Ścieżka prosta: Przez każdą krawędź przechodzi tylko raz
Cykl: Ścieżka prosta zaczynająca i kończąca się w tym samym wierzchołku
Ścieżka Hamiltona: Przechodzi przez wszystkie wierzchołki dokładnie raz
Cykl Hamiltona: Cykl przechodzący przez wszystkie wierzchołki dokładnie raz

🔢 MACIERZE GRAFÓW

Macierz sąsiedztwa (nieskierowany)

\[A_{ij} = \text{liczba krawędzi między wierzchołkami i i j}\]

Macierz symetryczna
Dla grafu prostego: 0 na diagonali, 0/1 poza diagonalą

Macierz sąsiedztwa (skierowany)

\[A_{ij} = \text{liczba krawędzi z i do j}\]

Krawędź wychodząca dodaje 1 w odpowiednim miejscu

Macierz incydencji (nieskierowany)

\[M_{ij} = \begin{cases} 1 & \text{gdy wierzchołek i jest incydentny z krawędzią j} \\ 0 & \text{w przeciwnym przypadku} \end{cases}\]

Macierz n × m, gdzie n – liczba wierzchołków, m – liczba krawędzi

Macierz incydencji (skierowany)

\[M_{ij} = \begin{cases} 1 & \text{gdy krawędź j wychodzi z wierzchołka i} \\ -1 & \text{gdy krawędź j wchodzi do wierzchołka i} \\ 0 & \text{w przeciwnym przypadku} \end{cases}\]

Specjalna notacja dla grafów skierowanych

Izomorfizm grafów: Dwa grafy G i H są izomorficzne jeśli istnieje bijekcja α: V(G)→V(H) taka że {u,v}∈E(G) ⇔ {α(u),α(v)}∈E(H)

Homeomorfizm grafów: Dwa grafy są homeomorficzne jeśli można je otrzymać z innego grafu przez wstawianie wierzchołków stopnia 2 na krawędziach

Podgraf: Graf otrzymany przez usunięcie pewnej liczby wierzchołków lub krawędzi (usunięcie wierzchołka = usunięcie przyległych krawędzi)

Problem 4 barw: Każdy graf planarny można pokolorować 4 kolorami tak, że sąsiednie wierzchołki mają różne kolory (odpowiednik: każdą mapę można pokolorować 4 kolorami)