• Instructor : M. Rajesh Kannan
• Instructor's mail id : rajeshkannan@math.iith.ac.in
• Class Schedule: Monday 11am-11.55am; Wednesday 10am-10.55am; Thursday 9.00am-9.55am (C-slot).
• Venue: MA ??
• Office hours: By appointment (MA201).

Tentative Syllabus

• Basic Counting: sum rule, product rule and inclusion-exclusion principle.
• Pigeon hole principle, generalized pigeon hole principle and its applications.
• Permutation and Combinations. Permutation and combinations with repetitions, binomial and multinomial coefficients.
• Weak compositions, compositions, set partitions, Stirling numbers, Bell numbers. Integer partition, Ferrer's shape, conjugate partitions. Catalan numbers.
• Recurrence relations. Solving linear recurrence relations with constant coefficients.
• Ordinary generating functions, exponential generating functions. Solving recurrence relations using generating functions.
• Burnside's lemma. Linear Algebraic methods in combinatorics.
• Basics of graphs, isomorphism, trees, Minimum spanning tree, Kruskal's algorithm.
• Counting spanning trees, Prufer sequence, Cayley's formula, Matrix-tree theorem (without proof).
• Mantel's theorem. Bipartite graphs, Matching, Hall's theorem, System of distinct representatives.
• Eulerian graphs, Decompositions, Graham and Pollak theorem, Veblen's theorem.
• Hamiltonian graphs, Ore's theorem.
• Planer graphs, Euler's formula and its applications.
• Chromatic number, Five color theorem.