Instructor: Dr. Attila SALI
Text: handouts and Miklós Bóna: A walk through
combinatorics (available digitally here)
Topics:
Basic counting rules (product rule, sum rule, permutations, combinations, Pascal's triangle, occupancy problems, distribution problems, Stirling numbers).
Generating functions (definition, operations on generating functions, applications to counting, binomial theorem, exponential generating functions).
Recurrences (Fibonacci numbers, derangements, the method of generating functions).
Principle of inclusion and exclusion (the principle and applications, occupancy problems with distinguishable balls and cells, derangements).
Graph theory taster(overview of fundamental concepts, connectedness, graph coloring, trees, Cayley's Theorem on the number of trees, Eulerian circuits and their applications: de Bruijn cycles, planar graphs).
Pigeonhole principle and Ramsey theory (Ramsey's theorem, bounds on Ramsey numbers, applications).
Two fundamental theorems on set systems: Erdös-Ko-Rado Theorem and Sperner's Theorem