Jacek Cichoń

Katedra Podstaw Informatyki ● WIT ● PWr
Strona główna Moje zajęcia

2020/21: Matematyka Dyskretna

Wykład przeznaczony jest dla studentów I roku I stopnia Informatyki Algorytmicznej. Odbywa się w piątki w godz. - na platformie Microsoft Teams. Na stronie tej znajdziesz informacje o zasadach zaliczenia, literaturze, listę zadań oraz streszczenie realizowanego materiału.

Literatura

Zasady zaliczania kursu

Ćwiczenia

Zasady zaliczenia ćwiczeń ogłaszają osoby z którymi macie ćwiczenia.

Egzamin

  1. Termin I: 28.06.2021 (poniedziałek), godz. 11:15-13:00
  2. Termin II: 07.07.2021 (środa), godz. 11:15-13:00

Egzamin będzie przeprowadzony za pomocą platformie ePortal PWr. Do egzaminu będą mogli przystąpić wszyscy studenci, również ci, którzy otrzymali ocenę 2.0 z ćwiczeń. Ocena za kurs będzie wystawiana za pomocą następującego wzoru: $$ K = \begin{cases} 2.0 &: \text{ jeśli } E = 2.0\\ \max\{E,C\} &: \text{ jeśli } E>2.0 \end{cases} $$ gdzie $C$ oznacza ocenę z ćwiczeń zaś $E$ ocenę z egzaminu.
Osoby które otrzymają ocenę 5.5 z ćwiczeń będą zwolnieni z egzaminu, ale otrzymają ocenę 5.0.
Jeśli ktoś otrzyma ocenę 5.0, a będzie chciał otrzymać 5.5, to będzie musiał odbyć ze mną krótką rozmowę na platformie Teams, na której dam jakieś zadanie do rozwiązania.

