Instructor: Dr. Dezső Miklós
Text: handouts and Miklós Bóna: A walk through combinatorics
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, the number of objects having exactly m properties).
Introductory graph theory (quick overview of fundamental concepts, connectedness, graph coloring, trees; Cayley's theorem on the number of trees).
Pigeonhole principle and Ramsey theory (Ramsey's theorem, bounds on Ramsey numbers, applications).
Symmetric combinatorial structures, block designs (definition, latin squares, finite projective planes).
Since finally it is decided that a slower pace version of Combinatorics 1 will be launched as well, this syllabus is considered as the syllabus of the fast track Combinatorics 1 course. See Combinatorics 1B for the alternative choice.
HW 1, HW 2, HW 3, HW 2, new version, HW 4, HW 5, HW 6, Sample midterm, HW 8, HW 9, HW 10, HW 11, HW 12, HW 13,