Tożsamości kombinatoryczne i zliczanie

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ęć

1. 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

2. 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