Processing math: 0%
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