Introduction to Combinatorics COM1

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.

Homework sets:
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,