$ \def\RR{\mathbb{R}} \def\QQ{\mathbb{Q}} \def\ZZ{\mathbb{Z}} \def\CC{\mathbb{C}} \def\NN{\mathbb{N}} \def\IFF{\leftrightarrow} \newcommand{\span}[1]{\mathrm{span}(#1)} \newcommand{\IS}[2]{\langle\,#1,#2\rangle} \newcommand{\sgn}[1]{\mathrm{sgn}(#1)} \newcommand{\StirlingSb}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} \newcommand{\StirlingSa}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} $

Zagadnienia omówione na wykładzie

05.03.2021: Wstęp

  1. Problem Wież z Hanoi; $T_n$ = liczba przestawień krążków;
    1. Rekursja: $T_1=1$; $T_{n+1} = 2 T_{n} + 1$
    2. Rozwiązanie: $T_n = 2^n -1$ (dowód indukcyjny)
  2. Oznaczenia
    1. $[n] = \{1,2,\ldots,n\}$
    2. $Sym(X)$ = zbiór permutacji zbioru $X$; $Sym(n) = Sym([n])$
    3. $[n]^k = \{X\in P([n]): |X|=k\}$
  3. Tw. $|Sym(n)| = n!$,
  4. Tw [Zasada Włączania-Wyłączania]
    $$ |\bigcup_{k=1}^{n} A_k| = \sum_{k=1}^{n} (-1)^k \sum_{T\in[n]^k} |A_T| $$
    gdzie $A_T = \bigcap_{k\in T} A_k$
  5. Tw. $[n]^k = \frac{n!}{k!(n-k)!} (= \binom{n}{k})$
  6. Analiza złożoności obliczenowej pętli 
    FOR I=1 TO N DO
  FOR J=I+1 TO N DO
    OP(I,J)
  7. Równoważność asymptotyczna: $(a_n) \sim (b_n) \IFF \lim_{n\to\infty} \frac{a_n}{b_n} = 1$
Notatki z wykładu: MD01.pdf

Twoje notatki:

12.03.2021: Wstęp

  1. Nieporządki:
    1. $\pi\in Sym(n)$ jest nieporządkiem jeśli $(\forall k\in [n])(\pi(k)\neq k)$
    2. Tw. Niech $N_n$ oznacza zbiór nieporządków na $[n]$. Wtedy
      $$\frac{|N_n|}{n!} = \sum_{k=0}^{n} \frac{(-1)^k}{k!}$$
    3. Wniosek: $\lim_n \frac{|N_n|}{n!} = \frac{1}{e}$
  2. Pojęcie przestrzeni probabilistycznej dyskretnej
  3. Pojęcie przestrzeni probabilistycznej kombinatorycznej
  4. Nawias logiczny: dla formuły $\phi$ $$ \|\phi\| = \begin{cases} 1 &: \phi \\ 0 &: \neg \phi \end{cases} $$
  5. Wzór dwumianowy Newtona
    $$ (x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}, \quad \text{ dla } n\in\NN $$
  6. Wnioski
    1. $\sum_{k=0}^{n} \binom{n}{k} = 2^n$
    2. $\sum_{k=0}^{n} (-1)^k \binom{n}{k} = \|n=0\|$
    3. $\sum_{k=0}^{n} \binom{n}{k}m^k = (m+1)^n$
Notatki z wykładu: MD02.pdf

Twoje notatki:

19.03.2021: Wspołczynniki dwumianowe

  1. Dowód wzoru dwumianowego Newtona
  2. Podstawowe tożsamości
    1. symetria: $\binom{n}{k} = \binom{n}{n-k}$, dla $0\leq k\leq n$ oraz $k,n\in\NN$
    2. tożsamość Pascala: $\binom{n}{k} = \binom{n-1}{k}+\binom{n-1}{k-1}$, dla $1\leq k\leq n$ oraz $n,k\in\NN$
    3. pochłanianie: $\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}$ dla $1\leq k\leq n$ oraz $n,k\in\NN$
  3. Przykład: $\sum_{k=0}^{n}k \binom{n}{k} = n 2^{n-1}$, gdzie $n\in\NN$ i $n\geq 1$
  4. $\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$, gdzie $0\leq k\leq m \leq n$ oraz $k,m,n\in\NN$
  5. Sumy częściowe:
    1. $\sum_{k\leq n} \binom{k}{a} = \binom{n+1}{a+1}$
    2. $\sum_{k\leq n} \binom{a+k}{a} = \binom{n+a+1}{n}$
    3. $\sum_{k\leq m} (-1)^k \binom{n}{k} = (-1)^m \binom{n-1}{m}$
    4. Splot Vardemonda: $\binom{n+m}{k} = \sum_{a+b=k}\binom{n}{a}\binom{m}{b}$
  6. Wniosek (tożsamość Cauchy'ego): $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$
Notatki z wykładu: MD03.pdf

Twoje notatki:

26.03.2021: Wspołczynniki dwumianowe: II

  1. Dolna silnia: $x^{\underline{k}} = \prod\limits_{l=0}^{k-1}(x-l)$
  2. Górna silnia: $x^{\overline{k}} = \prod\limits_{l=0}^{k-1}(x+l)$
  3. Def: $\binom{x}{k} = \frac{x^{\underline{k}}}{k!}$, gdzie $x\in\CC$ oraz $k\in\NN$
  4. Przykład: $\binom{-1}{k} = (-1)^k$
  5. Obserwacja: $(x^\alpha)^{'} = \alpha x^{\alpha -1}$, $(x^\alpha)^{''} = \alpha(\alpha-1) x^{\alpha -2}$, ..., $(x^\alpha)^{(k)} = \alpha^{\underline{k}}x^{\alpha - k}$
  6. Twierdzenie: Niech $x \in \RR$, $|x|\lt 1$ oraz $k\in\NN$. Wtedy
    $$(1+x)^{\alpha} = \sum_{k=0}^{\infty} \binom{\alpha}{k}x^k$$
  7. Przykład: $(1+x)^{-1} = \sum_{k} \binom{-1}{k}x^k = \sum_{k=0}^{\infty} (-1)^{k}x^k$
Notatki z wykładu: MD04.pdf

Twoje notatki:

30.03.2021: Wspołczynniki dwumianowe: III

  1. Dowód twierdzenia dwumianowego z poprzedniego wykładu
  2. Górna negacja:
    $$\binom{x}{k} = (-1)^k \binom{k-x-1}{k}$$
  3. Przykład: $(1-x)^{-2} = \ldots =\sum_{k\geq 0} (k+1)x^k$
  4. Wzó połówkowy: $x^{\underline{k}}(x-\frac12)^{\underline{k}} = \frac{1}{4^x} (2x)^{\underline{2k}}$
  5. Wniosek: $\binom{n-\frac12}{n} = \frac{1}{4^n}\binom{2n}{n}$
  6. Przykład: $\sum_n\binom{2n}{n}x^n = \ldots = (1-4x)^{-1/2}$, dla $|x| \lt \frac14$
  7. Twierdzenie: Niech $a,b\in\NN$, $a\lt b$ i $f:[a,b]\to\RR$ będzie funkcją nimalejącą. Wtedy
    $$ f(a)+\int_a^b f(x)dx \leq \sum_{k=a}^{b} \leq \int_a^b f(x)dx + f(b)~. $$
  8. Wniosek: $e\left(\frac{n}{e}\right)^n \leq n! \leq e\cdot n \left(\frac{n}{e}\right)^n$
  9. Wzór Stirlinga:
    $$ n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n $$
  10. Przykład: $\binom{2n}{n} \sim \frac{1}{\sqrt{\pi n}} 4^n$
  11. Def (Liczby Harmoniczne) $H_n = \sum_{k=1}^{n} \frac1k$
  12. Tw: $\ln n + \frac1n \leq H_n \leq \ln(n) + 1$
  13. Tw.(asymptotyka liczb harmonicznych)
    $$ H_n = \ln(n) + \gamma +\frac{1}{2n} + O\left(\frac{1}{n^2}\right) $$
    gdzie $\gamma = 0.5772...$ (stała Eulera-Masharoni'ego)
Notatki z wykładu: MD05.pdf

Twoje notatki:

09.04.2021: Liczby specjalne - I

  1. Ciąg Fibonacciego: $F_0=0$, $F_1=1$; $F_{n+2} = F_{n}+F_{n+1}$
  2. Tw. $\mathrm{nwd}(F_{n+1},F_n) = 1$.
  3. Obserwacja $$ \begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \circ \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} $$
  4. Wniosek: $$ \begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \circ \begin{bmatrix} 1 \\ 0 \end{bmatrix} $$
  5. Wniosek: (wzór Binet'a)
    $$ F_n = \frac{1}{\sqrt{5}} \left(\left(\frac{\sqrt{5}+1}{2}\right)^n + (-1)^{n+1} \left(\frac{\sqrt{5}-1}{2}\right)^n\right) $$
  6. Fakt: $$ \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix} $$
  7. Wniosek (Cassini): $F_{n+1}F_{n-1} - \left(F_n\right)^2 = (-1)^n$.
  8. Wniosek: $F_{n+m} = F_{n+1} F_m + F_n F_{m-1}$
  9. Tw: $\sum_a \binom{n-a}{a} = F_{n+1}$
  10. Def. (Liczby Stirlinga II rodzaju) $$ \StirlingSb{n}{k} = |\{\mathcal{P}: |\mathcal{P}|=k \land \mathcal{P} \mbox{ jest partycją zbioru } [n]\}| $$
  11. Przykłady (dla $n\geq 1$): $\StirlingSb{n}{1} = 1$, $\StirlingSb{n}{n} = 1$, $\StirlingSb{n}{n-1} = \binom{n}{2}$, $\StirlingSb{n}{2} = 2^{n-1} - 1$
  12. Tw. Niech $Sur(A,B)$ oznacza zbiór wszystkich surjekcji ze zbioru $A$ na zbiór $B$. Wtedy $$ \StirlingSb{n}{k} = \frac{1}{k!} |Sur([n],[k])|. $$
Notatki z wykładu: MD06.pdf

Twoje notatki:

16.04.2021: Liczby specjalne - II

  1. Obserwacja: $\StirlingSb{n}{0} = ||n=0||$
  2. Tw. $\StirlingSb{n}{k} = \frac{1}{k!}\sum_{a=0}^{k} (-1)^a \binom{k}{a}(k-a)^n$.
    Uwaga: (1) ten wzór przydaje się dla małych wartości $k$.
    (2) ze wzoru tego wynika, że dla ustalonego $k$ mamy $\StirlingSa{n}{k} \sim k^n/k!$.
  3. Wniosek. $\StirlingSb{n}{3}= \frac{1}{3!}(3^n - 3 \cdot 2^n + 3 - ||n=0||)$.
  4. Tw.
    $$ \StirlingSb{n+1}{k+1} = (k+1)\StirlingSb{n}{k+1} + \StirlingSb{n}{k} $$
  5. Tw. $x^n = \sum_{k=0}^{n} \StirlingSb{n}{k} x^{\underline{k}}$
  6. Tw. $\StirlingSb{n+1}{k+1} = \sum_{a=0}^{n} \binom{n}{a}\StirlingSb{n-a}{k}$
  7. Def. (liczby Bella) $B_n = \sum_{k=0}^{n} \StirlingSb{n}{k}$
  8. Wniosek (zadanie) $B_{n+1} = \sum_{a=0}^{n} \binom{n}{a} B_{n-a}$
  9. Def. (liczby Stirlinga I rodzaju) $\StirlingSa{n}{k}$ = liczba permutacji zbioru $[n]$ rozkładających się na $k$ cykli
  10. Wniosek. $\sum_{k}\StirlingSa{n}{k} = n!$
  11. Obserwacje: $\StirlingSa{n}{n} = 1$; $\StirlingSa{n}{n-1} = \binom{n}{2}$
  12. Tw. $\StirlingSa{n}{1} = (n-1)!$
  13. Tw. $\StirlingSa{n}{2} = (n-1)! H_{n-1}$
Notatki z wykładu: MD07.pdf

Twoje notatki:

23.04.2021: Liczby specjalne - III

  1. Tw. $\StirlingSa{n+1}{k+1} = \StirlingSa{n}{k} + n\StirlingSa{n}{k+1}$
  2. Tw. $x^{\overline{n}} = \sum_{k=0}^{n} \StirlingSa{n}{k} x^k$
  3. Def. Zmienna losowa na dyskretnej przestrzeni probabilistycznej $(\Omega,P)$: dowolna funkcja $X:\Omega\to\RR$
  4. Def. Wartość oczekiwana zmiennej losowej $X$: $$ E(X) = \sum_{\omega\in\Omega} X(\omega) P(\{\omega\}) $$
  5. Przykład: Jeśli $\Omega =[n]$, $P(A) = \frac{|A|}{n}$ i $X:\Omega\to\RR$ to $$ E(X) = \frac{X(1)+\ldots+X(n)}{n} $$
  6. Tw. Jeśli $X:\Omega\to\NN$, to $$ E(X) = \sum_{n=0}^{\infty} n \cdot P(X=n)~. $$
  7. Przekład. Niech $\Omega=P([n])$, $P(\{A\}) = \frac{1}{2^n}$ oraz $S(A)=|A|$ to $$ E(S) = \frac{n}{2} $$
  8. Zadanie: $\Omega = [n]^2$, $P(\{a,b\}) = 1/\binom{n}{2}$, $M(\{a,b\} = \min(a,b)$. Oblicz $E(M)$.
  9. Funkcją tworzącą prawdopodobieństwo zmiennej losowej $X:\Omega\to\NN$ nazywamy funkcję $$ \phi_X(x) = \sum_{n=0}^{\infty} P(X=n) \cdot x^n $$ Mamy:
    1. $\phi(1) = 1$
    2. $\phi'(1) = E(X)$
  10. Twierdzenie. Niech $\Omega = Sym([n])$, $P(\{\sigma\}) = 1/n!$. Niech $C(\sigma)$ = liczba cykli na które rozkłada się $\sigma$. Wtedy $$ E(C) = H_n \approx \ln n~. $$
Notatki z wykładu: MD08.pdf

Twoje notatki:

30.04.2021: Multizbiory. Funkcje tworzące

  1. Def. Niech $f:X\to\RR$. Suportem $f$ nazywamy zbiór $supp(f)=\{x\in X:f(x)\neq 0\}$
  2. Def. Multizbiory elementów $X$: $$\mathcal{M}(X)= \{f\in \NN^X: |supp(f)|\lt\aleph_0\}$$
  3. Rozmiar multizbioru $m$: $||m||= \sum_{x\in X} f(x)$
  4. Tw. Jeśli $|X|=k$ to $$ |\{m\in \mathcal{M}(X): ||m||= n\}| = \binom{n+k-1}{k-1} $$
  5. Uwaga: $\binom{n+k-1}{k-1} = \frac{k^{\overline{k}}}{n!}$
  6. Def. Dla $a\in X^{[n]}$ określamy $mult(a)\in \mathcal{M}(X)$ wzorem $$ (mult(a))(x) = |\{i\in[n]: a_i = x\}$$
  7. Def. Niech $m\in\mathcal{M}(X)$ i $||m|| =n$. Permutacją $m$ nazywamy dowolny ciąg $a\in X^{[n]}$ taki, że $mult(a)=m$
  8. Tw. Niech $m \in \mathcal{M}([k])$ i $||m||=n$. Wtedy zbiór premutacji $m$ ma moc
    $$ \frac{n}{m(1)!\cdots m(k!)}$$
  9. Def [współczynniki multinomialne] $$\binom{n}{a_1,\ldots,a_k} = \frac{n}{a_1!\cdots a_k}$$ dla takich $a_1,\ldots, a_k$, że $a_1+\cdots+a_k = n$.
  10. $$(x_1+\cdots+x_k)^n = \sum_{a_1+\cdots+a_k=n}\binom{n}{a_1,\ldots,a_k}x_1^{a_1}\cdots x_k^{a_k}$$
  11. Przykład: $\frac{1}{1-(1+x)y} = \sum_n\sum_k \binom{n}{k} x^k y^n$
  12. Def. Funkcją tworzącą ciągu $a \in \CC^\NN$ nazywamy szereg (formalny) $$ A(x) = \sum_n a_n x^n$$
  13. Przykład. Jeśli $a_n = 1$ dla każdego $n\in\NN$ to $A(x) = \sum_n x^n = \frac{1}{1-x}$ (dla $|x|\lt 1$)
  14. Przykład. Ustalmy $n$. Jeśli $b_k = \binom{n}{k}$ dla każdego $k\in\NN$ to $B(x) = \sum_k b_k x^n = (1+x)^n$
  15. Funkcja tworząca ciągu liczb Fibonnaciego:
    1. Definiujemu $F(x) = \sum_n F_n x^n$
    2. Liczymy $$ F(x) = F_0 + F_1 x + \sum_n F_{n+2} x^{n+2} = x + \sum_n (F_n+F_{n+1})x^{n+2} = $$ $$ x + \sum_n F_n x^{n+2} + \sum_n F_{n+1} x^{n+2} = x + x^2 \sum_n F_n x^{n} + x \sum_n F_{n+1} x^{n+1} = $$ $$ x + x^2 F(x) + x F(x) $$
    3. Z tego wnioskujemy, że
      $$ F(x) = \frac{x}{1-x-x^2} $$
    4. Tym wzorem zajmiemy się na następnym wykładzie.

Twoje notatki:

07.05.2021: Klasy kombinatoryczne

  1. Dokończenie wyprowadzenia wzoru Binet'a za pomocą funkcji tworzącej ciągu Fibonacciegi (spisuję to tutaj dokładniej, bo na wykładzie zapomniałem o jednym minusie)
    1. Mamy $F(x) = \frac{x}{1-x-x^2}$
    2. Rozwiązania równania $x^2+x-1=0$ to $\omega_1 = \frac{-1+\sqrt{5}}{2}$ i $\omega_2 = \frac{-1-\sqrt{5}}{2}$.
      Zauważamy, że $\omega_1\cdot\omega_2 = -1$ oraz $\omega_1-\omega_2 = \sqrt{5}$.
    3. Szukamy $A$ i $B$ takich, że $$ \frac{x}{1-x-x^2} = \frac{A}{\omega_1-x} + \frac{B}{\omega_2-x} $$
    4. Po krótkich obliczeniach wyznaczamy $A=\frac{\omega_1}{\omega_1-\omega_2}$ oraz $B= -\frac{\omega_2}{\omega_1-\omega_2}$
    5. Mamy więc $$ F(x) = \frac{1}{\sqrt{5}}\left(\frac{\omega_1}{\omega_1-x} - \frac{\omega_2}{\omega_2-x}\right) = \frac{1}{\sqrt{5}}\left(\frac{1}{1 - \frac{x}{\omega_1}} - \frac{1}{1-\frac{x}{\omega_2}}\right) = $$ (teraz chyba najważniejszy moment) $$ \frac{1}{\sqrt{5}}\left(\sum_{n\geq 0}\left(\frac{1}{\omega_1}\right)^n x^n - \sum_{n\geq 0}\left(\frac{1}{\omega_2}\right)^n x^n\right) = \frac{1}{\sqrt{5}} \sum_{n\geq 0}\left( \left(\frac{1}{\omega_1}\right)^n - \left(\frac{1}{\omega_2}\right)^n\right) x^n = $$ $$ \sum_{n\geq 0} \frac{1}{\sqrt{5}} \left( (-\omega_2)^n - (-\omega_1)^n \right) x^n $$ $$ \sum_{n\geq 0} \frac{1}{\sqrt{5}} \left( \left(\frac{1+\sqrt{5}}{2}\right)^n - (-1)^n \left(\frac{-1+\sqrt{5}}{2}\right)^n \right) x^n $$
  2. Def. Klasa kombinatoryczna: para $\mathcal{A}=(A,|\cdot|)$ taka że $|\cdot|:A\to\NN$ i dla każdego $n\in\NN$ mamy $\{a\in A: |a|=n\}|\lt\aleph_0$.
    Oznaczenia:
    1. $A_n = \{a\in A: |a|=n\}$
    2. $a_n = |A_n|$
    3. $\mathcal{A}(x) = \sum_n a_n x^n$ (funkcja tworząca klasy)
  3. Przykład: Niech $\mathcal{N} = (\NN, |\cdot|)$, gdzie $|n|=n$. Wtedy $$\mathcal{N}(x) = \frac{1}{1-x}$$
  4. SUMA KLAS: Zakładamy, że $\mathcal{A}=(A,|\cdot|_A)$ i $\mathcal{B}=(B,|\cdot|_B)$ są klasami kombinatorycznymi oraz $A\cap B = \emptyset$. Określamy $$ \mathcal{A} + \mathcal{B} = (A \cup B, |\cdot|_A \cup |\cdot|_B) $$ Tw. To jest klasa kombinatoryczna oraz $(\mathcal{A} + \mathcal{B})(x) = \mathcal{A}(x) + \mathcal{B}(x)$
  5. PRODUKT KLAS: Zakładamy, że $\mathcal{A}=(A,|\cdot|_A)$ i $\mathcal{B}=(B,|\cdot|_B)$ są klasami kombinatorycznymi. Określamy $$ \mathcal{A} \times \mathcal{B} = (A \times B, |\cdot|) $$ gdzie $|(a,b)| = |a|_A + |b|_B$.
    Tw. To jest klasa kombinatoryczna oraz $(\mathcal{A} \times \mathcal{B})(x) = \mathcal{A}(x) \cdot \mathcal{B}(x)$
  6. Def. $\mathcal{E} = (\{\epsilon\},|\cdot|)$, gdzie $|\epsilon|=0$.
    Zauważmy, że $\mathcal{E}(x) = 1$.
  7. CIĄGI ELEMENTÓW KLASY: Zakładamy, że $\mathcal{A}=(A,|\cdot|_A)$ jest taką klasą, że $a_0 = 0$. Określamy $$ \mathrm{SEQ}(\mathcal{A}) = \mathcal{E} + A + (A\times A) + (A\times A\times A) + \ldots $$ Tw. To jest klasa kombinatoryczna oraz $$\mathrm{SEQ}(\mathcal{A} )(x) = \frac{1}{1-\mathcal{A}(x)}$$
  8. Przykład (domino). Rozważamy klasę $\mathcal{D} = (\{a,b\},|\cdot |)$, gdzie $|a|=1$ i $|b|=2$. Wtedy $\mathcal{D}(x) = x+x^2$. Zatem $$\mathrm{SEQ}(\mathcal{D})(x) = \frac{1}{1-x-x^2}$$

Twoje notatki:

14.05.2021: Klasy kombinatoryczne - II

  1. ANALIZA MATEMATYCZNA: Dla $f:\RR^2\to\RR$ wprowadzamy oznaczenie na specyficzny operator różniczkowania: $$(D f)(a,b) = \{x \frac{d}{dx} + y \frac{d}{dy}\}(f)(a,b) = (x-a) \left(\frac{d f}{d x}|_{(x,y)=(a,b)}\right) + (y-b) \left(\frac{d f}{d y}|_{(x,y)=(a,b)}\right)~.$$ Następnie definiujemy iterację tego operarora $$(D^{(k)} f)(a,b) = \sum_{i=0}^{k} \binom{k}{i}(x-a)^i(y-b)^{k-i} \left(\frac{d^{(k)}f}{dx^{i}dy^{k-i}}\right)|_{(x,y)=(a,b)}~.$$ Wtedy
    $$ f(x,y) = f(0,0) + \sum_{k=1}^{n-1} \frac{D^{(k)}(f)(0,0)}{k!} + R_n $$
    gdzie $R_n = \frac{1}{n!} D^{(k)}(f)(\theta x,\theta y)$ dla pewnego $\theta \in (0,1)$.
    Wzór ten bez trudu możecie sobie wyprowadzić stosując wzór Taylora dla funkcji jednej zmiennej do funkcji $\phi(t) = f(t\cdot y,t\cdot y)$. Spróbujecie to zrobić najpierw dla $n=2$, potem dla $n=3$ a potem, jak zobaczycie co się dzieje, wyprowadźcie sobie go dla dowolnego $n$.
  2. Multizbiory: Jeśli $\mathcal{A}$ jest klasą kombinaroryczną bez elementów rozmiaru $0$ to
    $$Mult(\mathcal{A})(x) = \prod_{a\in A} \frac{1}{1-x^{|a|}}$$
Notatki z wykładu: MD11.pdf

Twoje notatki:

21.05.2021: Klasy kombinatoryczne - III

  1. ANALIZA MATEMATYCZNA: notacja $f=O(g)$ oraz $f = \Theta(g)$
  2. Cykle: Jeśli $\mathcal{A}$ jest klasą kombinaroryczną bez elementów rozmiaru $0$ to
    $$Cycle(\mathcal{A})(x) = \sum_{n \geq 1}\frac{\phi(n)}{n} \ln \frac{1}{1-\mathcal{A}(z^n)}$$
    gdzie $\phi(n) = |\{k\in\{1,\ldots n\}: nwd(k,n)=1\}|$ (funkcja "phi" Eulera).
  3. Przykład: Rozważamy $\mathcal{A} = (\{a,b\},|\cdot|)$, gdzie $|a|=|b| = 1$. Mamy $\mathcal{A}(x) = 2 x$. Więc $$ Cycle(\mathcal{A})(x) = \sum_{n \geq 1}\frac{\phi(n)}{n} \ln \frac{1}{1-2x^n} = \sum_{n \geq 1}\sum_{k\geq 1}\frac{\phi(n)}{n}\frac{1}{k}2^k x^{nk} = $$ $$ = \sum_{m\geq 1} x^m \frac{1}{m} \sum_{n\cdot k=m}\phi(n)2^k~. $$ Zatem, dla dowolnej liczby pierwszej $p$ mamy $$ [x^p]Cycle(\mathcal{A})(x) = \frac{1}{p} \left(2^p + (p-1)\cdot 2\right)~. $$
Notatki z wykładu: MD12.pdf

Twoje notatki:

28.05.2021: Klasy kombinatoryczne - IV

  1. Liczby Catalana: $C_n = \frac{1}{n+1}\binom{2 n}{n}$
  2. [LIT] Załóżmy, że $\phi$ jest analityczna w otoczeniu zera i $\phi(0)\neq 0$. Istnieje wtedy funkcja $f$ analityczna w otoczeniu zera taka, że $$ f(x) = x \cdot \phi(f(x)) $$ dla $x$ z tego otoczenia. Co więcej:
    $$[z^n]f[x] = \frac{1}{n}[u^{n-1}] \left(\phi(u)\right)^n$$
  3. Ścieżki Dyck'a
Notatki z wykładu: MD13.pdf

Twoje notatki:

Strona główna Moje zajęcia