Course Introduction

• Prerequisite：Calculus
• Recommended for： sophomore
• Introduction：

Discrete Mathematics, or called Combinatorics, is an important branch of Mathematics, and its influence continues to expand. Part of the reason for tremendous growth of Combinatorics is the development of computer, which needs combinatorial thinking to perform and analyze its correct and efficient functioning. Another reason for the recent growth of Combinatorics is its ideas and techniques applicable to many areas, for example, the physical sciences, the social sciences, the biological sciences, information theory and so on. This course prepares students the ability concerned with the existence, enumeration, analysis and optimization of discrete structure.

• Syllabus：

1. The Pigeonhole Principle and Ramsey Theorem
2. Permutations and Combinations
3. Partially Ordered Set and Equivalence Relations
4. The Binomial Theorem and Identities
5. The Inclusion-Exclusion Principle and Mobius Inversion
6. Recurrence Relations
7. Generating Functions
8. Special Counting Sequence
9. Combinatorial Designs (optimal)
10. Basic Graph Theory (optional)
11. Pólya Counting (optimal)

• Reference：

1. R. A. Brualdi: Introductory Combinatorics (Fifth Edition), 5th ed., Pearson Prentice Hall (2010).