Prowadzący
Piotr Pakosz (pakosz100 na gmailu)
Opis
Funkcje specjalne występujące w elementarnej kombinatoryce takie jak współczynniki dwumianowe czy liczby Fibonacciego, spełniają zaskakująco wiele tożsamości takich jak np. poniższa tożsamość Dixona:
$\sum_k (-1)^k {a+b \choose a+k} {a+c \choose c+k} {b+c \choose b+k} = \frac{(a+b+c)!}{a!b!c!}$
Metody ich dowodzenia można podzielić z grubsza na 2 klasy: konstruktywne i niekonstruktywne. Pierwsza polega na zinterpretowaniu stron tożsamości, jako wyrażeń zliczających obiekty w pewnej sytuacji kombinatorycznej oraz skorzystania z faktu, że moce zbiorów będących w bijekcji są równe. Metody niekonstruktywne polegają na manipulacjach algebraiczno-analitycznych zadanych wyrażeń. Okazuje się, że dla szerokiej klasy tożsamości takie manipulacje możemy wykonywać algorytmicznie lub prawie algorytmicznie, otrzymując w ten sposób dowody bez potrzeby odwoływania się do ludzkiej kreatywności.
Warsztaty podzielone będą na 2 części.
W pierwszej główny nacisk położony będzie na dowody konstruktywne - przez podwójne zliczanie i bijekcje. Ta część warsztatów będzie w większości polegać na stosowaniu elementarnych tricków, a większość czasu upłynie na ćwiczenia (przechodzące dynamicznie z wykładu i w wykład). Zamierzam opowiedzieć (jako przypomnienie) o podstawach - symbolach Newtona, liczbach Stirlinga, Catalana, Fibonacciego i ich uogólnieniach, zasadzie włączeń wyłączeń. Potem klasyczny rezultat o zliczaniu drzew etykietowanych. Jeżeli starczy czasu mogę też powiedzieć o interpretacjach kombinatorycznych liczb harmonicznych i ułamków łańcuchowych.
W drugiej części zajmiemy się algorytmami sumowania. Ta część będzie bardziej wykładowa niż ćwiczeniowa. Opowiem o algorytmach siostry Celine, Gospera i Zeilbergera. W ramach dostępnego czasu mogę też zarysować jak to wygląda od strony algebry operatorów rekurencyjnych.
Program zajęć
- Część pierwsza: konstruktywna
- podstawy zliczania, zasada włączeń-wyłączeń
- tożsamości ze współczynnikami dwumianowymi
- tożsamości pochodzące od rekurencji liniowych
- zliczanie drzew etykietowanych
- Część druga: algorytmiczna
- algorytm siostry Celine
- algorytm Gospera
- algorytm Zeilbergera
Wymagania
Przyda się umiejętność rozwiązywania najprostszych rekurencji i indukcja matematyczna. Ponadto znajomość "szkolnej" kombinatoryki: zasada mnożenia, współczynniki dwumianowe, etc.
Zadania kwalifikacyjne
Są Tutaj
Uwaga: rozwiązania można przesyłać w dowolnym sensownym formacie, PDF jest tylko sugestią.
Uwaga 2: do 13.07.09 23:59:59 można jeszcze wysyłać rozwiązania. Po tym terminie też można wysyłać rozwiązania, ale nie będą one przeze mnie sprawdzone.
Literatura
- W razie gdyby ktoś chciał się dowiedzieć czegoś więcej o algorytmach dowodzenia tożsamości, świetną pozycją jest książka "A=B", M. Petkovsek, H. Wilf, D. Zeilberger. Nazwiska autorów są w tym przypadku wystarczającą rekomendacją. Można ją znaleźć np. tu: http://www.math.upenn.edu/~wilf/AeqB.html
- O dowodach kombinatorycznych traktuje książka "Proofs that Really Count: The Art of Combinatorial Proof", A.T. Benjamin, J. Quinn
- Ogólnym wprowadzeniem do kombinatoryki enumeratywnej jest książka "A Course in Enumeration", M. Aigner
- A tutaj znaleźć można dużo zadanek na dowody bijektywne: http://www-math.mit.edu/~rstan/bij.pdf
2 ostatnie książki są do znalezienia na en.bookfi.org albo bookos.org