Instructor: Dr. Dezső MIKLÓS
Text: classnote 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, 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).
Homework sets:
info sheet,
Classnotes, Halcyon Derks: Principle of Inclusion/exclusion and the sieve TeX,
Chris Domenicali: Linear homogeneous recurrence relations,
Eli Melaas: An analysis of generating functions,
HW 1, HW 1 TeX,
HW 2, HW 2 TeX,
HW 3, HW 3 TeX,
HW 4, HW 4 TeX,
HW 5, HW 5 TeX,
Catalan numbers,
HW 6, HW 6 TeX,
HW 7, HW 7 TeX,
HW 8, HW 8 TeX,
HW 9, HW 9 TeX,
HW 10, HW 10 TeX,
HW 11, HW 11 TeX,
HW 12, HW 12 TeX,
HW 13, HW 13 TeX,
HW extra, HW extra TeX,
additional text for BIBD's additional text for projective planes
-->