Matematyka dyskretna, czyli liczenie po cichu

Opis

Matematyka dyskretna jest w rzeczywistości zbiorczą nazwą na wiele poddziedzin matematyki, które zajmują się badaniem struktur nieciągłych. W tym opisie zawiera się ogrom materiału, między innymi logika matematyczna, kombinatoryka, teoria grafów, prawdopodobieństwo, teoria gier, i wiele wiele innych. Z tego powodu nazwanie warsztatu “Matematyka dyskretna“ jest małym kłamstwem. Jest to temat zbyt duży i w praktyce będziemy się skupiać na ciekawych narzędziach, które pojawiają się w tej dziedzinie. Do nich należą:

1. Zasada szufladkowa Dirichleta
2. Interpretacja kombinatoryczna
3. Zasada włączeń i wyłączeń
4. Nieporządki, podziały
5. Funkcje tworzące  
6. Metody przekształcania wzorów rekurencyjnych na jawna
7. Lemat Cauchego-Frobeniusa-Burnsidea - co mają permutacje do zliczania

tl;dr będziemy robić kombinatorykę na sterydach

Wymagania

Do zrozumienia warsztatów potrzebna jest wiedza z zakresu kombinatoryki licealnej i trochę analizy:

1. Czym są permutację, kombinacje bez powtórzeń, wariacje i jak się je zlicza (*)
   
2. Reguła mnożenia, reguła dodawania (*)
   
3. Czym są zależności rekurencyjne
   
4. Jak policzyć pochodną z prostych funkcji (*)
   
5. Czym są iniekcje, surjekcje, bijekcje, składanie funkcji

(*) - sprawdzane na zadaniach kwalifikacyjnych

Przydatne rzeczy

Praktyczne:

Pierwsze kilka stron wykładów mogę przydać się w rozwiązywaniu  zadać kwalifikacyjnych:
https://home.agh.edu.pl/~meszka/md_wfis.pdf (Jeżeli ktoś rozumie wszystko co tutaj jest to warsztaty będą zbędne)
Dwie książki, które blisko pokrywają się z materiałem warsztatów to:

• Matematyka dyskretna - Kenneth A. Ross, Charles R. B. Wright
• Introductory Combinatorics - Richard Brualdi

Do zaciekawienia:

http://www.deltami.edu.pl/temat/matematyka/kombinatoryka/2011/06/21/Kolorowe_czapeczki/

Będziemy się zajmować tym drugim rodzajem