Introduction to Combinatorics COM1

Instructor:  Dr. Gábor LIPPNER
Text: handouts and Miklós Bóna: A walk through combinatorics

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, recurrences involving more than one sequence, the method of generating functions, Catalan numbers).

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, Euler's theorem on planar graphs, regular polyhedra).

Pigeonhole principle and Ramsey theory (Ramsey's theorem, bounds on Ramsey numbers, applications).