6125021 Introduction to Combinatorics

Lecturer: Prof. Zichen Xu

Email: zichenxu@outlook.com

Location: Graduate School Build 113

Time: Wednesday (Wed) 3:45PM-6:10PM

Open office time: Wednesday (Wed) 2:00PM-3:30PM, IEB A608-B


  1. Applied Combinatorics, online edition, by Mitchel T. Keller and William T. Trotter
  2. Applied Combinatorics, 6th edition, by Alan Tucker

Help Documents:

Markdown Cheatsheet


Combinatorics and discrete mathematics are increasingly important, particularly for their applications in computer science. This course will give a brief overview of this subject.

Topic List

  1. Introduction to Combinatorics: factorials, permutations and combinations, binomial coefficients, Stirling numbers, double counting;
  2. Induction and Combinatorics Basics: bijections, binomial theorem, generating functions;
  3. Graph theory: bridges of Konigsberg, Eulerian circuits, trees, edge coloring, vertex coloring, planar graphs, Kempe's proof of the 5-color theorem;
  4. Network flows: sphere packing bound, Hamming codes;
  5. Graphic algorithms: Djkstra's algorithm for minimum spanning tree, depth first and breadth first algorithms for trees, greedy algorithm for graph coloring


Roughly a few questions will be asked randomly at the end of one lecture in two weeks. Each homework takes one or two weeks to finish.



Topic Handout




Lecture 1

Lecture 2

Lecture 3

Lecture 4

Lecture 5

Lecture 6


Homework 1

Homework 2, due 11:59PM Sep. 17th, 2019

Homework 3, due 11:59PM Nov. 5th, 2019