必修課程介紹

• 預備知識：微積分
• 適合年級： 大二
• 課程簡介：

「離散數學」亦稱「組合數學」。自遠古數學活動肇始之初，算術與幾何便分別代表了離散與連續觀念的源頭。兩種思維方式相互的辯證發展，造就了內容繽紛的數學世界。但自牛頓開創微積分學以後，以分析為首的連續性數學獨領風騷近三百年之久。今日所謂離散數學的若干題材，雖然可在數論、代數、機率、初等幾何等學科中，發現其萌芽之跡，但終未能成氣候。甚至有侷限於益智遊戲形式，是理論深度未被辨識的研究課題。

本世紀以來，離散的工具與方法，逐漸在廣泛的學科中，被發展及使用起來。因此慢慢產生出新的焦點，以及新的學科意識。一些彼此關連掛鉤的研究領域，開始匯聚在離散數學（或稱組合數學）這張大傘之下來了。特別自三十年代以後，計算科學在理論與實用上都有突破性的發展。電子計算機這種能力巨大的資訊處理工具，把人類文明帶入一個嶄新的階段。它不僅提供了生活的方便，更深深影響人的思惟方式與知識發展的進步。計算機必須通過離散的表徵才能處理資訊，古典連續數學經由它的離散化，反而產生了深刻的離散問題，同時彰顯了離散現象的重要性。此外，計算機幫助人處理極大量的有限數及有限結構，踏入前人無法想像的天地，更開展了新意義、新層次的問題以供研究。

• 課程大綱：

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)

• 參考書目：

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