Combinatorics (Fall 2010)
This is the page for the class Combinatorics for the Fall 2010 semester. Students who take this class should check this page periodically for content updates and new announcements.
Announcement
- (2010/09/15) 第一次作业已发布,9月25日课上交。
- (2010/09/15) 第二课的lecture notes和slides中有个错误,
- [math]\displaystyle{ |U|-\sum_{I\subseteq\{1,\ldots,n\}}(-1)^{|I|}\left|\bigcap_{i\in I}A_i\right| }[/math] 的正负号有误,应为 [math]\displaystyle{ |U|+\sum_{I\subseteq\{1,\ldots,n\}}(-1)^{|I|}\left|\bigcap_{i\in I}A_i\right| }[/math] 或 [math]\displaystyle{ |U|-\sum_{I\subseteq\{1,\ldots,n\}}(-1)^{|I|-1}\left|\bigcap_{i\in I}A_i\right| }[/math]。
- 感谢林文敏同学发现这个错误。
- (2010/09/11) 前两节课slides已上传,在lecture notes的部分有链接。
- 9月3日第一次课。时间:上午三、四节;地点:馆I-105。
Course info
- Instructor : 尹一通,
- email: yitong.yin@gmail.com, yinyt@nju.edu.cn, yinyt@lamda.nju.edu.cn
- office: MMW 406.
- Class meeting: 10am-12 am, Friday; 馆I-105.
- Office hour: 2-5pm, Saturday; MMW 406.
Syllabus
先修课程 Prerequisites
- 离散数学(Discrete Mathematics)
- 线性代数(Linear Algebra)
- 概率论(Probability Theory)
Course materials
Policies
Assignments
- (2010/9/17) Problem set 1 due on Sept 25, in class.
Lecture Notes
A tentative list of topics:
- Basic enumeration | slides
- Partitions, Sieve methods | slides
- Generating functions | slides
- The probabilistic method
- Random graphs
- Extremal graph theory
- Finite set systems
- Extremal set theory
- Ramsey theory
- Optimization
- Duality
- Flow and matching
- Matroid
- Spectra of graphs
- Harmonic analysis of boolean functions
- The Szemeredi regularity lemma
- Sum-product theorems, Kakeya set
Concepts
- Binomial coefficient
- Composition of a number
- Combinations with repetition, [math]\displaystyle{ k }[/math]-multisets on a set
- Stirling number of the second kind
- Partition of a number
- The twelvefold way
- Ferrers diagram (and the MathWorld link)
- The principle of inclusion-exclusion (and more generally the sieve method)
- Derangement, and Problème des ménages