離散數學
Discrete Mathematics
| 節 | 週二 | 週四 |
|---|---|---|
2 09:00–09:50 | 離散數學 SA320（光復） | |
5 13:20–14:10 | 離散數學 SA320（光復） 2 節連堂 | |
6 14:20–15:10 |
* 根據陽明交大上課時間表所列
Course description: This is an introduction to discrete mathematics, an area that studies finite sets and their relations. It has many applications in and connections with other topics in mathematics and beyond, including computer science. The main emphases of this course are on techniques of counting and basic combinatorial structures.
Calculus I, Linear Algebra I
無備註
Use e3 system.
10% appearance, 30% homework, 30% midterm, 30% final.
1. What is Combinatorics
Introduction to combinatorics and combinatorial reasoning from examples
2. Permutations and Combinations
Basic counting principles, permutations and combinations of finite sets and multisets
3.The Pigeonhole Principle
Pigeonhole principle and its applications, basic Ramsey theory
4. The Binomial Coefficients
Binomial coefficients and their properties, binomial and multinomial theorems
5. The Inclusion-Exclusion Principle
Inclusion-exclusion principle and its applications, counting with repetitions
6. Recurrence Relations and Generating Functions
Recurrence relations in combinatorics, ordinary and exponential generating functions, solving linear recurrence relations
7. Special Counting Sequences
Catalan numbers, Stirling numbers, partition numbers
8. Partially ordered sets and other relations
Partial orders and equivalence relations, Mirsky and Dilworth theorems
9. Introduction to Graph Theory*
Basic terminology, trees, minimum spanning trees and algorithms, counting spanning trees
備註：時間允許
| 週次 | 主題 |
|---|---|
| 第 1 週 | Introduction to combinatorics with examples; counting principles 2024-02-20(二),2024-02-22(四) |
| 第 2 週 | Permutations and combinations of finite sets, permutations of multisets 2024-02-27(二),2024-02-29(四) |
| 第 3 週 | Combinations of special multisets; generating permutations, combinations, and subsets 2024-03-05(二),2024-03-07(四) |
| 第 4 週 | Pigeonhole principle (simple form and strong form) and examples; introduction to Ramsey theory 2024-03-12(二),2024-03-14(四) |
| 第 5 週 | Ramsey theory (cont.), binomial coefficients and theorem, binomial identities, generalized binomial theorem 2024-03-19(二),2024-03-21(四) |
| 第 6 週 | Multinomial theorem; inclusion-exclusion principle and examples, combinations of multisets, derangements 2024-03-26(二),2024-03-28(四) |
| 第 7 週 | Fibonacci sequence as an example of recurrence sequences and generating functions 2024-04-02(二),2024-04-04(四) |
| 第 8 週 | More on Fibonacci sequence; Midterm 11/4 2024-04-09(二),2024-04-11(四) |
| 第 9 週 | Ordinary and exponential generating functions 2024-04-16(二),2024-04-18(四) |
| 第 10 週 | Exponential generating function of derangement numbers; homogeneous linear recurrence 2024-04-23(二),2024-04-25(四) |
| 第 11 週 | Non-homogeneous linear recurrence; Catalan numbers 2024-04-30(二),2024-05-02(四) |
| 第 12 週 | Stirling numbers and the twelvefold way 2024-05-07(二),2024-05-09(四) |
| 第 13 週 | Partition numbers; equivalence relation and basic poset theory 2024-05-14(二),2024-05-16(四) |
| 第 14 週 | Mirsky and Dilworth theorems; basic notions in graph theory 2024-05-21(二),2024-05-23(四) |
| 第 15 週 | Minimum spanning trees and Kruskal's algorithm; Matrix-Tree Theorem, Cayley formula and Prufer sequences 2024-05-28(二),2024-05-30(四) |
| 第 16 週 | Final exam 6/6 2024-06-04(二),2024-06-06(四) |
R. A. Brualdi, Introductory Combinatorics, 5th Edition, PEARSON
- 地點
- SA341
- 時間
- Send an e-mail to me to make appointment (not available: M78, R34)
- 聯絡方式
- chyuen@math.nctu.edu.tw