Jacek Cichoń

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

2023/24: Wstęp do Kombinatoryki Analitycznej

Wykład przeznaczony jest dla studentów I stopnia Informatyki na WIT. Odbywa się w czwartki w godz. - w sali 30/D-1.

Zasady zaliczania kursu

Zaliczenie tego kursu polega na otrzymaniu zaliczenia z ćwiczeń i z laboratorium. Nie ma egzaminu końcowego.

Literatura

  1. P. Flajolet, R. Sagewick, Analytic Combinatorics, Cambridge University Press, 2009
  2. F. Bergeron, G. Labelle, P. Leroux, Introduction to the Theory of Species of Structures, 2011
  3. Lista zadań: ACombExercises.pdf, Uwaga: lista ta będzie się systematycznie rozszerzać.
$ \def\RR{\mathbb{R}} \def\QQ{\mathbb{Q}} \def\ZZ{\mathbb{Z}} \def\CC{\mathbb{C}} \def\NN{\mathbb{N}} \def\BIND{\,>\!>\!=\,} \newcommand{\span}[1]{\mathrm{span}(#1)} \newcommand{\IS}[2]{\langle\,#1,#2\rangle} \newcommand{\sgn}[1]{\mathrm{sgn}(#1)} $

Zagadnienia omówione na wykładzie

05.10.2023: Wstęp

  1. Uogólnienia wzoru dwumianowego: $$\prod_{i=1}^{n}(1+x_i) = \sum_{k=1}^{n} \sum_{T\in [n]^k} \prod_{i\in T} x_i$$
  2. Wzór $n$- mianowy: $$(x_1+\ldots+x_k)^n = \sum_{\alpha} \binom{n}{\alpha}x^{\alpha}~,$$ gdzie sumowanie odbywa się po wszystkich takich $\alpha\in [n]^{[k]}$, że $\sum_{i=1}^{k}\alpha_i = n$, $x^{\alpha} = \prod_{i=1}^k x_i^{\alpha_i}$ oraz $$ \binom{n}{\alpha} = \frac{n!}{\alpha_1 !\cdots\alpha_k!}~. $$
  3. Funkcja tworząca ciągu $a=(a_n)_n$: $f_a(x) = \sum_{n\geq 0} a_n x^n$
  4. Algebraiczna wersja zasady włączania - wyłączania:
    • ustalamy rodzinę $A_1,\ldots,A_n$ podzbiorów $\Omega$
    • dla $k\in [n]$ definiujemy $A_k = \sum_{T\in[n]^k} |\bigcap_{i\in T}A_i|$
    • dla $k\in [n]$ definujemy $E_k = \{\omega\in\Omega: |\{i\in[n]: \omega\in A_i\}|=k\}$
    • kładziemy $\mathcal{N}(x) = \sum_{k=0}^{n}A_k x^k$
    • kładziemy $\mathcal{E}(x) = \sum_{k=0}^{n}|E_k| x^k$
    Twierdzenie. $\mathcal{N}(x) = \mathcal{E}(x+1)~.$
  5. Pierścień szeregów formalych $K[[x]]$
  6. Tw. Element $a\in K[[x]]$ jest odwracalny w $K[[x]]$ wtedy i tylko wtedy, gdy $[x^0]a \neq 0$.

12.10.2023: Klasy kombinatoryczne

  1. Własności szeregów potęgowych
  2. Zgodność działań algebraicznych w $K[[x]]$ z działaniami na szeregach potęgowych o niezerowym promieniu zbieżności::
    • Definiujemy $\mathcal{C} = \{a\in K[[x]]: \limsup_n |a_n|^{\frac1n} \lt \infty\}$
    • Definiujemy: $\mathcal{P}$ = rodzina wszystkich szeregów potęgowych
    • Definiujemy: $\mathcal{P}_c$ = szeregi potęgowe o niezerowym promieniu zbieżności
    • Definiujemy: $\phi:\mathcal{C} \to \mathcal{P}$ wzorem $$(\phi(a))(x) = \sum_{n\geq 0} a_n x^n$$ dla $x$ z przedziału zbieżności.
    • Pokazujemy, że $\phi:\mathcal{C} \to \mathcal{P}_c$ jest bijekcją
    • Pokazujemy, że $\phi(a+b) = \phi(a)+\phi(b)$, $\phi(a\cdot b) = \phi(a)\cdot\phi(b)$ (iloczyn Cauchy'ego), $\phi(a^{-1}) = \frac{1}{\phi(a)}$ dla odwracalnych $a$
    • Pokazujemy, że $\phi(D a) = \frac{d}{d x} \phi(a)$
    • Pokazujemy, że $\phi(\int a) = \int_{0}^{x} \phi(a)(t) dt$
  3. Przykład: Rozważamy ciąg $a_0=0$, $a_{n+1} = 2 a_n + n$. Rozważamy funkcję tworzącą $A(x) = \sum_n a_n x^n$. Pokazujemy, że $$A(x) = \frac{x^2}{(1-2x)(1-x)^2}$$. Stosując rozkład na ułamki proste otrzymujemy $a_n = 2^n - (n+1)$.
  4. Przypomnienie (liczby Fibonacciego): jeśli $F_0=0; F_1 = 1; F_{n+2}=F_n+F_{n+1}$ i $\mathcal{F}(x) = \sum_n F_n x^n$, to $$\mathcal{F}(x) = \frac{x}{1-x-x^2}~.$$
  5. Pojęcie klasy kombinatorycznej
  6. Konstrukcje:
    • $(\mathcal{A}+\mathcal{B})(x) = \mathcal{A}(x) + \mathcal{B}(x)$
    • $(\mathcal{A}\times\mathcal{B})(x) = \mathcal{A}(x) \cdot \mathcal{B}(x)$
    • $SEQ(\mathcal{A})(x) = \frac{1}{1-\mathcal{A}(x)}$
  7. Przyklad. Rozważamy klasę $\mathcal{D} = (\{a,b\},|\cdot|)$, gdzie $|a|=1$ oraz $|b|=2$. Wtedy $\mathcal{D}(x) = x + x^2$, wiec $SEQ(\mathcal{D})(x) = \frac{1}{1-x-x^2}$, z czego otrzymujemy $d_n = F_{n+1}$, gdzie $F_n$ oznacza $n$-tą liczbę Fibonacciego.

19.10.2023:

  1. Pojęcie kategorii

26.10.2023: Gatunki kombinatoryczne

  1. Pojęcie funktora.
  2. Przykłady funktorów
  3. Kategoria FIN: obiekty = zbiory skończone; morfizmy = bijekcje
  4. Pojęcie gatunku kombinatorycznego: endofunktor kategorii FIN
  5. Funkcja tworząca gatunku $F$: $F(x) = \sum_{n\geq 0} |F([n])| \frac{x^n}{n!}$
  6. Przykłady:
    1. Funktor zbioru potęgowego: $\mathcal{P}(X) = P(X)$, $(\mathcal{P}(f))(A) = f[A]$;
      $\mathcal{P}(x) = e^{2x}$
    2. Porządki liniowe: $Lin(X) = $ zbiór liniowych porządków na $X$;
      $Lin(f)((x_1 \lt x_2 \lt \ldots \lt x_n)) = (f(x_1) \lt \ldots \lt f(x_n))$
      $Lin(x) = \frac{1}{1-x}$
    3. Permutacje: $S(X) = $ zbiór permutacji zbioru $X$; $(S(f))(\pi) = f \circ \pi \circ f^{-1}$
      $S(x) = \frac{1}{1-x}$
Strona główna Moje zajęcia