Type of Credit: Partially Required
Credit(s)
Number of Students
This is the first half of a one-year course which has the aim of giving an introduction into combinatorics, a relativ new area of mathematics. Even though some of its problems have been investigated many centuries ago, a systematic development as an independent area of mathematics has started in the middle of the last century (with the notable exception of Graph Theory). Modern combinatorics uses tools from many other areas of mathematics, e.g., topology, algebra, probability theory, analysis, etc. It has many applications, notable in Computer Science, Information Theory, Probability Theory and Biology.
能力項目說明
Getting aquainted with some of the basic tools, theorems and subareas of Combinatorics; the first semester will focus on enumerative and analytic combinatorics, the second semester will focus on graph theory and extremal combinatorics.
| 教學週次Course Week | 彈性補充教學週次Flexible Supplemental Instruction Week | 彈性補充教學類別Flexible Supplemental Instruction Type |
|---|---|---|
In-class Hours: 3; Outside-of-class Hours: 3
Syllabus:
1. The principle of inclusion-exclusion and inversion formulae
2. Lattices and Moebius inversion I
3. Lattices and Moebius inversion II
4. Elementary counting and Stirling numbers
5. Recursions and generating functions I
6. Recursions and generating functions II
7. Partitions
8. Midterm Exam
9. Asymptotics and combinatorics
10. Real-analytic asymptotics I
11. Real-analytic asymptotics II
12. Complex analysis and combinatorics
13. Exponential growth and rational asymptotics
14. Meromorphic asymptotics
15. Singularity analysis of generating functions I
16. Singularity analysis of generating functions II
17. Final exam
Weekly Homework Assignments: 60%
Midterm Exam: 20%
Final Exam: 20%
P. Flajolet and R. Sedgewick. Analytic Combinatorics, Cambridge University Press, 2009
| 書名 Book Title | 作者 Author | 出版年 Publish Year | 出版者 Publisher | ISBN | 館藏來源* | 備註 Note |
|---|