TCS Wiki - User contributions [en]

组合数学 (Spring 2025)/第四次作业提交名单

2025-06-19T10:13:53Z

Gispzjz: Created page with "如有错漏请邮件联系助教. <center> {| class="wikitable" |- ! 学号 !! 姓名 |- | 211220166 || 王诚昊 |- | 211830008 || 缪天顺 |- | 221180133 || 黄可唯 |- | 221220002 || 沈均文 |- | 221220022 || 颜树 |- | 221220029 || 陈俊翰 |- | 221220034 || 王旭 |- | 221220095 || 曾凡俊 |- | 221220104 || 刘宇平 |- | 221220111 || 于源智 |- | 221220123 || 董立伟 |- | 221240035 || 李想 |- | 221240073 || 李恒济 |- | 221300016 ||..."

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 211220166 || 王诚昊
|-
| 211830008 || 缪天顺
|-
| 221180133 || 黄可唯
|-
| 221220002 || 沈均文
|-
| 221220022 || 颜树
|-
| 221220029 || 陈俊翰
|-
| 221220034 || 王旭
|-
| 221220095 || 曾凡俊
|-
| 221220104 || 刘宇平
|-
| 221220111 || 于源智
|-
| 221220123 || 董立伟
|-
| 221240035 || 李想
|-
| 221240073 || 李恒济
|-
| 221300016 || 白皓瑀
|-
| 221502002 || 严宇恒
|-
| 221502003 || 张天钰
|-
| 221502005 || 王昕浩
|-
| 221502007 || 崔毓泽
|-
| 221502010 || 梁志浩
|-
| 221502013 || 贺龄瑞
|-
| 221502017 || 卢君和
|-
| 221502021 || 李尚敖
|-
| 221840201 || 钟锦立
|-
| 221840207 || 陈逸迪
|-
| 221900059 || 王齐剑
|-
| 221900156 || 韩加瑞
|-
| 221900500 || 李亦非
|-
| 231220012 || 张启越
|-
| 231220073 || 李世昌
|-
| 231300059 || 阮一海
|-
| 231300084 || 柴梓涵
|-
| 231502022 || 胡骏秋
|-
| 231830106 || 朱逸宸
|-
| 231840164 || 高旭
|-
| 231840288 || 魏丽轩
|-
| 502024330019 || 黄锐
|-
| 502024330020 || 蒋承欢
|-
| 502024330065 || 张天泽
|-
| 502024330075 || 周灿
|-
| 522024330036 || 李尚达
|-
| 522024330112 || 叶佳
|-
| 522024330118 || 张弛
|-
| 522024330144 || 刘学彬
|-
| 652024330035 || 杨宇轩
|-
| DZ1833024 || 王竞冕
|-
|}
</center>

组合数学 (Spring 2025)

2025-06-19T10:13:48Z

Gispzjz: /* Assignments */

{{Infobox
|name = Infobox
|bodystyle =
|title = 组合数学 
Combinatorics
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = Wednesday, 2pm-4pm 逸A-322
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = TBA 计算机系 804
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = [[File:LW-combinatorics.jpeg|border|100px]]
|header11 =
|label11 =
|data11 = van Lint and Wilson. ''A course in Combinatorics, 2nd ed.'', Cambridge Univ Press, 2001.
|header12 =
|label12 =
|data12 = [[File:Jukna_book.jpg|border|100px]]
|header13 =
|label13 =
|data13 = Jukna. ''Extremal Combinatorics: With Applications in Computer Science, 2nd ed.'', Springer, 2011.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Combinatorics'' class of Spring 2025. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* '''(2025/03/18)''' 第一次作业已发布，请在 2025/04/02 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A1.pdf')
* '''(2025/04/09)''' 第二次作业已发布，请在 2025/04/23 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A2.pdf')
* '''(2025/05/07)''' 第三次作业已发布，请在 2025/05/28 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A3.pdf')
* '''(2025/06/04)''' 第四次作业已发布，请在 2025/06/18 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A4.pdf')

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** [https://lhy-gispzjz.github.io 刘弘洋] ([mailto:liuhongyang@smail.nju.edu.cn liuhongyang@smail.nju.edu.cn])
** 丁天行
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-322.
* '''Office hour''': TBA
:* '''QQ群''': 260501949 (加入时需报姓名、专业、学号)

= Syllabus =

=== 先修课程 Prerequisites ===
* 离散数学（Discrete Mathematics）
* 线性代数（Linear Algebra）
* 概率论（Probability Theory）

=== Course materials ===
* [[组合数学 (Spring 2025)/Course materials|教材和参考书清单]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
* [[组合数学 (Spring 2025)/Problem Set 1|Problem Set 1]] [[组合数学 (Spring 2025)/第一次作业提交名单|第一次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 2|Problem Set 2]] [[组合数学 (Spring 2025)/第二次作业提交名单|第二次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 3|Problem Set 3]] [[组合数学 (Spring 2025)/第三次作业提交名单|第三次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 4|Problem Set 4]] [[组合数学 (Spring 2025)/第四次作业提交名单|第四次作业提交名单]]

= Lecture Notes =
# [[组合数学 (Spring 2025)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2025/BasicEnumeration.pdf slides])
# [[组合数学 (Fall 2025)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2025/GeneratingFunction.pdf slides])
# [[组合数学 (Fall 2025)/Sieve methods|Sieve methods | 筛法]] ([http://tcs.nju.edu.cn/slides/comb2025/PIE.pdf slides])
# [[组合数学 (Fall 2025)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] ([http://tcs.nju.edu.cn/slides/comb2025/Polya.pdf slides])
# [[组合数学 (Fall 2025)/Cayley's formula|Cayley's formula | Cayley公式]] ([http://tcs.nju.edu.cn/slides/comb2025/Cayley.pdf slides])
# [[组合数学 (Fall 2025)/Existence problems|Existence problems | 存在性问题]] ([http://tcs.nju.edu.cn/slides/comb2025/Existence.pdf slides])
# [[组合数学 (Fall 2025)/The probabilistic method|The probabilistic method | 概率法]] ([http://tcs.nju.edu.cn/slides/comb2025/ProbMethod.pdf slides])
# [[组合数学 (Fall 2025)/Extremal graph theory|Extremal graph theory | 极值图论]] ([http://tcs.nju.edu.cn/slides/comb2025/ExtremalGraphs.pdf slides])
# [[组合数学 (Fall 2025)/Extremal set theory|Extremal set theory | 极值集合论]]（[http://tcs.nju.edu.cn/slides/comb2024/ExtremalSets.pdf slides]）
#* [https://mathweb.ucsd.edu/~ronspubs/90_03_erdos_ko_rado.pdf Old and new proofs of the Erdős–Ko–Rado theorem] by Frankl and Graham
#* [https://arxiv.org/pdf/1908.08483.pdf Improved bounds for the sunflower lemma] by Alweiss-Lovet-Wu-Zhang and a [https://arxiv.org/pdf/1909.04774.pdf simplified proof] by Rao
# [[组合数学 (Fall 2025)/Ramsey theory|Ramsey theory | Ramsey理论]]（[http://tcs.nju.edu.cn/slides/comb2024/Ramsey.pdf slides]）
# [[组合数学 (Fall 2025)/Matching theory|Matching theory | 匹配论]]（[http://tcs.nju.edu.cn/slides/comb2024/Matchings.pdf slides]）

= Resources =
* [http://math.mit.edu/~fox/MAT307.html Combinatorics course] by Jacob Fox
* [https://yufeizhao.com/pm/ Probabilistic Methods in Combinatorics] and [https://yufeizhao.com/gtacbook/ Graph Theory and Additive Combinatorics] by Yufei Zhao
* [https://www.math.uvic.ca/~noelj/combinatoricsLectures.html Combinatorics Lecture Videos online]
* [https://www.math.ucla.edu/~pak/lectures/Math-Videos/comb-videos.htm Collection of Combinatorics Videos]

= Concepts =
* [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient]
* [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way]
* [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number]
* [http://en.wikipedia.org/wiki/Multiset#Formal_definition Multiset]
* [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset#Counting_multisets <math>k</math>-multisets on a set]
* [http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients Multinomial coefficients]
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind]
* [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number]
** [http://en.wikipedia.org/wiki/Young_tableau Young tableau]
* [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]
* [http://en.wikipedia.org/wiki/Catalan_number Catalan number]
* [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series]
* [http://en.wikipedia.org/wiki/Binomial_series Newton's formula]
* [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method])
* [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius inversion formula]
* [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages]
* [http://en.wikipedia.org/wiki/Ryser%27s_formula#Ryser_formula Ryser's formula]
* [http://en.wikipedia.org/wiki/Euler_totient Euler totient function]
* [https://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside's lemma]
** [https://en.wikipedia.org/wiki/Group_action Group action]
** [https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers Orbits]
* [https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Pólya enumeration theorem]
** [https://en.wikipedia.org/wiki/Permutation_group Permutation group]
** [https://en.wikipedia.org/wiki/Cycle_index Cycle index]
* [http://en.wikipedia.org/wiki/Cayley_formula Cayley's formula]
** [http://en.wikipedia.org/wiki/Prüfer_sequence Prüfer code for trees]
** [http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem Kirchhoff's matrix-tree theorem]
* [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma]
* [http://en.wikipedia.org/wiki/Sperner's_lemma Sperner's lemma] and [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer fixed point theorem]
* [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
:* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem]
* [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method]
* [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs]
* [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
* [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
* Two analytic inequalities:
:*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
:* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
* [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower lemma and conjecture]
* [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
* [https://en.wikipedia.org/wiki/Sperner%27s_theorem Sperner's theorem]
** [https://en.wikipedia.org/wiki/Sperner_family Sperner system] or '''antichain'''
* [https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma Sauer–Shelah lemma]
** [https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension Vapnik–Chervonenkis dimension]
* [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal–Katona theorem]
* [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
:*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
:*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
:*[https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem Van der Waerden's theorem]
:*[https://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem Hales–Jewett theorem]
* [https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem Hall's theorem ] (the marriage theorem)
:* [https://en.wikipedia.org/wiki/Doubly_stochastic_matrix Birkhoff–Von Neumann theorem]
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
* [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
* The [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
:* [https://en.wikipedia.org/wiki/Menger%27s_theorem Menger's theorem]
:* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]
* [https://en.wikipedia.org/wiki/Linear_programming Linear programming]
** [https://en.wikipedia.org/wiki/Dual_linear_program Duality]
** [https://en.wikipedia.org/wiki/Unimodular_matrix Unimodularity]
* [https://en.wikipedia.org/wiki/Matroid Matroid]

组合数学 (Spring 2025)

2025-06-04T05:06:17Z

Gispzjz: /* Announcement */

{{Infobox
|name = Infobox
|bodystyle =
|title = 组合数学 
Combinatorics
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = Wednesday, 2pm-4pm 逸A-322
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = TBA 计算机系 804
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = [[File:LW-combinatorics.jpeg|border|100px]]
|header11 =
|label11 =
|data11 = van Lint and Wilson. ''A course in Combinatorics, 2nd ed.'', Cambridge Univ Press, 2001.
|header12 =
|label12 =
|data12 = [[File:Jukna_book.jpg|border|100px]]
|header13 =
|label13 =
|data13 = Jukna. ''Extremal Combinatorics: With Applications in Computer Science, 2nd ed.'', Springer, 2011.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Combinatorics'' class of Spring 2025. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* '''(2025/03/18)''' 第一次作业已发布，请在 2025/04/02 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A1.pdf')
* '''(2025/04/09)''' 第二次作业已发布，请在 2025/04/23 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A2.pdf')
* '''(2025/05/07)''' 第三次作业已发布，请在 2025/05/28 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A3.pdf')
* '''(2025/06/04)''' 第四次作业已发布，请在 2025/06/18 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A4.pdf')

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** [https://lhy-gispzjz.github.io 刘弘洋] ([mailto:liuhongyang@smail.nju.edu.cn liuhongyang@smail.nju.edu.cn])
** 丁天行
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-322.
* '''Office hour''': TBA
:* '''QQ群''': 260501949 (加入时需报姓名、专业、学号)

= Syllabus =

=== 先修课程 Prerequisites ===
* 离散数学（Discrete Mathematics）
* 线性代数（Linear Algebra）
* 概率论（Probability Theory）

=== Course materials ===
* [[组合数学 (Spring 2025)/Course materials|教材和参考书清单]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
* [[组合数学 (Spring 2025)/Problem Set 1|Problem Set 1]] [[组合数学 (Spring 2025)/第一次作业提交名单|第一次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 2|Problem Set 2]] [[组合数学 (Spring 2025)/第二次作业提交名单|第二次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 3|Problem Set 3]] [[组合数学 (Spring 2025)/第三次作业提交名单|第三次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 4|Problem Set 4]]

= Lecture Notes =
# [[组合数学 (Spring 2025)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2025/BasicEnumeration.pdf slides])
# [[组合数学 (Fall 2025)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2025/GeneratingFunction.pdf slides])
# [[组合数学 (Fall 2025)/Sieve methods|Sieve methods | 筛法]] ([http://tcs.nju.edu.cn/slides/comb2025/PIE.pdf slides])
# [[组合数学 (Fall 2025)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] ([http://tcs.nju.edu.cn/slides/comb2025/Polya.pdf slides])
# [[组合数学 (Fall 2025)/Cayley's formula|Cayley's formula | Cayley公式]] ([http://tcs.nju.edu.cn/slides/comb2025/Cayley.pdf slides])
# [[组合数学 (Fall 2025)/Existence problems|Existence problems | 存在性问题]] ([http://tcs.nju.edu.cn/slides/comb2025/Existence.pdf slides])
# [[组合数学 (Fall 2025)/The probabilistic method|The probabilistic method | 概率法]] ([http://tcs.nju.edu.cn/slides/comb2025/ProbMethod.pdf slides])
# [[组合数学 (Fall 2025)/Extremal graph theory|Extremal graph theory | 极值图论]] ([http://tcs.nju.edu.cn/slides/comb2025/ExtremalGraphs.pdf slides])
# [[组合数学 (Fall 2025)/Extremal set theory|Extremal set theory | 极值集合论]]（[http://tcs.nju.edu.cn/slides/comb2024/ExtremalSets.pdf slides]）
#* [https://mathweb.ucsd.edu/~ronspubs/90_03_erdos_ko_rado.pdf Old and new proofs of the Erdős–Ko–Rado theorem] by Frankl and Graham
#* [https://arxiv.org/pdf/1908.08483.pdf Improved bounds for the sunflower lemma] by Alweiss-Lovet-Wu-Zhang and a [https://arxiv.org/pdf/1909.04774.pdf simplified proof] by Rao
# [[组合数学 (Fall 2025)/Ramsey theory|Ramsey theory | Ramsey理论]]（[http://tcs.nju.edu.cn/slides/comb2024/Ramsey.pdf slides]）

= Resources =
* [http://math.mit.edu/~fox/MAT307.html Combinatorics course] by Jacob Fox
* [https://yufeizhao.com/pm/ Probabilistic Methods in Combinatorics] and [https://yufeizhao.com/gtacbook/ Graph Theory and Additive Combinatorics] by Yufei Zhao
* [https://www.math.uvic.ca/~noelj/combinatoricsLectures.html Combinatorics Lecture Videos online]
* [https://www.math.ucla.edu/~pak/lectures/Math-Videos/comb-videos.htm Collection of Combinatorics Videos]

= Concepts =
* [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient]
* [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way]
* [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number]
* [http://en.wikipedia.org/wiki/Multiset#Formal_definition Multiset]
* [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset#Counting_multisets <math>k</math>-multisets on a set]
* [http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients Multinomial coefficients]
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind]
* [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number]
** [http://en.wikipedia.org/wiki/Young_tableau Young tableau]
* [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]
* [http://en.wikipedia.org/wiki/Catalan_number Catalan number]
* [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series]
* [http://en.wikipedia.org/wiki/Binomial_series Newton's formula]
* [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method])
* [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius inversion formula]
* [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages]
* [http://en.wikipedia.org/wiki/Ryser%27s_formula#Ryser_formula Ryser's formula]
* [http://en.wikipedia.org/wiki/Euler_totient Euler totient function]
* [https://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside's lemma]
** [https://en.wikipedia.org/wiki/Group_action Group action]
** [https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers Orbits]
* [https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Pólya enumeration theorem]
** [https://en.wikipedia.org/wiki/Permutation_group Permutation group]
** [https://en.wikipedia.org/wiki/Cycle_index Cycle index]
* [http://en.wikipedia.org/wiki/Cayley_formula Cayley's formula]
** [http://en.wikipedia.org/wiki/Prüfer_sequence Prüfer code for trees]
** [http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem Kirchhoff's matrix-tree theorem]
* [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma]
* [http://en.wikipedia.org/wiki/Sperner's_lemma Sperner's lemma] and [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer fixed point theorem]
* [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
:* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem]
* [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method]
* [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs]
* [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
* [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
* Two analytic inequalities:
:*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
:* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
* [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower lemma and conjecture]
* [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
* [https://en.wikipedia.org/wiki/Sperner%27s_theorem Sperner's theorem]
** [https://en.wikipedia.org/wiki/Sperner_family Sperner system] or '''antichain'''
* [https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma Sauer–Shelah lemma]
** [https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension Vapnik–Chervonenkis dimension]
* [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal–Katona theorem]
* [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
:*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
:*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
:*[https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem Van der Waerden's theorem]
:*[https://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem Hales–Jewett theorem]
* [https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem Hall's theorem ] (the marriage theorem)
:* [https://en.wikipedia.org/wiki/Doubly_stochastic_matrix Birkhoff–Von Neumann theorem]
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
* [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
* The [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
:* [https://en.wikipedia.org/wiki/Menger%27s_theorem Menger's theorem]
:* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]
* [https://en.wikipedia.org/wiki/Linear_programming Linear programming]
** [https://en.wikipedia.org/wiki/Dual_linear_program Duality]
** [https://en.wikipedia.org/wiki/Unimodular_matrix Unimodularity]
* [https://en.wikipedia.org/wiki/Matroid Matroid]

组合数学 (Spring 2025)

2025-06-04T05:06:08Z

Gispzjz: /* Announcement */

{{Infobox
|name = Infobox
|bodystyle =
|title = 组合数学 
Combinatorics
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = Wednesday, 2pm-4pm 逸A-322
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = TBA 计算机系 804
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = [[File:LW-combinatorics.jpeg|border|100px]]
|header11 =
|label11 =
|data11 = van Lint and Wilson. ''A course in Combinatorics, 2nd ed.'', Cambridge Univ Press, 2001.
|header12 =
|label12 =
|data12 = [[File:Jukna_book.jpg|border|100px]]
|header13 =
|label13 =
|data13 = Jukna. ''Extremal Combinatorics: With Applications in Computer Science, 2nd ed.'', Springer, 2011.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Combinatorics'' class of Spring 2025. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* '''(2025/03/18)''' 第一次作业已发布，请在 2025/04/02 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A1.pdf')
* '''(2025/04/09)''' 第二次作业已发布，请在 2025/04/23 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A2.pdf')
* '''(2025/05/07)''' 第二次作业已发布，请在 2025/05/28 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A3.pdf')
* '''(2025/06/04)''' 第二次作业已发布，请在 2025/06/18 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A4.pdf')

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** [https://lhy-gispzjz.github.io 刘弘洋] ([mailto:liuhongyang@smail.nju.edu.cn liuhongyang@smail.nju.edu.cn])
** 丁天行
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-322.
* '''Office hour''': TBA
:* '''QQ群''': 260501949 (加入时需报姓名、专业、学号)

= Syllabus =

=== 先修课程 Prerequisites ===
* 离散数学（Discrete Mathematics）
* 线性代数（Linear Algebra）
* 概率论（Probability Theory）

=== Course materials ===
* [[组合数学 (Spring 2025)/Course materials|教材和参考书清单]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
* [[组合数学 (Spring 2025)/Problem Set 1|Problem Set 1]] [[组合数学 (Spring 2025)/第一次作业提交名单|第一次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 2|Problem Set 2]] [[组合数学 (Spring 2025)/第二次作业提交名单|第二次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 3|Problem Set 3]] [[组合数学 (Spring 2025)/第三次作业提交名单|第三次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 4|Problem Set 4]]

= Lecture Notes =
# [[组合数学 (Spring 2025)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2025/BasicEnumeration.pdf slides])
# [[组合数学 (Fall 2025)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2025/GeneratingFunction.pdf slides])
# [[组合数学 (Fall 2025)/Sieve methods|Sieve methods | 筛法]] ([http://tcs.nju.edu.cn/slides/comb2025/PIE.pdf slides])
# [[组合数学 (Fall 2025)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] ([http://tcs.nju.edu.cn/slides/comb2025/Polya.pdf slides])
# [[组合数学 (Fall 2025)/Cayley's formula|Cayley's formula | Cayley公式]] ([http://tcs.nju.edu.cn/slides/comb2025/Cayley.pdf slides])
# [[组合数学 (Fall 2025)/Existence problems|Existence problems | 存在性问题]] ([http://tcs.nju.edu.cn/slides/comb2025/Existence.pdf slides])
# [[组合数学 (Fall 2025)/The probabilistic method|The probabilistic method | 概率法]] ([http://tcs.nju.edu.cn/slides/comb2025/ProbMethod.pdf slides])
# [[组合数学 (Fall 2025)/Extremal graph theory|Extremal graph theory | 极值图论]] ([http://tcs.nju.edu.cn/slides/comb2025/ExtremalGraphs.pdf slides])
# [[组合数学 (Fall 2025)/Extremal set theory|Extremal set theory | 极值集合论]]（[http://tcs.nju.edu.cn/slides/comb2024/ExtremalSets.pdf slides]）
#* [https://mathweb.ucsd.edu/~ronspubs/90_03_erdos_ko_rado.pdf Old and new proofs of the Erdős–Ko–Rado theorem] by Frankl and Graham
#* [https://arxiv.org/pdf/1908.08483.pdf Improved bounds for the sunflower lemma] by Alweiss-Lovet-Wu-Zhang and a [https://arxiv.org/pdf/1909.04774.pdf simplified proof] by Rao
# [[组合数学 (Fall 2025)/Ramsey theory|Ramsey theory | Ramsey理论]]（[http://tcs.nju.edu.cn/slides/comb2024/Ramsey.pdf slides]）

= Resources =
* [http://math.mit.edu/~fox/MAT307.html Combinatorics course] by Jacob Fox
* [https://yufeizhao.com/pm/ Probabilistic Methods in Combinatorics] and [https://yufeizhao.com/gtacbook/ Graph Theory and Additive Combinatorics] by Yufei Zhao
* [https://www.math.uvic.ca/~noelj/combinatoricsLectures.html Combinatorics Lecture Videos online]
* [https://www.math.ucla.edu/~pak/lectures/Math-Videos/comb-videos.htm Collection of Combinatorics Videos]

= Concepts =
* [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient]
* [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way]
* [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number]
* [http://en.wikipedia.org/wiki/Multiset#Formal_definition Multiset]
* [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset#Counting_multisets <math>k</math>-multisets on a set]
* [http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients Multinomial coefficients]
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind]
* [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number]
** [http://en.wikipedia.org/wiki/Young_tableau Young tableau]
* [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]
* [http://en.wikipedia.org/wiki/Catalan_number Catalan number]
* [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series]
* [http://en.wikipedia.org/wiki/Binomial_series Newton's formula]
* [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method])
* [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius inversion formula]
* [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages]
* [http://en.wikipedia.org/wiki/Ryser%27s_formula#Ryser_formula Ryser's formula]
* [http://en.wikipedia.org/wiki/Euler_totient Euler totient function]
* [https://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside's lemma]
** [https://en.wikipedia.org/wiki/Group_action Group action]
** [https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers Orbits]
* [https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Pólya enumeration theorem]
** [https://en.wikipedia.org/wiki/Permutation_group Permutation group]
** [https://en.wikipedia.org/wiki/Cycle_index Cycle index]
* [http://en.wikipedia.org/wiki/Cayley_formula Cayley's formula]
** [http://en.wikipedia.org/wiki/Prüfer_sequence Prüfer code for trees]
** [http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem Kirchhoff's matrix-tree theorem]
* [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma]
* [http://en.wikipedia.org/wiki/Sperner's_lemma Sperner's lemma] and [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer fixed point theorem]
* [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
:* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem]
* [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method]
* [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs]
* [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
* [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
* Two analytic inequalities:
:*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
:* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
* [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower lemma and conjecture]
* [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
* [https://en.wikipedia.org/wiki/Sperner%27s_theorem Sperner's theorem]
** [https://en.wikipedia.org/wiki/Sperner_family Sperner system] or '''antichain'''
* [https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma Sauer–Shelah lemma]
** [https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension Vapnik–Chervonenkis dimension]
* [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal–Katona theorem]
* [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
:*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
:*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
:*[https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem Van der Waerden's theorem]
:*[https://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem Hales–Jewett theorem]
* [https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem Hall's theorem ] (the marriage theorem)
:* [https://en.wikipedia.org/wiki/Doubly_stochastic_matrix Birkhoff–Von Neumann theorem]
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
* [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
* The [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
:* [https://en.wikipedia.org/wiki/Menger%27s_theorem Menger's theorem]
:* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]
* [https://en.wikipedia.org/wiki/Linear_programming Linear programming]
** [https://en.wikipedia.org/wiki/Dual_linear_program Duality]
** [https://en.wikipedia.org/wiki/Unimodular_matrix Unimodularity]
* [https://en.wikipedia.org/wiki/Matroid Matroid]

组合数学 (Spring 2025)/Problem Set 4

2025-06-04T05:04:38Z

Gispzjz: /* Problem 2 */

== Problem 1 ==
An <math>n</math>-player tournament (竞赛图) <math>T([n],E)</math> is said to be '''transitive''', if there exists a permutation <math>\pi</math> of <math>[n]</math> such that <math>\pi_i<\pi_j</math> for every <math>(i,j)\in E</math>.

Show that for any <math>k\ge 3</math>, there exists a finite <math>N(k)</math> such that every tournament of <math>n\ge N(k)</math> players contains a transitive sub-tournament of <math>k</math> players. Express <math>N(k)</math> in terms of Ramsey number.

== Problem 2 ==
Recall that the smallest number <math>R(k,\ell)</math> satisfying the condition in the Ramsey theory is called the '''Ramsey number'''. Prove that:
* <math>R(4,3)\leq 9</math>. (Hint: Proof by contradiction. Color the edges of <math>K_9</math> in red and blue, and assume that there are no red triangles and no blue <math>4</math>-cliques. Try to determine the number of red and blue edges adjacent to each vertex.)
* <math>R(4,4)\leq 18</math>.

== Problem 3 ==
Let <math>G</math> be a bipartite graph with bipartition <math>A,B</math>. Let <math>a</math> be the minimum degree of a vertex in <math>A</math>,and <math>b</math> the maximum degree of a vertex in <math>B</math>. Prove the following: if <math>a\geq b</math> then there exists a matching of <math>A</math> into <math>B</math>.

== Problem 4 ==
Suppose that <math>M,M'</math> are matchings in a bipartite graph <math>G</math> with bipartition <math>A,B</math>. Suppose that all the vertices of <math>S\subseteq A</math> are matched by <math>M</math> and that all the vertices of <math>T\subseteq B</math> are matched by <math>M'</math>. Prove that <math>G</math> contains a matching that matches all the vertices of <math>S \cup T</math>.

== Problem 5 ==
Use the '''König-Egerváry theorem''' to prove the followings:
* Every bipartite graph <math>G</math> with <math>l</math> edges has a matching of size at least <math>l/\Delta(G)</math>, where <math>\Delta(G)</math> is the maximum degree of a vertex in <math>G</math>.
* Let <math>A</math> be a 0-1 matrix with <math>m</math> 1s. Let <math>s</math> be the maximal number of 1s in a row or column of <math>A</math>, and suppose that <math>A</math> has no square <math>r\times r</math> all-1 sub-matrix. It requires at least <math>m/(sr)</math> all-1 (not necessarily square) sub-matrices to cover all 1s in <math>A</math>.

组合数学 (Spring 2025)/Problem Set 4

2025-06-04T05:00:39Z

Gispzjz:

== Problem 1 ==
An <math>n</math>-player tournament (竞赛图) <math>T([n],E)</math> is said to be '''transitive''', if there exists a permutation <math>\pi</math> of <math>[n]</math> such that <math>\pi_i<\pi_j</math> for every <math>(i,j)\in E</math>.

Show that for any <math>k\ge 3</math>, there exists a finite <math>N(k)</math> such that every tournament of <math>n\ge N(k)</math> players contains a transitive sub-tournament of <math>k</math> players. Express <math>N(k)</math> in terms of Ramsey number.

== Problem 2==
We color each non-empty subset of <math>[n]=\{1,2,\ldots,n\}</math> with one of the <math>r</math> colors in <math>[r]</math>. Show that for any finite <math>r</math> there is a finite <math>N</math> such that for all <math>n\ge N</math>, for any <math>r</math>-coloring of non-empty subsets of <math>[n]</math>, there always exist <math>1\le i<j<k\le n</math> such that the intervals <math>[i,j)=\{i,i+1,\ldots, j-1\}</math>, <math>[j,k)=\{j,j+1,\ldots, k-1\}</math> and <math>[i,k)=\{i,i+1,\ldots, k-1\}</math> are all assigned with the same color.

== Problem 3 ==
Let <math>G</math> be a bipartite graph with bipartition <math>A,B</math>. Let <math>a</math> be the minimum degree of a vertex in <math>A</math>,and <math>b</math> the maximum degree of a vertex in <math>B</math>. Prove the following: if <math>a\geq b</math> then there exists a matching of <math>A</math> into <math>B</math>.

== Problem 4 ==
Suppose that <math>M,M'</math> are matchings in a bipartite graph <math>G</math> with bipartition <math>A,B</math>. Suppose that all the vertices of <math>S\subseteq A</math> are matched by <math>M</math> and that all the vertices of <math>T\subseteq B</math> are matched by <math>M'</math>. Prove that <math>G</math> contains a matching that matches all the vertices of <math>S \cup T</math>.

== Problem 5 ==
Use the '''König-Egerváry theorem''' to prove the followings:
* Every bipartite graph <math>G</math> with <math>l</math> edges has a matching of size at least <math>l/\Delta(G)</math>, where <math>\Delta(G)</math> is the maximum degree of a vertex in <math>G</math>.
* Let <math>A</math> be a 0-1 matrix with <math>m</math> 1s. Let <math>s</math> be the maximal number of 1s in a row or column of <math>A</math>, and suppose that <math>A</math> has no square <math>r\times r</math> all-1 sub-matrix. It requires at least <math>m/(sr)</math> all-1 (not necessarily square) sub-matrices to cover all 1s in <math>A</math>.

组合数学 (Spring 2025)/Problem Set 4

2025-06-04T04:54:07Z

Gispzjz: Created page with "== Problem 1 == Recall that the smallest number <math>R(k,\ell)</math> satisfying the condition in the Ramsey theory is called the '''Ramsey number'''. Prove that: * <math>R(4,3)\leq 9</math>. (Hint: Proof by contradiction. Color the edges of <math>K_9</math> in red and blue, and assume that there are no red triangles and no blue <math>4</math>-cliques. Try to determine the number of red and blue edges adjacent to each vertex.) * <math>R(4,4)\leq 18</math>. ==Problem 2..."

== Problem 1 ==

Recall that the smallest number <math>R(k,\ell)</math> satisfying the condition in the Ramsey theory is called the '''Ramsey number'''. Prove that:
* <math>R(4,3)\leq 9</math>. (Hint: Proof by contradiction. Color the edges of <math>K_9</math> in red and blue, and assume that there are no red triangles and no blue <math>4</math>-cliques. Try to determine the number of red and blue edges adjacent to each vertex.)
* <math>R(4,4)\leq 18</math>.

==Problem 2==
We color each non-empty subset of <math>[n]=\{1,2,\ldots,n\}</math> with one of the <math>r</math> colors in <math>[r]</math>. Show that for any finite <math>r</math> there is a finite <math>N</math> such that for all <math>n\ge N</math>, for any <math>r</math>-coloring of non-empty subsets of <math>[n]</math>, there always exist <math>1\le i<j<k\le n</math> such that the intervals <math>[i,j)=\{i,i+1,\ldots, j-1\}</math>, <math>[j,k)=\{j,j+1,\ldots, k-1\}</math> and <math>[i,k)=\{i,i+1,\ldots, k-1\}</math> are all assigned with the same color.

==Problem 3 ==
An <math>n</math>-player tournament (竞赛图) <math>T([n],E)</math> is said to be '''transitive''', if there exists a permutation <math>\pi</math> of <math>[n]</math> such that <math>\pi_i<\pi_j</math> for every <math>(i,j)\in E</math>.

Show that for any <math>k\ge 3</math>, there exists a finite <math>N(k)</math> such that every tournament of <math>n\ge N(k)</math> players contains a transitive sub-tournament of <math>k</math> players. Express <math>N(k)</math> in terms of Ramsey number.

== Problem 4 ==
Suppose that <math>M,M'</math> are matchings in a bipartite graph <math>G</math> with bipartition <math>A,B</math>. Suppose that all the vertices of <math>S\subseteq A</math> are matched by <math>M</math> and that all the vertices of <math>T\subseteq B</math> are matched by <math>M'</math>. Prove that <math>G</math> contains a matching that matches all the vertices of <math>S \cup T</math>.

== Problem 5 ==
Use the '''König-Egerváry theorem''' to prove the followings:
* Every bipartite graph <math>G</math> with <math>l</math> edges has a matching of size at least <math>l/\Delta(G)</math>, where <math>\Delta(G)</math> is the maximum degree of a vertex in <math>G</math>.
* Let <math>A</math> be a 0-1 matrix with <math>m</math> 1s. Let <math>s</math> be the maximal number of 1s in a row or column of <math>A</math>, and suppose that <math>A</math> has no square <math>r\times r</math> all-1 sub-matrix. It requires at least <math>m/(sr)</math> all-1 (not necessarily square) sub-matrices to cover all 1s in <math>A</math>.

组合数学 (Spring 2025)

2025-06-04T04:54:00Z

Gispzjz: /* Assignments */

{{Infobox
|name = Infobox
|bodystyle =
|title = 组合数学 
Combinatorics
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = Wednesday, 2pm-4pm 逸A-322
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = TBA 计算机系 804
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = [[File:LW-combinatorics.jpeg|border|100px]]
|header11 =
|label11 =
|data11 = van Lint and Wilson. ''A course in Combinatorics, 2nd ed.'', Cambridge Univ Press, 2001.
|header12 =
|label12 =
|data12 = [[File:Jukna_book.jpg|border|100px]]
|header13 =
|label13 =
|data13 = Jukna. ''Extremal Combinatorics: With Applications in Computer Science, 2nd ed.'', Springer, 2011.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Combinatorics'' class of Spring 2025. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* '''(2025/03/18)''' 第一次作业已发布，请在 2025/04/02 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A1.pdf')
* '''(2025/04/09)''' 第二次作业已发布，请在 2025/04/23 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A2.pdf')
* '''(2025/05/07)''' 第二次作业已发布，请在 2025/05/28 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A3.pdf')

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** [https://lhy-gispzjz.github.io 刘弘洋] ([mailto:liuhongyang@smail.nju.edu.cn liuhongyang@smail.nju.edu.cn])
** 丁天行
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-322.
* '''Office hour''': TBA
:* '''QQ群''': 260501949 (加入时需报姓名、专业、学号)

= Syllabus =

=== 先修课程 Prerequisites ===
* 离散数学（Discrete Mathematics）
* 线性代数（Linear Algebra）
* 概率论（Probability Theory）

=== Course materials ===
* [[组合数学 (Spring 2025)/Course materials|教材和参考书清单]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
* [[组合数学 (Spring 2025)/Problem Set 1|Problem Set 1]] [[组合数学 (Spring 2025)/第一次作业提交名单|第一次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 2|Problem Set 2]] [[组合数学 (Spring 2025)/第二次作业提交名单|第二次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 3|Problem Set 3]] [[组合数学 (Spring 2025)/第三次作业提交名单|第三次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 4|Problem Set 4]]

= Lecture Notes =
# [[组合数学 (Spring 2025)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2025/BasicEnumeration.pdf slides])
# [[组合数学 (Fall 2025)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2025/GeneratingFunction.pdf slides])
# [[组合数学 (Fall 2025)/Sieve methods|Sieve methods | 筛法]] ([http://tcs.nju.edu.cn/slides/comb2025/PIE.pdf slides])
# [[组合数学 (Fall 2025)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] ([http://tcs.nju.edu.cn/slides/comb2025/Polya.pdf slides])
# [[组合数学 (Fall 2025)/Cayley's formula|Cayley's formula | Cayley公式]] ([http://tcs.nju.edu.cn/slides/comb2025/Cayley.pdf slides])
# [[组合数学 (Fall 2025)/Existence problems|Existence problems | 存在性问题]] ([http://tcs.nju.edu.cn/slides/comb2025/Existence.pdf slides])
# [[组合数学 (Fall 2025)/The probabilistic method|The probabilistic method | 概率法]] ([http://tcs.nju.edu.cn/slides/comb2025/ProbMethod.pdf slides])
# [[组合数学 (Fall 2025)/Extremal graph theory|Extremal graph theory | 极值图论]] ([http://tcs.nju.edu.cn/slides/comb2025/ExtremalGraphs.pdf slides])
# [[组合数学 (Fall 2025)/Extremal set theory|Extremal set theory | 极值集合论]]（[http://tcs.nju.edu.cn/slides/comb2024/ExtremalSets.pdf slides]）
#* [https://mathweb.ucsd.edu/~ronspubs/90_03_erdos_ko_rado.pdf Old and new proofs of the Erdős–Ko–Rado theorem] by Frankl and Graham
#* [https://arxiv.org/pdf/1908.08483.pdf Improved bounds for the sunflower lemma] by Alweiss-Lovet-Wu-Zhang and a [https://arxiv.org/pdf/1909.04774.pdf simplified proof] by Rao
# [[组合数学 (Fall 2025)/Ramsey theory|Ramsey theory | Ramsey理论]]（[http://tcs.nju.edu.cn/slides/comb2024/Ramsey.pdf slides]）

= Resources =
* [http://math.mit.edu/~fox/MAT307.html Combinatorics course] by Jacob Fox
* [https://yufeizhao.com/pm/ Probabilistic Methods in Combinatorics] and [https://yufeizhao.com/gtacbook/ Graph Theory and Additive Combinatorics] by Yufei Zhao
* [https://www.math.uvic.ca/~noelj/combinatoricsLectures.html Combinatorics Lecture Videos online]
* [https://www.math.ucla.edu/~pak/lectures/Math-Videos/comb-videos.htm Collection of Combinatorics Videos]

= Concepts =
* [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient]
* [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way]
* [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number]
* [http://en.wikipedia.org/wiki/Multiset#Formal_definition Multiset]
* [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset#Counting_multisets <math>k</math>-multisets on a set]
* [http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients Multinomial coefficients]
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind]
* [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number]
** [http://en.wikipedia.org/wiki/Young_tableau Young tableau]
* [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]
* [http://en.wikipedia.org/wiki/Catalan_number Catalan number]
* [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series]
* [http://en.wikipedia.org/wiki/Binomial_series Newton's formula]
* [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method])
* [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius inversion formula]
* [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages]
* [http://en.wikipedia.org/wiki/Ryser%27s_formula#Ryser_formula Ryser's formula]
* [http://en.wikipedia.org/wiki/Euler_totient Euler totient function]
* [https://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside's lemma]
** [https://en.wikipedia.org/wiki/Group_action Group action]
** [https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers Orbits]
* [https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Pólya enumeration theorem]
** [https://en.wikipedia.org/wiki/Permutation_group Permutation group]
** [https://en.wikipedia.org/wiki/Cycle_index Cycle index]
* [http://en.wikipedia.org/wiki/Cayley_formula Cayley's formula]
** [http://en.wikipedia.org/wiki/Prüfer_sequence Prüfer code for trees]
** [http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem Kirchhoff's matrix-tree theorem]
* [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma]
* [http://en.wikipedia.org/wiki/Sperner's_lemma Sperner's lemma] and [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer fixed point theorem]
* [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
:* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem]
* [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method]
* [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs]
* [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
* [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
* Two analytic inequalities:
:*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
:* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
* [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower lemma and conjecture]
* [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
* [https://en.wikipedia.org/wiki/Sperner%27s_theorem Sperner's theorem]
** [https://en.wikipedia.org/wiki/Sperner_family Sperner system] or '''antichain'''
* [https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma Sauer–Shelah lemma]
** [https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension Vapnik–Chervonenkis dimension]
* [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal–Katona theorem]
* [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
:*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
:*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
:*[https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem Van der Waerden's theorem]
:*[https://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem Hales–Jewett theorem]
* [https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem Hall's theorem ] (the marriage theorem)
:* [https://en.wikipedia.org/wiki/Doubly_stochastic_matrix Birkhoff–Von Neumann theorem]
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
* [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
* The [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
:* [https://en.wikipedia.org/wiki/Menger%27s_theorem Menger's theorem]
:* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]
* [https://en.wikipedia.org/wiki/Linear_programming Linear programming]
** [https://en.wikipedia.org/wiki/Dual_linear_program Duality]
** [https://en.wikipedia.org/wiki/Unimodular_matrix Unimodularity]
* [https://en.wikipedia.org/wiki/Matroid Matroid]

组合数学 (Spring 2025)/第三次作业提交名单

2025-06-03T11:47:08Z

Gispzjz: Created page with "如有错漏请邮件联系助教. <center> {| class="wikitable" |- ! 学号 !! 姓名 |- | 211220166 || 王诚昊 |- | 211830008 || 缪天顺 |- | 221180133 || 黄可唯 |- | 221220002 || 沈均文 |- | 221220022 || 颜树 |- | 221220029 || 陈俊翰 |- | 221220034 || 王旭 |- | 221220052 || 周宇轩 |- | 221220095 || 曾凡俊 |- | 221220104 || 刘宇平 |- | 221220109 || 肖琰 |- | 221220111 || 于源智 |- | 221220123 || 董立伟 |- | 221240035 ||..."

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 211220166 || 王诚昊
|-
| 211830008 || 缪天顺
|-
| 221180133 || 黄可唯
|-
| 221220002 || 沈均文
|-
| 221220022 || 颜树
|-
| 221220029 || 陈俊翰
|-
| 221220034 || 王旭
|-
| 221220052 || 周宇轩
|-
| 221220095 || 曾凡俊
|-
| 221220104 || 刘宇平
|-
| 221220109 || 肖琰
|-
| 221220111 || 于源智
|-
| 221220123 || 董立伟
|-
| 221240035 || 李想
|-
| 221240065 || 何俊渊
|-
| 221240073 || 李恒济
|-
| 221300016 || 白皓瑀
|-
| 221502002 || 严宇恒
|-
| 221502003 || 张天钰
|-
| 221502005 || 王昕浩
|-
| 221502007 || 崔毓泽
|-
| 221502010 || 梁志浩
|-
| 221502013 || 贺龄瑞
|-
| 221502017 || 卢君和
|-
| 221502021 || 李尚敖
|-
| 221504012 || 姜湛
|-
| 221840201 || 钟锦立
|-
| 221840207 || 陈逸迪
|-
| 221900059 || 王齐剑
|-
| 221900156 || 韩加瑞
|-
| 221900500 || 李亦非
|-
| 231220012 || 张启越
|-
| 231220073 || 李世昌
|-
| 231300059 || 阮一海
|-
| 231300084 || 柴梓涵
|-
| 231502022 || 胡骏秋
|-
| 231830106 || 朱逸宸
|-
| 231840164 || 高旭
|-
| 231840288 || 魏丽轩
|-
| 502024330019 || 黄锐
|-
| 502024330020 || 蒋承欢
|-
| 502024330065 || 张天泽
|-
| 502024330075 || 周灿
|-
| 522024330036 || 李尚达
|-
| 522024330112 || 叶佳
|-
| 522024330118 || 张弛
|-
| 522024330144 || 刘学彬
|-
| 652024330035 || 杨宇轩
|-
| DZ1833024 || 王竞冕
|-
|}
</center>

组合数学 (Spring 2025)/第二次作业提交名单

2025-06-03T11:41:18Z

Gispzjz: Created page with "如有错漏请邮件联系助教. <center> {| class="wikitable" |- ! 学号 !! 姓名 |- | 211220166 || 王诚昊 |- | 211830008 || 缪天顺 |- | 221180133 || 黄可唯 |- | 221220002 || 沈均文 |- | 221220022 || 颜树 |- | 221220029 || 陈俊翰 |- | 221220034 || 王旭 |- | 221220052 || 周宇轩 |- | 221220095 || 曾凡俊 |- | 221220109 || 肖琰 |- | 221220111 || 于源智 |- | 221220123 || 董立伟 |- | 221240035 || 李想 |- | 221240065 || 何..."

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 211220166 || 王诚昊
|-
| 211830008 || 缪天顺
|-
| 221180133 || 黄可唯
|-
| 221220002 || 沈均文
|-
| 221220022 || 颜树
|-
| 221220029 || 陈俊翰
|-
| 221220034 || 王旭
|-
| 221220052 || 周宇轩
|-
| 221220095 || 曾凡俊
|-
| 221220109 || 肖琰
|-
| 221220111 || 于源智
|-
| 221220123 || 董立伟
|-
| 221240035 || 李想
|-
| 221240065 || 何俊渊
|-
| 221240073 || 李恒济
|-
| 221300016 || 白皓瑀
|-
| 221502002 || 严宇恒
|-
| 221502003 || 张天钰
|-
| 221502005 || 王昕浩
|-
| 221502007 || 崔毓泽
|-
| 221502010 || 梁志浩
|-
| 221502013 || 贺龄瑞
|-
| 221502017 || 卢君和
|-
| 221502021 || 李尚敖
|-
| 221504012 || 姜湛
|-
| 221840201 || 钟锦立
|-
| 221840207 || 陈逸迪
|-
| 221900059 || 王齐剑
|-
| 221900156 || 韩加瑞
|-
| 221900500 || 李亦非
|-
| 231220012 || 张启越
|-
| 231220073 || 李世昌
|-
| 231300059 || 阮一海
|-
| 231300084 || 柴梓涵
|-
| 231502022 || 胡骏秋
|-
| 231830106 || 朱逸宸
|-
| 231840164 || 高旭
|-
| 231840288 || 魏丽轩
|-
| 231870210 || 沈奕齐
|-
| 502024330019 || 黄锐
|-
| 502024330020 || 蒋承欢
|-
| 502024330065 || 张天泽
|-
| 502024330075 || 周灿
|-
| 522024330036 || 李尚达
|-
| 522024330112 || 叶佳
|-
| 522024330118 || 张弛
|-
| 522024330144 || 刘学彬
|-
| 652024330035 || 杨宇轩
|-
| DZ1833024 || 王竞冕
|-
|}
</center>

组合数学 (Spring 2025)

2025-06-03T11:41:12Z

Gispzjz: /* Assignments */

{{Infobox
|name = Infobox
|bodystyle =
|title = 组合数学 
Combinatorics
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = Wednesday, 2pm-4pm 逸A-322
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = TBA 计算机系 804
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = [[File:LW-combinatorics.jpeg|border|100px]]
|header11 =
|label11 =
|data11 = van Lint and Wilson. ''A course in Combinatorics, 2nd ed.'', Cambridge Univ Press, 2001.
|header12 =
|label12 =
|data12 = [[File:Jukna_book.jpg|border|100px]]
|header13 =
|label13 =
|data13 = Jukna. ''Extremal Combinatorics: With Applications in Computer Science, 2nd ed.'', Springer, 2011.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Combinatorics'' class of Spring 2025. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* '''(2025/03/18)''' 第一次作业已发布，请在 2025/04/02 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A1.pdf')
* '''(2025/04/09)''' 第二次作业已发布，请在 2025/04/23 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A2.pdf')
* '''(2025/05/07)''' 第二次作业已发布，请在 2025/05/28 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A3.pdf')

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** [https://lhy-gispzjz.github.io 刘弘洋] ([mailto:liuhongyang@smail.nju.edu.cn liuhongyang@smail.nju.edu.cn])
** 丁天行
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-322.
* '''Office hour''': TBA
:* '''QQ群''': 260501949 (加入时需报姓名、专业、学号)

= Syllabus =

=== 先修课程 Prerequisites ===
* 离散数学（Discrete Mathematics）
* 线性代数（Linear Algebra）
* 概率论（Probability Theory）

=== Course materials ===
* [[组合数学 (Spring 2025)/Course materials|教材和参考书清单]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
* [[组合数学 (Spring 2025)/Problem Set 1|Problem Set 1]] [[组合数学 (Spring 2025)/第一次作业提交名单|第一次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 2|Problem Set 2]] [[组合数学 (Spring 2025)/第二次作业提交名单|第二次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 3|Problem Set 3]] [[组合数学 (Spring 2025)/第三次作业提交名单|第三次作业提交名单]]

= Lecture Notes =
# [[组合数学 (Spring 2025)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2025/BasicEnumeration.pdf slides])
# [[组合数学 (Fall 2025)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2025/GeneratingFunction.pdf slides])
# [[组合数学 (Fall 2025)/Sieve methods|Sieve methods | 筛法]] ([http://tcs.nju.edu.cn/slides/comb2025/PIE.pdf slides])
# [[组合数学 (Fall 2025)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] ([http://tcs.nju.edu.cn/slides/comb2025/Polya.pdf slides])
# [[组合数学 (Fall 2025)/Cayley's formula|Cayley's formula | Cayley公式]] ([http://tcs.nju.edu.cn/slides/comb2025/Cayley.pdf slides])
# [[组合数学 (Fall 2025)/Existence problems|Existence problems | 存在性问题]] ([http://tcs.nju.edu.cn/slides/comb2025/Existence.pdf slides])
# [[组合数学 (Fall 2025)/The probabilistic method|The probabilistic method | 概率法]] ([http://tcs.nju.edu.cn/slides/comb2025/ProbMethod.pdf slides])
# [[组合数学 (Fall 2025)/Extremal graph theory|Extremal graph theory | 极值图论]] ([http://tcs.nju.edu.cn/slides/comb2025/ExtremalGraphs.pdf slides])
# [[组合数学 (Fall 2025)/Extremal set theory|Extremal set theory | 极值集合论]]（[http://tcs.nju.edu.cn/slides/comb2024/ExtremalSets.pdf slides]）
#* [https://mathweb.ucsd.edu/~ronspubs/90_03_erdos_ko_rado.pdf Old and new proofs of the Erdős–Ko–Rado theorem] by Frankl and Graham
#* [https://arxiv.org/pdf/1908.08483.pdf Improved bounds for the sunflower lemma] by Alweiss-Lovet-Wu-Zhang and a [https://arxiv.org/pdf/1909.04774.pdf simplified proof] by Rao
# [[组合数学 (Fall 2025)/Ramsey theory|Ramsey theory | Ramsey理论]]（[http://tcs.nju.edu.cn/slides/comb2024/Ramsey.pdf slides]）

= Resources =
* [http://math.mit.edu/~fox/MAT307.html Combinatorics course] by Jacob Fox
* [https://yufeizhao.com/pm/ Probabilistic Methods in Combinatorics] and [https://yufeizhao.com/gtacbook/ Graph Theory and Additive Combinatorics] by Yufei Zhao
* [https://www.math.uvic.ca/~noelj/combinatoricsLectures.html Combinatorics Lecture Videos online]
* [https://www.math.ucla.edu/~pak/lectures/Math-Videos/comb-videos.htm Collection of Combinatorics Videos]

= Concepts =
* [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient]
* [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way]
* [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number]
* [http://en.wikipedia.org/wiki/Multiset#Formal_definition Multiset]
* [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset#Counting_multisets <math>k</math>-multisets on a set]
* [http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients Multinomial coefficients]
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind]
* [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number]
** [http://en.wikipedia.org/wiki/Young_tableau Young tableau]
* [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]
* [http://en.wikipedia.org/wiki/Catalan_number Catalan number]
* [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series]
* [http://en.wikipedia.org/wiki/Binomial_series Newton's formula]
* [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method])
* [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius inversion formula]
* [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages]
* [http://en.wikipedia.org/wiki/Ryser%27s_formula#Ryser_formula Ryser's formula]
* [http://en.wikipedia.org/wiki/Euler_totient Euler totient function]
* [https://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside's lemma]
** [https://en.wikipedia.org/wiki/Group_action Group action]
** [https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers Orbits]
* [https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Pólya enumeration theorem]
** [https://en.wikipedia.org/wiki/Permutation_group Permutation group]
** [https://en.wikipedia.org/wiki/Cycle_index Cycle index]
* [http://en.wikipedia.org/wiki/Cayley_formula Cayley's formula]
** [http://en.wikipedia.org/wiki/Prüfer_sequence Prüfer code for trees]
** [http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem Kirchhoff's matrix-tree theorem]
* [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma]
* [http://en.wikipedia.org/wiki/Sperner's_lemma Sperner's lemma] and [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer fixed point theorem]
* [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
:* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem]
* [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method]
* [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs]
* [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
* [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
* Two analytic inequalities:
:*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
:* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
* [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower lemma and conjecture]
* [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
* [https://en.wikipedia.org/wiki/Sperner%27s_theorem Sperner's theorem]
** [https://en.wikipedia.org/wiki/Sperner_family Sperner system] or '''antichain'''
* [https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma Sauer–Shelah lemma]
** [https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension Vapnik–Chervonenkis dimension]
* [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal–Katona theorem]
* [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
:*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
:*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
:*[https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem Van der Waerden's theorem]
:*[https://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem Hales–Jewett theorem]
* [https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem Hall's theorem ] (the marriage theorem)
:* [https://en.wikipedia.org/wiki/Doubly_stochastic_matrix Birkhoff–Von Neumann theorem]
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
* [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
* The [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
:* [https://en.wikipedia.org/wiki/Menger%27s_theorem Menger's theorem]
:* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]
* [https://en.wikipedia.org/wiki/Linear_programming Linear programming]
** [https://en.wikipedia.org/wiki/Dual_linear_program Duality]
** [https://en.wikipedia.org/wiki/Unimodular_matrix Unimodularity]
* [https://en.wikipedia.org/wiki/Matroid Matroid]

组合数学 (Spring 2025)/第一次作业提交名单

2025-06-03T11:35:37Z

Gispzjz:

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 211220166 || 王诚昊
|-
| 211830008 || 缪天顺
|-
| 221180133 || 黄可唯
|-
| 221220002 || 沈均文
|-
| 221220022 || 颜树
|-
| 221220029 || 陈俊翰
|-
| 221220034 || 王旭
|-
| 221220052 || 周宇轩
|-
| 221220095 || 曾凡俊
|-
| 221220104 || 刘宇平
|-
| 221220109 || 肖琰
|-
| 221220111 || 于源智
|-
| 221220123 || 董立伟
|-
| 221240035 || 李想
|-
| 221240065 || 何俊渊
|-
| 221240073 || 李恒济
|-
| 221300016 || 白皓瑀
|-
| 221300048 || 姚岐周
|-
| 221300082 || 孟坤泽
|-
| 221502002 || 严宇恒
|-
| 221502003 || 张天钰
|-
| 221502005 || 王昕浩
|-
| 221502007 || 崔毓泽
|-
| 221502010 || 梁志浩
|-
| 221502013 || 贺龄瑞
|-
| 221502017 || 卢君和
|-
| 221502021 || 李尚敖
|-
| 221504012 || 姜湛
|-
| 221840201 || 钟锦立
|-
| 221840207 || 陈逸迪
|-
| 221900059 || 王齐剑
|-
| 221900156 || 韩加瑞
|-
| 221900500 || 李亦非
|-
| 231220012 || 张启越
|-
| 231220073 || 李世昌
|-
| 231300059 || 阮一海
|-
| 231300084 || 柴梓涵
|-
| 231502022 || 胡骏秋
|-
| 231830106 || 朱逸宸
|-
| 231840164 || 高旭
|-
| 231840288 || 魏丽轩
|-
| 231870210 || 沈奕齐
|-
| 502024330019 || 黄锐
|-
| 502024330020 || 蒋承欢
|-
| 502024330065 || 张天泽
|-
| 502024330075 || 周灿
|-
| 522024330036 || 李尚达
|-
| 522024330112 || 叶佳
|-
| 522024330118 || 张弛
|-
| 522024330144 || 刘学彬
|-
| 652024330035 || 杨宇轩
|-
| DZ1833024 || 王竞冕
|-
|}
</center>

组合数学 (Spring 2025)

2025-05-18T14:59:27Z

Gispzjz: /* Announcement */

{{Infobox
|name = Infobox
|bodystyle =
|title = 组合数学 
Combinatorics
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = Wednesday, 2pm-4pm 逸A-322
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = TBA 计算机系 804
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = [[File:LW-combinatorics.jpeg|border|100px]]
|header11 =
|label11 =
|data11 = van Lint and Wilson. ''A course in Combinatorics, 2nd ed.'', Cambridge Univ Press, 2001.
|header12 =
|label12 =
|data12 = [[File:Jukna_book.jpg|border|100px]]
|header13 =
|label13 =
|data13 = Jukna. ''Extremal Combinatorics: With Applications in Computer Science, 2nd ed.'', Springer, 2011.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Combinatorics'' class of Spring 2025. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* '''(2025/03/18)''' 第一次作业已发布，请在 2025/04/02 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A1.pdf')
* '''(2025/04/09)''' 第二次作业已发布，请在 2025/04/23 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A2.pdf')
* '''(2025/05/07)''' 第二次作业已发布，请在 2025/05/28 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A3.pdf')

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** [https://lhy-gispzjz.github.io 刘弘洋] ([mailto:liuhongyang@smail.nju.edu.cn liuhongyang@smail.nju.edu.cn])
** 丁天行
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-322.
* '''Office hour''': TBA
:* '''QQ群''': 260501949 (加入时需报姓名、专业、学号)

= Syllabus =

=== 先修课程 Prerequisites ===
* 离散数学（Discrete Mathematics）
* 线性代数（Linear Algebra）
* 概率论（Probability Theory）

=== Course materials ===
* [[组合数学 (Spring 2025)/Course materials|教材和参考书清单]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
* [[组合数学 (Spring 2025)/Problem Set 1|Problem Set 1]] [[组合数学 (Spring 2025)/第一次作业提交名单|第一次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 2|Problem Set 2]]
* [[组合数学 (Spring 2025)/Problem Set 3|Problem Set 3]]

= Lecture Notes =
# [[组合数学 (Spring 2025)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2025/BasicEnumeration.pdf slides])
# [[组合数学 (Fall 2025)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2025/GeneratingFunction.pdf slides])
# [[组合数学 (Fall 2025)/Sieve methods|Sieve methods | 筛法]] ([http://tcs.nju.edu.cn/slides/comb2025/PIE.pdf slides])
# [[组合数学 (Fall 2025)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] ([http://tcs.nju.edu.cn/slides/comb2025/Polya.pdf slides])
# [[组合数学 (Fall 2025)/Cayley's formula|Cayley's formula | Cayley公式]] ([http://tcs.nju.edu.cn/slides/comb2025/Cayley.pdf slides])
# [[组合数学 (Fall 2025)/Existence problems|Existence problems | 存在性问题]] ([http://tcs.nju.edu.cn/slides/comb2025/Existence.pdf slides])
# [[组合数学 (Fall 2025)/The probabilistic method|The probabilistic method | 概率法]] ([http://tcs.nju.edu.cn/slides/comb2025/ProbMethod.pdf slides])
# [[组合数学 (Fall 2025)/Extremal graph theory|Extremal graph theory | 极值图论]] ([http://tcs.nju.edu.cn/slides/comb2025/ExtremalGraphs.pdf slides])

= Resources =
* [http://math.mit.edu/~fox/MAT307.html Combinatorics course] by Jacob Fox
* [https://yufeizhao.com/pm/ Probabilistic Methods in Combinatorics] and [https://yufeizhao.com/gtacbook/ Graph Theory and Additive Combinatorics] by Yufei Zhao
* [https://www.math.uvic.ca/~noelj/combinatoricsLectures.html Combinatorics Lecture Videos online]
* [https://www.math.ucla.edu/~pak/lectures/Math-Videos/comb-videos.htm Collection of Combinatorics Videos]

= Concepts =
* [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient]
* [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way]
* [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number]
* [http://en.wikipedia.org/wiki/Multiset#Formal_definition Multiset]
* [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset#Counting_multisets <math>k</math>-multisets on a set]
* [http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients Multinomial coefficients]
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind]
* [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number]
** [http://en.wikipedia.org/wiki/Young_tableau Young tableau]
* [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]
* [http://en.wikipedia.org/wiki/Catalan_number Catalan number]
* [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series]
* [http://en.wikipedia.org/wiki/Binomial_series Newton's formula]
* [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method])
* [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius inversion formula]
* [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages]
* [http://en.wikipedia.org/wiki/Ryser%27s_formula#Ryser_formula Ryser's formula]
* [http://en.wikipedia.org/wiki/Euler_totient Euler totient function]
* [https://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside's lemma]
** [https://en.wikipedia.org/wiki/Group_action Group action]
** [https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers Orbits]
* [https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Pólya enumeration theorem]
** [https://en.wikipedia.org/wiki/Permutation_group Permutation group]
** [https://en.wikipedia.org/wiki/Cycle_index Cycle index]
* [http://en.wikipedia.org/wiki/Cayley_formula Cayley's formula]
** [http://en.wikipedia.org/wiki/Prüfer_sequence Prüfer code for trees]
** [http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem Kirchhoff's matrix-tree theorem]
* [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma]
* [http://en.wikipedia.org/wiki/Sperner's_lemma Sperner's lemma] and [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer fixed point theorem]
* [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
:* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem]
* [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method]
* [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs]
* [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
* [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
* Two analytic inequalities:
:*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
:* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
* [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower lemma and conjecture]
* [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
* [https://en.wikipedia.org/wiki/Sperner%27s_theorem Sperner's theorem]
** [https://en.wikipedia.org/wiki/Sperner_family Sperner system] or '''antichain'''
* [https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma Sauer–Shelah lemma]
** [https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension Vapnik–Chervonenkis dimension]
* [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal–Katona theorem]
* [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
:*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
:*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
:*[https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem Van der Waerden's theorem]
:*[https://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem Hales–Jewett theorem]
* [https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem Hall's theorem ] (the marriage theorem)
:* [https://en.wikipedia.org/wiki/Doubly_stochastic_matrix Birkhoff–Von Neumann theorem]
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
* [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
* The [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
:* [https://en.wikipedia.org/wiki/Menger%27s_theorem Menger's theorem]
:* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]
* [https://en.wikipedia.org/wiki/Linear_programming Linear programming]
** [https://en.wikipedia.org/wiki/Dual_linear_program Duality]
** [https://en.wikipedia.org/wiki/Unimodular_matrix Unimodularity]
* [https://en.wikipedia.org/wiki/Matroid Matroid]

组合数学 (Spring 2025)/Problem Set 3

2025-05-06T16:05:42Z

Gispzjz: /* Problem 3 */

probability and computing 6.17 (page 166)

extremal comb 4.17

== Problem 1 ==
Use the Lovász Local Lemma to show that, if <math> 4\binom{k}{2}\binom{n}{k-2}2^{1-\binom{k}{2}} \leq 1 </math>, then it is possible to color the edges of <math>K_n</math> with two colors so that it has no monochromatic <math>K_k</math> subgraph.

== Problem 2 ==
Let <math>G = (V, E)</math> be an undirected graph and suppose each <math>v \in V</math> is
associated with a set <math>S(v)</math> of at least <math>2\mathrm{e}r</math> colors, where <math>r \geq 1 </math>. Suppose, in addition, that for each
<math>v \in V</math> and <math>c \in S(v)</math> there are at most <math>r</math> neighbors <math>u</math> of <math>v</math> such that <math>c</math> lies in <math>S(u)</math>. Prove
that there is a proper coloring of <math>G</math> assigning to each vertex <math>v</math> a color from its class
<math>S(v)</math> such that, for any edge <math>(u, v) \in E</math>, the colors assigned to <math>u</math> and <math>v</math> are different.

== Problem 3 ==
(Goodman 1959)

Let <math> G=(V,E) </math> be a graph on <math> n </math> vertices and <math> t(G) </math> denote the number of triangles contained in the graph <math> G </math> or in its complement. Prove that <math> t(G)\geq \binom{n}{3}+\frac{2m^2}{n}-m(n-1)</math>.

'''Hint''': Let <math>t_i</math> be the number of triples of vertices <math>(i,j,k)</math> such that the vertex <math>i</math> is adjacent to precisely one of <math>j</math> or <math>k</math>.
Note that <math>t_i = d_i(n-1-d_i)</math> where <math>d_i</math> is the degree of the vertex <math>i</math>.
Show that <math>t(G) \geq \binom{n}{3}-\frac{1}{2}\sum_i t_i</math> and use the Cauchy–Schwarz to bound <math> \sum_i t_i </math>.

== Problem 4 ==
Prove the following theorem on extremal graph theory:

* (Graham–Kleitman 1973). If the edges of a complete graph on <math>n</math> vertices are labeled arbitrarily with the integers <math>1, 2,\dots, \frac{n(n-1)}{2}</math>, each edge receiving its own integer, then there is a trail (i.e., a walk without repeated edges) of length at least <math>n − 1 </math> with an increasing sequence of edge-labels. (Hint: To each vertex <math>v</math>, assign its weight <math>w_v</math> equal to the length of the longest increasing trail ending at <math>v</math>. Can you show that <math>\sum\limits_{i=1}^{n} w_i\geq n(n-1)</math>?)

== Problem 5 ==
(Frankl 1986)

Let <math>\mathcal{F}\subseteq {[n]\choose k}</math> be a <math>k</math>-uniform family, and suppose that it satisfies that <math>A\cap B \not\subset C</math> for any <math>A,B,C\in\mathcal{F}</math>.
* Fix any <math>B\in\mathcal{F}</math>. Show that the family <math>\{A\cap B\mid A\in\mathcal{F}, A\neq B\}</math> is an anti chain.
* Show that <math>|\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor}</math>.

组合数学 (Spring 2025)/Problem Set 3

2025-05-06T16:05:31Z

Gispzjz: /* Problem 3 */

probability and computing 6.17 (page 166)

extremal comb 4.17

== Problem 1 ==
Use the Lovász Local Lemma to show that, if <math> 4\binom{k}{2}\binom{n}{k-2}2^{1-\binom{k}{2}} \leq 1 </math>, then it is possible to color the edges of <math>K_n</math> with two colors so that it has no monochromatic <math>K_k</math> subgraph.

== Problem 2 ==
Let <math>G = (V, E)</math> be an undirected graph and suppose each <math>v \in V</math> is
associated with a set <math>S(v)</math> of at least <math>2\mathrm{e}r</math> colors, where <math>r \geq 1 </math>. Suppose, in addition, that for each
<math>v \in V</math> and <math>c \in S(v)</math> there are at most <math>r</math> neighbors <math>u</math> of <math>v</math> such that <math>c</math> lies in <math>S(u)</math>. Prove
that there is a proper coloring of <math>G</math> assigning to each vertex <math>v</math> a color from its class
<math>S(v)</math> such that, for any edge <math>(u, v) \in E</math>, the colors assigned to <math>u</math> and <math>v</math> are different.

== Problem 3 ==
(Goodman 1959). Let <math> G=(V,E) </math> be a graph on <math> n </math> vertices and <math> t(G) </math> denote the number of triangles contained in the graph <math> G </math> or in its complement. Prove that <math> t(G)\geq \binom{n}{3}+\frac{2m^2}{n}-m(n-1)</math>.

'''Hint''': Let <math>t_i</math> be the number of triples of vertices <math>(i,j,k)</math> such that the vertex <math>i</math> is adjacent to precisely one of <math>j</math> or <math>k</math>.
Note that <math>t_i = d_i(n-1-d_i)</math> where <math>d_i</math> is the degree of the vertex <math>i</math>.
Show that <math>t(G) \geq \binom{n}{3}-\frac{1}{2}\sum_i t_i</math> and use the Cauchy–Schwarz to bound <math> \sum_i t_i </math>.

== Problem 4 ==
Prove the following theorem on extremal graph theory:

* (Graham–Kleitman 1973). If the edges of a complete graph on <math>n</math> vertices are labeled arbitrarily with the integers <math>1, 2,\dots, \frac{n(n-1)}{2}</math>, each edge receiving its own integer, then there is a trail (i.e., a walk without repeated edges) of length at least <math>n − 1 </math> with an increasing sequence of edge-labels. (Hint: To each vertex <math>v</math>, assign its weight <math>w_v</math> equal to the length of the longest increasing trail ending at <math>v</math>. Can you show that <math>\sum\limits_{i=1}^{n} w_i\geq n(n-1)</math>?)

== Problem 5 ==
(Frankl 1986)

Let <math>\mathcal{F}\subseteq {[n]\choose k}</math> be a <math>k</math>-uniform family, and suppose that it satisfies that <math>A\cap B \not\subset C</math> for any <math>A,B,C\in\mathcal{F}</math>.
* Fix any <math>B\in\mathcal{F}</math>. Show that the family <math>\{A\cap B\mid A\in\mathcal{F}, A\neq B\}</math> is an anti chain.
* Show that <math>|\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor}</math>.

组合数学 (Spring 2025)/Problem Set 3

2025-05-06T16:03:54Z

Gispzjz:

probability and computing 6.17 (page 166)

extremal comb 4.17

== Problem 1 ==
Use the Lovász Local Lemma to show that, if <math> 4\binom{k}{2}\binom{n}{k-2}2^{1-\binom{k}{2}} \leq 1 </math>, then it is possible to color the edges of <math>K_n</math> with two colors so that it has no monochromatic <math>K_k</math> subgraph.

== Problem 2 ==
Let <math>G = (V, E)</math> be an undirected graph and suppose each <math>v \in V</math> is
associated with a set <math>S(v)</math> of at least <math>2\mathrm{e}r</math> colors, where <math>r \geq 1 </math>. Suppose, in addition, that for each
<math>v \in V</math> and <math>c \in S(v)</math> there are at most <math>r</math> neighbors <math>u</math> of <math>v</math> such that <math>c</math> lies in <math>S(u)</math>. Prove
that there is a proper coloring of <math>G</math> assigning to each vertex <math>v</math> a color from its class
<math>S(v)</math> such that, for any edge <math>(u, v) \in E</math>, the colors assigned to <math>u</math> and <math>v</math> are different.

== Problem 3 ==
* (Goodman 1959). Let <math> G=(V,E) </math> be a graph on <math> n </math> vertices and <math> t(G) </math> denote the number of triangles contained in the graph <math> G </math> or in its complement. Prove that <math> t(G)\geq \binom{n}{3}+\frac{2m^2}{n}-m(n-1)</math>.

'''Hint''': Let <math>t_i</math> be the number of triples of vertices <math>(i,j,k)</math> such that the vertex <math>i</math> is adjacent to precisely one of <math>j</math> or <math>k</math>.
Note that <math>t_i = d_i(n-1-d_i)</math> where <math>d_i</math> is the degree of the vertex <math>i</math>.
Show that <math>t(G) \geq \binom{n}{3}-\frac{1}{2}\sum_i t_i</math> and use the Cauchy–Schwarz to bound <math> \sum_i t_i </math>.

== Problem 4 ==
Prove the following theorem on extremal graph theory:

* (Graham–Kleitman 1973). If the edges of a complete graph on <math>n</math> vertices are labeled arbitrarily with the integers <math>1, 2,\dots, \frac{n(n-1)}{2}</math>, each edge receiving its own integer, then there is a trail (i.e., a walk without repeated edges) of length at least <math>n − 1 </math> with an increasing sequence of edge-labels. (Hint: To each vertex <math>v</math>, assign its weight <math>w_v</math> equal to the length of the longest increasing trail ending at <math>v</math>. Can you show that <math>\sum\limits_{i=1}^{n} w_i\geq n(n-1)</math>?)

== Problem 5 ==
(Frankl 1986)

Let <math>\mathcal{F}\subseteq {[n]\choose k}</math> be a <math>k</math>-uniform family, and suppose that it satisfies that <math>A\cap B \not\subset C</math> for any <math>A,B,C\in\mathcal{F}</math>.
* Fix any <math>B\in\mathcal{F}</math>. Show that the family <math>\{A\cap B\mid A\in\mathcal{F}, A\neq B\}</math> is an anti chain.
* Show that <math>|\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor}</math>.

组合数学 (Spring 2025)/Problem Set 3

2025-05-06T16:03:37Z

Gispzjz: /* Problem 3 */

probability and computing 6.17 (page 166)

extremal comb 4.17

== Problem 1 ==
Use the Lovász Local Lemma to show that, if <math> 4\binom{k}{2}\binom{n}{k-2}2^{1-\binom{k}{2}} \leq 1 </math>, then it is possible to color the edges of <math>K_n</math> with two colors so that it has no monochromatic <math>K_k</math> subgraph.

== Problem 2 ==
Let <math>G = (V, E)</math> be an undirected graph and suppose each <math>v \in V</math> is
associated with a set <math>S(v)</math> of at least <math>2\mathrm{e}r</math> colors, where <math>r \geq 1 </math>. Suppose, in addition, that for each
<math>v \in V</math> and <math>c \in S(v)</math> there are at most <math>r</math> neighbors <math>u</math> of <math>v</math> such that <math>c</math> lies in <math>S(u)</math>. Prove
that there is a proper coloring of <math>G</math> assigning to each vertex <math>v</math> a color from its class
<math>S(v)</math> such that, for any edge <math>(u, v) \in E</math>, the colors assigned to <math>u</math> and <math>v</math> are different.

== Problem 3 ==
* (Goodman 1959). Let <math> G=(V,E) </math> be a graph on <math> n </math> vertices and <math> t(G) </math> denote the number of triangles contained in the graph <math> G </math> or in its complement. Prove that <math> t(G)\geq \binom{n}{3}+\frac{2m^2}{n}-m(n-1)</math>.

'''Hint''': Let <math>t_i</math> be the number of triples of vertices <math>(i,j,k)</math> such that the vertex <math>i</math> is adjacent to precisely one of <math>j</math> or <math>k</math>.
Note that <math>t_i = d_i(n-1-d_i)</math> where <math>d_i</math> is the degree of the vertex <math>i</math>.
Show that <math>t(G) \geq \binom{n}{3}-\frac{1}{2}\sum_i t_i</math> and use the Cauchy–Schwarz to bound <math> \sum_i t_i </math>.

== Problem 4 ==
Prove the following theorem on extremal graph theory:

* (Graham–Kleitman 1973). If the edges of a complete graph on <math>n</math> vertices are labeled arbitrarily with the integers <math>1, 2,\dots, \frac{n(n-1)}{2}</math>, each edge receiving its own integer, then there is a trail (i.e., a walk without repeated edges) of length at least <math>n − 1 </math> with an increasing sequence of edge-labels. (Hint: To each vertex <math>v</math>, assign its weight <math>w_v</math> equal to the length of the longest increasing trail ending at <math>v</math>. Can you show that <math>\sum\limits_{i=1}^{n} w_i\geq n(n-1)</math>?)

== Problem 5 ==
(Frankl 1986)

Let <math>\mathcal{F}\subseteq {[n]\choose k}</math> be a <math>k</math>-uniform family, and suppose that it satisfies that <math>A\cap B \not\subset C</math> for any <math>A,B,C\in\mathcal{F}</math>.
* Fix any <math>B\in\mathcal{F}</math>. Show that the family <math>\{A\cap B\mid A\in\mathcal{F}, A\neq B\}</math> is an anti chain.
* Show that <math>|\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor}</math>.

组合数学 (Spring 2025)/Problem Set 3

2025-05-06T16:02:14Z

Gispzjz: /* Problem 3 */

probability and computing 6.17 (page 166)

extremal comb 4.17

== Problem 1 ==
Use the Lovász Local Lemma to show that, if <math> 4\binom{k}{2}\binom{n}{k-2}2^{1-\binom{k}{2}} \leq 1 </math>, then it is possible to color the edges of <math>K_n</math> with two colors so that it has no monochromatic <math>K_k</math> subgraph.

== Problem 2 ==
Let <math>G = (V, E)</math> be an undirected graph and suppose each <math>v \in V</math> is
associated with a set <math>S(v)</math> of at least <math>2\mathrm{e}r</math> colors, where <math>r \geq 1 </math>. Suppose, in addition, that for each
<math>v \in V</math> and <math>c \in S(v)</math> there are at most <math>r</math> neighbors <math>u</math> of <math>v</math> such that <math>c</math> lies in <math>S(u)</math>. Prove
that there is a proper coloring of <math>G</math> assigning to each vertex <math>v</math> a color from its class
<math>S(v)</math> such that, for any edge <math>(u, v) \in E</math>, the colors assigned to <math>u</math> and <math>v</math> are different.

== Problem 3 ==
* (Goodman 1959). Let <math> G=(V,E) </math> be a graph on <math> n </math> vertices and <math> t(G) </math> denote the number of triangles contained in the graph <math> G </math> or in its complement. Prove that <math> t(G)\geq \binom{n}{3}+\frac{2m^2}{n}-m(n-1)</math>.

'''Hint''': Let <math>t_i</math> be the number of triples of vertices <math>(i,j,k)</math> such that the vertex <math>i</math> is adjacent to precisely one of <math>j</math> or <math>k</math>. Show that <math>t(G) \geq \binom{n}{3}-\frac{1}{2}\sum_i t_i</math> and use the Cauchy–Schwarz to bound <math> \sum_i t_i </math>.

== Problem 4 ==
Prove the following theorem on extremal graph theory:

* (Graham–Kleitman 1973). If the edges of a complete graph on <math>n</math> vertices are labeled arbitrarily with the integers <math>1, 2,\dots, \frac{n(n-1)}{2}</math>, each edge receiving its own integer, then there is a trail (i.e., a walk without repeated edges) of length at least <math>n − 1 </math> with an increasing sequence of edge-labels. (Hint: To each vertex <math>v</math>, assign its weight <math>w_v</math> equal to the length of the longest increasing trail ending at <math>v</math>. Can you show that <math>\sum\limits_{i=1}^{n} w_i\geq n(n-1)</math>?)

== Problem 5 ==
(Frankl 1986)

Let <math>\mathcal{F}\subseteq {[n]\choose k}</math> be a <math>k</math>-uniform family, and suppose that it satisfies that <math>A\cap B \not\subset C</math> for any <math>A,B,C\in\mathcal{F}</math>.
* Fix any <math>B\in\mathcal{F}</math>. Show that the family <math>\{A\cap B\mid A\in\mathcal{F}, A\neq B\}</math> is an anti chain.
* Show that <math>|\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor}</math>.

组合数学 (Spring 2025)/Problem Set 3

2025-05-06T16:01:30Z

Gispzjz: Created page with "probability and computing 6.17 (page 166) extremal comb 4.17 == Problem 1 == Use the Lovász Local Lemma to show that, if <math> 4\binom{k}{2}\binom{n}{k-2}2^{1-\binom{k}{2}} \leq 1 </math>, then it is possible to color the edges of <math>K_n</math> with two colors so that it has no monochromatic <math>K_k</math> subgraph. == Problem 2 == Let <math>G = (V, E)</math> be an undirected graph and suppose each <math>v \in V</math> is associated with a set <math>S(v)</math..."

probability and computing 6.17 (page 166)

extremal comb 4.17

== Problem 1 ==
Use the Lovász Local Lemma to show that, if <math> 4\binom{k}{2}\binom{n}{k-2}2^{1-\binom{k}{2}} \leq 1 </math>, then it is possible to color the edges of <math>K_n</math> with two colors so that it has no monochromatic <math>K_k</math> subgraph.

== Problem 2 ==
Let <math>G = (V, E)</math> be an undirected graph and suppose each <math>v \in V</math> is
associated with a set <math>S(v)</math> of at least <math>2\mathrm{e}r</math> colors, where <math>r \geq 1 </math>. Suppose, in addition, that for each
<math>v \in V</math> and <math>c \in S(v)</math> there are at most <math>r</math> neighbors <math>u</math> of <math>v</math> such that <math>c</math> lies in <math>S(u)</math>. Prove
that there is a proper coloring of <math>G</math> assigning to each vertex <math>v</math> a color from its class
<math>S(v)</math> such that, for any edge <math>(u, v) \in E</math>, the colors assigned to <math>u</math> and <math>v</math> are different.

== Problem 3 ==
* (Goodman 1959). Let <math> G=(V,E) </math> be a graph on <math> n </math> vertices and <math> t(G) </math> denote the number of triangles contained in the graph <math> G </math> or in its complement. Prove that <math> t(G)\geq \binom{n}{3}+\frac{2m^2}{n}-m(n-1)</math>.

'''Hint''': Let <math>t_i</math> be the number of triples of vertices <math>(i,j,k)</math> such that the vertex <math>i</math> is adjacent to precisely one of <math>j</math> or <math>k</math>. Show that <math>t(G) \geq \binom{n}{3}-\frac{1}{2}\sum_i t_i</math> and try to use the Cauchy–Schwarz to bound <math> \sum_i t_i </math>.

== Problem 4 ==
Prove the following theorem on extremal graph theory:

* (Graham–Kleitman 1973). If the edges of a complete graph on <math>n</math> vertices are labeled arbitrarily with the integers <math>1, 2,\dots, \frac{n(n-1)}{2}</math>, each edge receiving its own integer, then there is a trail (i.e., a walk without repeated edges) of length at least <math>n − 1 </math> with an increasing sequence of edge-labels. (Hint: To each vertex <math>v</math>, assign its weight <math>w_v</math> equal to the length of the longest increasing trail ending at <math>v</math>. Can you show that <math>\sum\limits_{i=1}^{n} w_i\geq n(n-1)</math>?)

== Problem 5 ==
(Frankl 1986)

Let <math>\mathcal{F}\subseteq {[n]\choose k}</math> be a <math>k</math>-uniform family, and suppose that it satisfies that <math>A\cap B \not\subset C</math> for any <math>A,B,C\in\mathcal{F}</math>.
* Fix any <math>B\in\mathcal{F}</math>. Show that the family <math>\{A\cap B\mid A\in\mathcal{F}, A\neq B\}</math> is an anti chain.
* Show that <math>|\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor}</math>.

组合数学 (Spring 2025)

2025-05-06T15:50:31Z

Gispzjz: /* Assignments */

{{Infobox
|name = Infobox
|bodystyle =
|title = 组合数学 
Combinatorics
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = Wednesday, 2pm-4pm 逸A-322
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = TBA 计算机系 804
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = [[File:LW-combinatorics.jpeg|border|100px]]
|header11 =
|label11 =
|data11 = van Lint and Wilson. ''A course in Combinatorics, 2nd ed.'', Cambridge Univ Press, 2001.
|header12 =
|label12 =
|data12 = [[File:Jukna_book.jpg|border|100px]]
|header13 =
|label13 =
|data13 = Jukna. ''Extremal Combinatorics: With Applications in Computer Science, 2nd ed.'', Springer, 2011.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Combinatorics'' class of Spring 2025. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* '''(2025/03/18)''' 第一次作业已发布，请在 2025/04/02 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A1.pdf')
* '''(2025/04/09)''' 第二次作业已发布，请在 2025/04/23 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A2.pdf')

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** [https://lhy-gispzjz.github.io 刘弘洋] ([mailto:liuhongyang@smail.nju.edu.cn liuhongyang@smail.nju.edu.cn])
** 丁天行
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-322.
* '''Office hour''': TBA
:* '''QQ群''': 260501949 (加入时需报姓名、专业、学号)

= Syllabus =

=== 先修课程 Prerequisites ===
* 离散数学（Discrete Mathematics）
* 线性代数（Linear Algebra）
* 概率论（Probability Theory）

=== Course materials ===
* [[组合数学 (Spring 2025)/Course materials|教材和参考书清单]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
* [[组合数学 (Spring 2025)/Problem Set 1|Problem Set 1]] [[组合数学 (Spring 2025)/第一次作业提交名单|第一次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 2|Problem Set 2]]
* [[组合数学 (Spring 2025)/Problem Set 3|Problem Set 3]]

= Lecture Notes =
# [[组合数学 (Spring 2025)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2025/BasicEnumeration.pdf slides])
# [[组合数学 (Fall 2025)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2025/GeneratingFunction.pdf slides])
# [[组合数学 (Fall 2025)/Sieve methods|Sieve methods | 筛法]] ([http://tcs.nju.edu.cn/slides/comb2025/PIE.pdf slides])
# [[组合数学 (Fall 2025)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] ([http://tcs.nju.edu.cn/slides/comb2025/Polya.pdf slides])
# [[组合数学 (Fall 2025)/Cayley's formula|Cayley's formula | Cayley公式]] ([http://tcs.nju.edu.cn/slides/comb2025/Cayley.pdf slides])
# [[组合数学 (Fall 2025)/Existence problems|Existence problems | 存在性问题]] ([http://tcs.nju.edu.cn/slides/comb2025/Existence.pdf slides])
# [[组合数学 (Fall 2025)/The probabilistic method|The probabilistic method | 概率法]] ([http://tcs.nju.edu.cn/slides/comb2025/ProbMethod.pdf slides])
# [[组合数学 (Fall 2025)/Extremal graph theory|Extremal graph theory | 极值图论]] ([http://tcs.nju.edu.cn/slides/comb2025/ExtremalGraphs.pdf slides])

= Resources =
* [http://math.mit.edu/~fox/MAT307.html Combinatorics course] by Jacob Fox
* [https://yufeizhao.com/pm/ Probabilistic Methods in Combinatorics] and [https://yufeizhao.com/gtacbook/ Graph Theory and Additive Combinatorics] by Yufei Zhao
* [https://www.math.uvic.ca/~noelj/combinatoricsLectures.html Combinatorics Lecture Videos online]
* [https://www.math.ucla.edu/~pak/lectures/Math-Videos/comb-videos.htm Collection of Combinatorics Videos]

= Concepts =
* [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient]
* [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way]
* [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number]
* [http://en.wikipedia.org/wiki/Multiset#Formal_definition Multiset]
* [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset#Counting_multisets <math>k</math>-multisets on a set]
* [http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients Multinomial coefficients]
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind]
* [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number]
** [http://en.wikipedia.org/wiki/Young_tableau Young tableau]
* [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]
* [http://en.wikipedia.org/wiki/Catalan_number Catalan number]
* [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series]
* [http://en.wikipedia.org/wiki/Binomial_series Newton's formula]
* [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method])
* [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius inversion formula]
* [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages]
* [http://en.wikipedia.org/wiki/Ryser%27s_formula#Ryser_formula Ryser's formula]
* [http://en.wikipedia.org/wiki/Euler_totient Euler totient function]
* [https://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside's lemma]
** [https://en.wikipedia.org/wiki/Group_action Group action]
** [https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers Orbits]
* [https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Pólya enumeration theorem]
** [https://en.wikipedia.org/wiki/Permutation_group Permutation group]
** [https://en.wikipedia.org/wiki/Cycle_index Cycle index]
* [http://en.wikipedia.org/wiki/Cayley_formula Cayley's formula]
** [http://en.wikipedia.org/wiki/Prüfer_sequence Prüfer code for trees]
** [http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem Kirchhoff's matrix-tree theorem]
* [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma]
* [http://en.wikipedia.org/wiki/Sperner's_lemma Sperner's lemma] and [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer fixed point theorem]
* [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
:* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem]
* [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method]
* [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs]
* [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
* [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
* Two analytic inequalities:
:*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
:* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
* [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower lemma and conjecture]
* [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
* [https://en.wikipedia.org/wiki/Sperner%27s_theorem Sperner's theorem]
** [https://en.wikipedia.org/wiki/Sperner_family Sperner system] or '''antichain'''
* [https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma Sauer–Shelah lemma]
** [https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension Vapnik–Chervonenkis dimension]
* [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal–Katona theorem]
* [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
:*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
:*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
:*[https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem Van der Waerden's theorem]
:*[https://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem Hales–Jewett theorem]
* [https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem Hall's theorem ] (the marriage theorem)
:* [https://en.wikipedia.org/wiki/Doubly_stochastic_matrix Birkhoff–Von Neumann theorem]
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
* [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
* The [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
:* [https://en.wikipedia.org/wiki/Menger%27s_theorem Menger's theorem]
:* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]
* [https://en.wikipedia.org/wiki/Linear_programming Linear programming]
** [https://en.wikipedia.org/wiki/Dual_linear_program Duality]
** [https://en.wikipedia.org/wiki/Unimodular_matrix Unimodularity]
* [https://en.wikipedia.org/wiki/Matroid Matroid]

组合数学 (Spring 2025)/Problem Set 2

2025-04-13T11:33:13Z

Gispzjz: /* Problem 3 */

== Problem 1 ==
Let <math>0\leq l\leq k\leq n</math>. Show that <math>\binom{n}{k}\binom{k}{l} = \binom{n}{l}\binom{n-l}{k-l}</math>.

== Problem 2 ==
Prove the following claims related to Cayley's formula:

* The number of rooted labelled forests with <math>n</math> vertices is given by <math>(n+1)^{n-1}</math>.

* The number of unrooted labelled forests with <math>n</math> vertices and <math>k</math> connected components such that <math>1,\dots,k</math> belong to distinct components is given by <math>kn^{n-k-1}</math>.

* The number of unrooted labelled trees with <math>n</math> vertices of degrees <math>d_1,d_2,\dots,d_n</math> respectively is given by <math>\binom{n-2}{d_1-1,d_2-1,\dots,d_n-1}=\frac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots(d_n-1)!}</math>.

== Problem 3 ==
There are <math>n</math> parking spaces <math>1, 2,...,n</math> available for <math>n</math> drivers. Each
driver has a favorite space, driver <math>i</math> space <math>f (i)</math>, <math>1 ≤ f (i) ≤ n</math>. The drivers
arrive one by one. When driver <math>i</math> arrives he tries to park his car in space
<math>f (i)</math>. If it is taken he moves down the line to take the first free space
greater than <math>f (i)</math>, if any. Example: <math>n = 4, f = 3221</math>; then driver <math>1 →
3, 2 → 2, 3 → 4, 4 → 1</math>, but for <math>f = 2332</math> we have <math>1 → 2, 2 → 3, 3 → 4, 4 →?</math>.
Let <math>p(n)</math> be the number of sequences <math>f</math> that allow each driver to park his
car; <math>f</math> is then called a parking sequence. Prove:
* <math>f</math> is a parking sequence if and only if <math>\#\{i : f (i) ≤ k\} ≥ k</math>.
* <math>p(n) = (n + 1)^{n−1}</math>. This looks like the number of rooted labelled forests with <math>n</math> vertices. Can you find a bijection?

== Problem 4 ==

Solve the following two existence problems:

* You are given <math>n</math> integers <math>a_1,a_2,\dots,a_n</math>, such that for each <math> 1\leq i\leq n</math> it holds that <math>i-n\leq a_i\leq i-1</math>. Show that there exists a '''nonempty''' subsequence (not necessarily consecutive) of these integers, whose sum is equal to <math> 0 </math>. (Hint: Consider <math> b_i=a_i-i </math>)

* You are given two '''multisets''' <math> A </math> and <math> B </math>, both with <math> n </math> integers from <math> 1 </math> to <math> n </math>. Show that there exist two '''nonempty''' subsets <math> A'\subseteq A </math> and <math> B'\subseteq B </math> with equal sum, i.e. <math>\sum\limits_{x\in A'}x=\sum\limits_{y\in B'}y </math> (Hint: Replace the term ''multiset'' by ''sequence'', the term ''subset'' by ''consecutive subsequence'', and the statement is still true. )

== Problem 5 ==

Suppose <math> n \geq 4 </math>, and let <math> H </math> be an <math>n</math>-uniform hypergraph with at most <math> \frac{4^{n−1}}{3^n} </math>
(hyper)edges. Prove that there is a coloring of the vertices of <math> H </math> by four colors so that in every (hyper)edge all four colors are represented.

== Problem 6 ==
Prove that there is an absolute constant <math> c>0 </math> with the following property: let <math> A </math> be an <math> n\times n </math> matrix with pairwise distinct entries. Then there is a permutation of the rows of <math> A </math> so that no column in the permuted matrix contains an increasing subsequence of length at least <math> c\sqrt{n} </math>.

组合数学 (Spring 2025)/第一次作业提交名单

2025-04-10T14:07:52Z

Gispzjz:

如有错漏请邮件联系助教.
如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 211220166 || 王诚昊
|-
| 211830008 || 缪天顺
|-
| 221180133 || 黄可唯
|-
| 221220002 || 沈均文
|-
| 221220022 || 颜树
|-
| 221220029 || 陈俊翰
|-
| 221220034 || 王旭
|-
| 221220052 || 周宇轩
|-
| 221220095 || 曾凡俊
|-
| 221220104 || 刘宇平
|-
| 221220109 || 肖琰
|-
| 221220111 || 于源智
|-
| 221220123 || 董立伟
|-
| 221240035 || 李想
|-
| 221240065 || 何俊渊
|-
| 221240073 || 李恒济
|-
| 221300016 || 白皓瑀
|-
| 221300048 || 姚岐周
|-
| 221300082 || 孟坤泽
|-
| 221502002 || 严宇恒
|-
| 221502003 || 张天钰
|-
| 221502005 || 王昕浩
|-
| 221502007 || 崔毓泽
|-
| 221502010 || 梁志浩
|-
| 221502013 || 贺龄瑞
|-
| 221502017 || 卢君和
|-
| 221502021 || 李尚敖
|-
| 221504012 || 姜湛
|-
| 221840201 || 钟锦立
|-
| 221840207 || 陈逸迪
|-
| 221900059 || 王齐剑
|-
| 221900156 || 韩加瑞
|-
| 221900500 || 李亦非
|-
| 231220012 || 张启越
|-
| 231220073 || 李世昌
|-
| 231300059 || 阮一海
|-
| 231300084 || 柴梓涵
|-
| 231502022 || 胡骏秋
|-
| 231830106 || 朱逸宸
|-
| 231840164 || 高旭
|-
| 231840288 || 魏丽轩
|-
| 231870210 || 沈奕齐
|-
| 502024330019 || 黄锐
|-
| 502024330020 || 蒋承欢
|-
| 502024330065 || 张天泽
|-
| 502024330075 || 周灿
|-
| 522024330036 || 李尚达
|-
| 522024330112 || 叶佳
|-
| 522024330118 || 张弛
|-
| 522024330144 || 刘学彬
|-
| 652024330035 || 杨宇轩
|-
| DZ1833024 || 王竞冕
|-
|}
</center>

组合数学 (Spring 2025)

2025-04-09T04:54:13Z

Gispzjz: /* Announcement */

{{Infobox
|name = Infobox
|bodystyle =
|title = 组合数学 
Combinatorics
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = Wednesday, 2pm-4pm 逸A-322
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = TBA 计算机系 804
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = [[File:LW-combinatorics.jpeg|border|100px]]
|header11 =
|label11 =
|data11 = van Lint and Wilson. ''A course in Combinatorics, 2nd ed.'', Cambridge Univ Press, 2001.
|header12 =
|label12 =
|data12 = [[File:Jukna_book.jpg|border|100px]]
|header13 =
|label13 =
|data13 = Jukna. ''Extremal Combinatorics: With Applications in Computer Science, 2nd ed.'', Springer, 2011.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Combinatorics'' class of Spring 2025. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* '''(2025/03/18)''' 第一次作业已发布，请在 2024/04/02 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A1.pdf')
* '''(2025/04/09)''' 第一次作业已发布，请在 2024/04/23 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A2.pdf')

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** [https://lhy-gispzjz.github.io 刘弘洋] ([mailto:liuhongyang@smail.nju.edu.cn liuhongyang@smail.nju.edu.cn])
** 丁天行
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-322.
* '''Office hour''': TBA
:* '''QQ群''': 260501949 (加入时需报姓名、专业、学号)

= Syllabus =

=== 先修课程 Prerequisites ===
* 离散数学（Discrete Mathematics）
* 线性代数（Linear Algebra）
* 概率论（Probability Theory）

=== Course materials ===
* [[组合数学 (Spring 2025)/Course materials|教材和参考书清单]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
* [[组合数学 (Spring 2025)/Problem Set 1|Problem Set 1]] [[组合数学 (Spring 2025)/第一次作业提交名单|第一次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 2|Problem Set 2]]

= Lecture Notes =
# [[组合数学 (Spring 2025)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2025/BasicEnumeration.pdf slides])
# [[组合数学 (Fall 2025)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2025/GeneratingFunction.pdf slides])
# [[组合数学 (Fall 2025)/Sieve methods|Sieve methods | 筛法]] ([http://tcs.nju.edu.cn/slides/comb2025/PIE.pdf slides])
# [[组合数学 (Fall 2025)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] ([http://tcs.nju.edu.cn/slides/comb2025/Polya.pdf slides])
# [[组合数学 (Fall 2025)/Cayley's formula|Cayley's formula | Cayley公式]] ([http://tcs.nju.edu.cn/slides/comb2025/Cayley.pdf slides])
# [[组合数学 (Fall 2025)/Existence problems|Existence problems | 存在性问题]] ([http://tcs.nju.edu.cn/slides/comb2025/Existence.pdf slides])

= Resources =
* [http://math.mit.edu/~fox/MAT307.html Combinatorics course] by Jacob Fox
* [https://yufeizhao.com/pm/ Probabilistic Methods in Combinatorics] and [https://yufeizhao.com/gtacbook/ Graph Theory and Additive Combinatorics] by Yufei Zhao
* [https://www.math.uvic.ca/~noelj/combinatoricsLectures.html Combinatorics Lecture Videos online]
* [https://www.math.ucla.edu/~pak/lectures/Math-Videos/comb-videos.htm Collection of Combinatorics Videos]

= Concepts =
* [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient]
* [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way]
* [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number]
* [http://en.wikipedia.org/wiki/Multiset#Formal_definition Multiset]
* [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset#Counting_multisets <math>k</math>-multisets on a set]
* [http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients Multinomial coefficients]
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind]
* [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number]
** [http://en.wikipedia.org/wiki/Young_tableau Young tableau]
* [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]
* [http://en.wikipedia.org/wiki/Catalan_number Catalan number]
* [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series]
* [http://en.wikipedia.org/wiki/Binomial_series Newton's formula]
* [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method])
* [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius inversion formula]
* [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages]
* [http://en.wikipedia.org/wiki/Ryser%27s_formula#Ryser_formula Ryser's formula]
* [http://en.wikipedia.org/wiki/Euler_totient Euler totient function]
* [https://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside's lemma]
** [https://en.wikipedia.org/wiki/Group_action Group action]
** [https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers Orbits]
* [https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Pólya enumeration theorem]
** [https://en.wikipedia.org/wiki/Permutation_group Permutation group]
** [https://en.wikipedia.org/wiki/Cycle_index Cycle index]
* [http://en.wikipedia.org/wiki/Cayley_formula Cayley's formula]
** [http://en.wikipedia.org/wiki/Prüfer_sequence Prüfer code for trees]
** [http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem Kirchhoff's matrix-tree theorem]
* [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma]
* [http://en.wikipedia.org/wiki/Sperner's_lemma Sperner's lemma] and [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer fixed point theorem]
* [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
:* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem]
* [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method]
* [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs]
* [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
* [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
* Two analytic inequalities:
:*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
:* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
* [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower lemma and conjecture]
* [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
* [https://en.wikipedia.org/wiki/Sperner%27s_theorem Sperner's theorem]
** [https://en.wikipedia.org/wiki/Sperner_family Sperner system] or '''antichain'''
* [https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma Sauer–Shelah lemma]
** [https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension Vapnik–Chervonenkis dimension]
* [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal–Katona theorem]
* [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
:*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
:*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
:*[https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem Van der Waerden's theorem]
:*[https://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem Hales–Jewett theorem]
* [https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem Hall's theorem ] (the marriage theorem)
:* [https://en.wikipedia.org/wiki/Doubly_stochastic_matrix Birkhoff–Von Neumann theorem]
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
* [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
* The [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
:* [https://en.wikipedia.org/wiki/Menger%27s_theorem Menger's theorem]
:* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]
* [https://en.wikipedia.org/wiki/Linear_programming Linear programming]
** [https://en.wikipedia.org/wiki/Dual_linear_program Duality]
** [https://en.wikipedia.org/wiki/Unimodular_matrix Unimodularity]
* [https://en.wikipedia.org/wiki/Matroid Matroid]

组合数学 (Spring 2025)/Problem Set 2

2025-04-09T03:29:57Z

Gispzjz: /* Problem 6 */

== Problem 1 ==
Let <math>0\leq l\leq k\leq n</math>. Show that <math>\binom{n}{k}\binom{k}{l} = \binom{n}{l}\binom{n-l}{k-l}</math>.

== Problem 2 ==
Prove the following claims related to Cayley's formula:

* The number of rooted labelled forests with <math>n</math> vertices is given by <math>(n+1)^{n-1}</math>.

* The number of unrooted labelled forests with <math>n</math> vertices and <math>k</math> connected components such that <math>1,\dots,k</math> belong to distinct components is given by <math>kn^{n-k-1}</math>.

* The number of unrooted labelled trees with <math>n</math> vertices of degrees <math>d_1,d_2,\dots,d_n</math> respectively is given by <math>\binom{n-2}{d_1-1,d_2-1,\dots,d_n-1}=\frac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots(d_n-1)!}</math>.

== Problem 3 ==
There are <math>n</math> parking spaces <math>1, 2,...,n</math> available for <math>n</math> drivers. Each
driver has a favorite space, driver <math>i</math> space <math>f (i)</math>, <math>1 ≤ f (i) ≤ n</math>. The drivers
arrive one by one. When driver <math>i</math> arrives he tries to park his car in space
<math>f (i)</math>. If it is taken he moves down the line to take the first free space
greater than <math>f (i)</math>, if any. Example: <math>n = 4, f = 3221</math>; then driver <math>1 →
3, 2 → 2, 3 → 4, 4 → 1</math>, but for <math>f = 2332</math> we have <math>1 → 2, 2 → 3, 3 → 4, 2 →?</math>.
Let <math>p(n)</math> be the number of sequences <math>f</math> that allow each driver to park his
car; <math>f</math> is then called a parking sequence. Prove:
* <math>f</math> is a parking sequence if and only if <math>\#\{i : f (i) ≤ k\} ≥ k</math>.
* <math>p(n) = (n + 1)^{n−1}</math>. This looks like the number of rooted labelled forests with <math>n</math> vertices. Can you find a bijection?

== Problem 4 ==

Solve the following two existence problems:

* You are given <math>n</math> integers <math>a_1,a_2,\dots,a_n</math>, such that for each <math> 1\leq i\leq n</math> it holds that <math>i-n\leq a_i\leq i-1</math>. Show that there exists a '''nonempty''' subsequence (not necessarily consecutive) of these integers, whose sum is equal to <math> 0 </math>. (Hint: Consider <math> b_i=a_i-i </math>)

* You are given two '''multisets''' <math> A </math> and <math> B </math>, both with <math> n </math> integers from <math> 1 </math> to <math> n </math>. Show that there exist two '''nonempty''' subsets <math> A'\subseteq A </math> and <math> B'\subseteq B </math> with equal sum, i.e. <math>\sum\limits_{x\in A'}x=\sum\limits_{y\in B'}y </math> (Hint: Replace the term ''multiset'' by ''sequence'', the term ''subset'' by ''consecutive subsequence'', and the statement is still true. )

== Problem 5 ==

Suppose <math> n \geq 4 </math>, and let <math> H </math> be an <math>n</math>-uniform hypergraph with at most <math> \frac{4^{n−1}}{3^n} </math>
(hyper)edges. Prove that there is a coloring of the vertices of <math> H </math> by four colors so that in every (hyper)edge all four colors are represented.

== Problem 6 ==
Prove that there is an absolute constant <math> c>0 </math> with the following property: let <math> A </math> be an <math> n\times n </math> matrix with pairwise distinct entries. Then there is a permutation of the rows of <math> A </math> so that no column in the permuted matrix contains an increasing subsequence of length at least <math> c\sqrt{n} </math>.

组合数学 (Spring 2025)/Problem Set 2

2025-04-09T03:28:51Z

Gispzjz: Created page with "== Problem 1 == Let <math>0\leq l\leq k\leq n</math>. Show that <math>\binom{n}{k}\binom{k}{l} = \binom{n}{l}\binom{n-l}{k-l}</math>. == Problem 2 == Prove the following claims related to Cayley's formula: * The number of rooted labelled forests with <math>n</math> vertices is given by <math>(n+1)^{n-1}</math>. * The number of unrooted labelled forests with <math>n</math> vertices and <math>k</math> connected components such that <math>1,\dots,k</math> belong to disti..."

== Problem 1 ==
Let <math>0\leq l\leq k\leq n</math>. Show that <math>\binom{n}{k}\binom{k}{l} = \binom{n}{l}\binom{n-l}{k-l}</math>.

== Problem 2 ==
Prove the following claims related to Cayley's formula:

* The number of rooted labelled forests with <math>n</math> vertices is given by <math>(n+1)^{n-1}</math>.

* The number of unrooted labelled forests with <math>n</math> vertices and <math>k</math> connected components such that <math>1,\dots,k</math> belong to distinct components is given by <math>kn^{n-k-1}</math>.

* The number of unrooted labelled trees with <math>n</math> vertices of degrees <math>d_1,d_2,\dots,d_n</math> respectively is given by <math>\binom{n-2}{d_1-1,d_2-1,\dots,d_n-1}=\frac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots(d_n-1)!}</math>.

== Problem 3 ==
There are <math>n</math> parking spaces <math>1, 2,...,n</math> available for <math>n</math> drivers. Each
driver has a favorite space, driver <math>i</math> space <math>f (i)</math>, <math>1 ≤ f (i) ≤ n</math>. The drivers
arrive one by one. When driver <math>i</math> arrives he tries to park his car in space
<math>f (i)</math>. If it is taken he moves down the line to take the first free space
greater than <math>f (i)</math>, if any. Example: <math>n = 4, f = 3221</math>; then driver <math>1 →
3, 2 → 2, 3 → 4, 4 → 1</math>, but for <math>f = 2332</math> we have <math>1 → 2, 2 → 3, 3 → 4, 2 →?</math>.
Let <math>p(n)</math> be the number of sequences <math>f</math> that allow each driver to park his
car; <math>f</math> is then called a parking sequence. Prove:
* <math>f</math> is a parking sequence if and only if <math>\#\{i : f (i) ≤ k\} ≥ k</math>.
* <math>p(n) = (n + 1)^{n−1}</math>. This looks like the number of rooted labelled forests with <math>n</math> vertices. Can you find a bijection?

== Problem 4 ==

Solve the following two existence problems:

* You are given <math>n</math> integers <math>a_1,a_2,\dots,a_n</math>, such that for each <math> 1\leq i\leq n</math> it holds that <math>i-n\leq a_i\leq i-1</math>. Show that there exists a '''nonempty''' subsequence (not necessarily consecutive) of these integers, whose sum is equal to <math> 0 </math>. (Hint: Consider <math> b_i=a_i-i </math>)

* You are given two '''multisets''' <math> A </math> and <math> B </math>, both with <math> n </math> integers from <math> 1 </math> to <math> n </math>. Show that there exist two '''nonempty''' subsets <math> A'\subseteq A </math> and <math> B'\subseteq B </math> with equal sum, i.e. <math>\sum\limits_{x\in A'}x=\sum\limits_{y\in B'}y </math> (Hint: Replace the term ''multiset'' by ''sequence'', the term ''subset'' by ''consecutive subsequence'', and the statement is still true. )

== Problem 5 ==

Suppose <math> n \geq 4 </math>, and let <math> H </math> be an <math>n</math>-uniform hypergraph with at most <math> \frac{4^{n−1}}{3^n} </math>
(hyper)edges. Prove that there is a coloring of the vertices of <math> H </math> by four colors so that in every (hyper)edge all four colors are represented.

== Problem 6 ==
Let <math>D=(V,E)</math> be a simple directed graph with '''minimum outdegree''' <math>\delta</math> and '''maximum indegree''' <math>\Delta</math>. Prove:

For any positive integer <math> k</math>, if <math>\mathrm{e}(\Delta \delta+1)(1-\frac{1}{k})^{\delta}<1</math>, then <math>D</math> contains a (directed,simple) cycle of length <math>0\pmod k.</math>

'''Hint''': Let <math>f:V\rightarrow \{0,1,\dots,k-1\}</math> be a random coloring of <math> V </math> obtained by choosing uniformly and independently at random for each <math> v\in V</math>. Try to use Lovász Local Lemma to show something interesting!

组合数学 (Spring 2025)

2025-04-08T19:00:19Z

Gispzjz: /* Assignments */

{{Infobox
|name = Infobox
|bodystyle =
|title = 组合数学 
Combinatorics
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = Wednesday, 2pm-4pm 逸A-322
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = TBA 计算机系 804
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = [[File:LW-combinatorics.jpeg|border|100px]]
|header11 =
|label11 =
|data11 = van Lint and Wilson. ''A course in Combinatorics, 2nd ed.'', Cambridge Univ Press, 2001.
|header12 =
|label12 =
|data12 = [[File:Jukna_book.jpg|border|100px]]
|header13 =
|label13 =
|data13 = Jukna. ''Extremal Combinatorics: With Applications in Computer Science, 2nd ed.'', Springer, 2011.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Combinatorics'' class of Spring 2025. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* '''(2025/03/18)''' 第一次作业已发布，请在 2024/04/02 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A1.pdf')

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** [https://lhy-gispzjz.github.io 刘弘洋] ([mailto:liuhongyang@smail.nju.edu.cn liuhongyang@smail.nju.edu.cn])
** 丁天行
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-322.
* '''Office hour''': TBA
:* '''QQ群''': 260501949 (加入时需报姓名、专业、学号)

= Syllabus =

=== 先修课程 Prerequisites ===
* 离散数学（Discrete Mathematics）
* 线性代数（Linear Algebra）
* 概率论（Probability Theory）

=== Course materials ===
* [[组合数学 (Spring 2025)/Course materials|教材和参考书清单]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
* [[组合数学 (Spring 2025)/Problem Set 1|Problem Set 1]] [[组合数学 (Spring 2025)/第一次作业提交名单|第一次作业提交名单]]
* [[组合数学 (Spring 2025)/Problem Set 2|Problem Set 2]]

= Lecture Notes =
# [[组合数学 (Spring 2025)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2025/BasicEnumeration.pdf slides])
# [[组合数学 (Fall 2025)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2025/GeneratingFunction.pdf slides])
# [[组合数学 (Fall 2025)/Sieve methods|Sieve methods | 筛法]] ([http://tcs.nju.edu.cn/slides/comb2025/PIE.pdf slides])
# [[组合数学 (Fall 2025)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] ([http://tcs.nju.edu.cn/slides/comb2025/Polya.pdf slides])
# [[组合数学 (Fall 2025)/Cayley's formula|Cayley's formula | Cayley公式]] ([http://tcs.nju.edu.cn/slides/comb2025/Cayley.pdf slides])
# [[组合数学 (Fall 2025)/Existence problems|Existence problems | 存在性问题]] ([http://tcs.nju.edu.cn/slides/comb2025/Existence.pdf slides])

= Resources =
* [http://math.mit.edu/~fox/MAT307.html Combinatorics course] by Jacob Fox
* [https://yufeizhao.com/pm/ Probabilistic Methods in Combinatorics] and [https://yufeizhao.com/gtacbook/ Graph Theory and Additive Combinatorics] by Yufei Zhao
* [https://www.math.uvic.ca/~noelj/combinatoricsLectures.html Combinatorics Lecture Videos online]
* [https://www.math.ucla.edu/~pak/lectures/Math-Videos/comb-videos.htm Collection of Combinatorics Videos]

= Concepts =
* [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient]
* [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way]
* [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number]
* [http://en.wikipedia.org/wiki/Multiset#Formal_definition Multiset]
* [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset#Counting_multisets <math>k</math>-multisets on a set]
* [http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients Multinomial coefficients]
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind]
* [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number]
** [http://en.wikipedia.org/wiki/Young_tableau Young tableau]
* [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]
* [http://en.wikipedia.org/wiki/Catalan_number Catalan number]
* [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series]
* [http://en.wikipedia.org/wiki/Binomial_series Newton's formula]
* [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method])
* [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius inversion formula]
* [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages]
* [http://en.wikipedia.org/wiki/Ryser%27s_formula#Ryser_formula Ryser's formula]
* [http://en.wikipedia.org/wiki/Euler_totient Euler totient function]
* [https://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside's lemma]
** [https://en.wikipedia.org/wiki/Group_action Group action]
** [https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers Orbits]
* [https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Pólya enumeration theorem]
** [https://en.wikipedia.org/wiki/Permutation_group Permutation group]
** [https://en.wikipedia.org/wiki/Cycle_index Cycle index]
* [http://en.wikipedia.org/wiki/Cayley_formula Cayley's formula]
** [http://en.wikipedia.org/wiki/Prüfer_sequence Prüfer code for trees]
** [http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem Kirchhoff's matrix-tree theorem]
* [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma]
* [http://en.wikipedia.org/wiki/Sperner's_lemma Sperner's lemma] and [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer fixed point theorem]
* [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
:* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem]
* [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method]
* [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs]
* [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
* [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
* Two analytic inequalities:
:*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
:* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
* [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower lemma and conjecture]
* [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
* [https://en.wikipedia.org/wiki/Sperner%27s_theorem Sperner's theorem]
** [https://en.wikipedia.org/wiki/Sperner_family Sperner system] or '''antichain'''
* [https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma Sauer–Shelah lemma]
** [https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension Vapnik–Chervonenkis dimension]
* [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal–Katona theorem]
* [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
:*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
:*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
:*[https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem Van der Waerden's theorem]
:*[https://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem Hales–Jewett theorem]
* [https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem Hall's theorem ] (the marriage theorem)
:* [https://en.wikipedia.org/wiki/Doubly_stochastic_matrix Birkhoff–Von Neumann theorem]
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
* [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
* The [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
:* [https://en.wikipedia.org/wiki/Menger%27s_theorem Menger's theorem]
:* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]
* [https://en.wikipedia.org/wiki/Linear_programming Linear programming]
** [https://en.wikipedia.org/wiki/Dual_linear_program Duality]
** [https://en.wikipedia.org/wiki/Unimodular_matrix Unimodularity]
* [https://en.wikipedia.org/wiki/Matroid Matroid]

组合数学 (Spring 2025)/第一次作业提交名单

2025-04-07T08:29:43Z

Gispzjz:

如有错漏请邮件联系助教.
如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 211220166 || 王诚昊
|-
| 211830008 || 缪天顺
|-
| 221180133 || 黄可唯
|-
| 221220002 || 沈均文
|-
| 221220029 || 陈俊翰
|-
| 221220034 || 王旭
|-
| 221220052 || 周宇轩
|-
| 221220095 || 曾凡俊
|-
| 221220104 || 刘宇平
|-
| 221220109 || 肖琰
|-
| 221220111 || 于源智
|-
| 221220123 || 董立伟
|-
| 221240035 || 李想
|-
| 221240065 || 何俊渊
|-
| 221240073 || 李恒济
|-
| 221300016 || 白皓瑀
|-
| 221300048 || 姚岐周
|-
| 221300082 || 孟坤泽
|-
| 221502002 || 严宇恒
|-
| 221502003 || 张天钰
|-
| 221502005 || 王昕浩
|-
| 221502007 || 崔毓泽
|-
| 221502010 || 梁志浩
|-
| 221502013 || 贺龄瑞
|-
| 221502017 || 卢君和
|-
| 221502021 || 李尚敖
|-
| 221504012 || 姜湛
|-
| 221840201 || 钟锦立
|-
| 221840207 || 陈逸迪
|-
| 221900059 || 王齐剑
|-
| 221900156 || 韩加瑞
|-
| 221900500 || 李亦非
|-
| 231220012 || 张启越
|-
| 231220073 || 李世昌
|-
| 231300059 || 阮一海
|-
| 231300084 || 柴梓涵
|-
| 231502022 || 胡骏秋
|-
| 231830106 || 朱逸宸
|-
| 231840164 || 高旭
|-
| 231840288 || 魏丽轩
|-
| 231870210 || 沈奕齐
|-
| 502024330019 || 黄锐
|-
| 502024330020 || 蒋承欢
|-
| 502024330065 || 张天泽
|-
| 502024330075 || 周灿
|-
| 522024330036 || 李尚达
|-
| 522024330112 || 叶佳
|-
| 522024330118 || 张弛
|-
| 522024330144 || 刘学彬
|-
| 652024330035 || 杨宇轩
|-
| DZ1833024 || 王竞冕
|-
|}
</center>

组合数学 (Spring 2025)/第一次作业提交名单

2025-04-07T06:36:59Z

Gispzjz: Created page with "如有错漏请邮件联系助教. <center> {| class="wikitable" |- ! 学号 !! 姓名 |- | 211220166 || 王诚昊 |- | 221180133 || 黄可唯 |- | 221220002 || 沈均文 |- | 221220029 || 陈俊翰 |- | 221220034 || 王旭 |- | 221220052 || 周宇轩 |- | 221220104 || 刘宇平 |- | 221220109 || 肖琰 |- | 221220111 || 于源智 |- | 221220123 || 董立伟 |- | 221240035 || 李想 |- | 221240065 || 何俊渊 |- | 221240073 || 李恒济 |- | 221300016 ||..."

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 211220166 || 王诚昊
|-
| 221180133 || 黄可唯
|-
| 221220002 || 沈均文
|-
| 221220029 || 陈俊翰
|-
| 221220034 || 王旭
|-
| 221220052 || 周宇轩
|-
| 221220104 || 刘宇平
|-
| 221220109 || 肖琰
|-
| 221220111 || 于源智
|-
| 221220123 || 董立伟
|-
| 221240035 || 李想
|-
| 221240065 || 何俊渊
|-
| 221240073 || 李恒济
|-
| 221300016 || 白皓瑀
|-
| 221502002 || 严宇恒
|-
| 221502003 || 张天钰
|-
| 221502005 || 王昕浩
|-
| 221502007 || 崔毓泽
|-
| 221502013 || 贺龄瑞
|-
| 221502017 || 卢君和
|-
| 221502021 || 李尚敖
|-
| 221504012 || 姜湛
|-
| 221900059 || 王齐剑
|-
| 221900500 || 李亦非
|-
| 231220073 || 李世昌
|-
| 231300059 || 阮一海
|-
| 231830106 || 朱逸宸
|-
| 231840164 || 高旭
|-
| 231840288 || 魏丽轩
|-
| 231870210 || 沈奕齐
|-
| 502024330020 || 蒋承欢
|-
| 502024330075 || 周灿
|-
| 522024330036 || 李尚达
|-
| 522024330112 || 叶佳
|-
| 522024330144 || 刘学彬
|-
| 652024330035 || 杨宇轩
|-
|}
</center>

组合数学 (Spring 2025)

2025-04-07T06:36:46Z

Gispzjz: /* Assignments */

{{Infobox
|name = Infobox
|bodystyle =
|title = 组合数学 
Combinatorics
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = Wednesday, 2pm-4pm 逸A-322
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = TBA 计算机系 804
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = [[File:LW-combinatorics.jpeg|border|100px]]
|header11 =
|label11 =
|data11 = van Lint and Wilson. ''A course in Combinatorics, 2nd ed.'', Cambridge Univ Press, 2001.
|header12 =
|label12 =
|data12 = [[File:Jukna_book.jpg|border|100px]]
|header13 =
|label13 =
|data13 = Jukna. ''Extremal Combinatorics: With Applications in Computer Science, 2nd ed.'', Springer, 2011.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Combinatorics'' class of Spring 2025. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* '''(2025/03/18)''' 第一次作业已发布，请在 2024/04/02 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A1.pdf')

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** [https://lhy-gispzjz.github.io 刘弘洋] ([mailto:liuhongyang@smail.nju.edu.cn liuhongyang@smail.nju.edu.cn])
** 丁天行
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-322.
* '''Office hour''': TBA
:* '''QQ群''': 260501949 (加入时需报姓名、专业、学号)

= Syllabus =

=== 先修课程 Prerequisites ===
* 离散数学（Discrete Mathematics）
* 线性代数（Linear Algebra）
* 概率论（Probability Theory）

=== Course materials ===
* [[组合数学 (Spring 2025)/Course materials|教材和参考书清单]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
* [[组合数学 (Spring 2025)/Problem Set 1|Problem Set 1]] [[组合数学 (Spring 2025)/第一次作业提交名单|第一次作业提交名单]]

= Lecture Notes =
# [[组合数学 (Spring 2025)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2025/BasicEnumeration.pdf slides])
# [[组合数学 (Fall 2025)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2025/GeneratingFunction.pdf slides])
# [[组合数学 (Fall 2025)/Sieve methods|Sieve methods | 筛法]] ([http://tcs.nju.edu.cn/slides/comb2025/PIE.pdf slides])
# [[组合数学 (Fall 2025)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] ([http://tcs.nju.edu.cn/slides/comb2025/Polya.pdf slides])
# [[组合数学 (Fall 2025)/Cayley's formula|Cayley's formula | Cayley公式]] ([http://tcs.nju.edu.cn/slides/comb2025/Cayley.pdf slides])
# [[组合数学 (Fall 2025)/Existence problems|Existence problems | 存在性问题]] ([http://tcs.nju.edu.cn/slides/comb2025/Existence.pdf slides])

= Resources =
* [http://math.mit.edu/~fox/MAT307.html Combinatorics course] by Jacob Fox
* [https://yufeizhao.com/pm/ Probabilistic Methods in Combinatorics] and [https://yufeizhao.com/gtacbook/ Graph Theory and Additive Combinatorics] by Yufei Zhao
* [https://www.math.uvic.ca/~noelj/combinatoricsLectures.html Combinatorics Lecture Videos online]
* [https://www.math.ucla.edu/~pak/lectures/Math-Videos/comb-videos.htm Collection of Combinatorics Videos]

= Concepts =
* [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient]
* [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way]
* [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number]
* [http://en.wikipedia.org/wiki/Multiset#Formal_definition Multiset]
* [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset#Counting_multisets <math>k</math>-multisets on a set]
* [http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients Multinomial coefficients]
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind]
* [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number]
** [http://en.wikipedia.org/wiki/Young_tableau Young tableau]
* [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]
* [http://en.wikipedia.org/wiki/Catalan_number Catalan number]
* [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series]
* [http://en.wikipedia.org/wiki/Binomial_series Newton's formula]
* [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method])
* [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius inversion formula]
* [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages]
* [http://en.wikipedia.org/wiki/Ryser%27s_formula#Ryser_formula Ryser's formula]
* [http://en.wikipedia.org/wiki/Euler_totient Euler totient function]
* [https://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside's lemma]
** [https://en.wikipedia.org/wiki/Group_action Group action]
** [https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers Orbits]
* [https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Pólya enumeration theorem]
** [https://en.wikipedia.org/wiki/Permutation_group Permutation group]
** [https://en.wikipedia.org/wiki/Cycle_index Cycle index]
* [http://en.wikipedia.org/wiki/Cayley_formula Cayley's formula]
** [http://en.wikipedia.org/wiki/Prüfer_sequence Prüfer code for trees]
** [http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem Kirchhoff's matrix-tree theorem]
* [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma]
* [http://en.wikipedia.org/wiki/Sperner's_lemma Sperner's lemma] and [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer fixed point theorem]
* [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
:* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem]
* [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method]
* [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs]
* [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
* [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
* Two analytic inequalities:
:*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
:* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
* [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower lemma and conjecture]
* [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
* [https://en.wikipedia.org/wiki/Sperner%27s_theorem Sperner's theorem]
** [https://en.wikipedia.org/wiki/Sperner_family Sperner system] or '''antichain'''
* [https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma Sauer–Shelah lemma]
** [https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension Vapnik–Chervonenkis dimension]
* [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal–Katona theorem]
* [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
:*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
:*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
:*[https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem Van der Waerden's theorem]
:*[https://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem Hales–Jewett theorem]
* [https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem Hall's theorem ] (the marriage theorem)
:* [https://en.wikipedia.org/wiki/Doubly_stochastic_matrix Birkhoff–Von Neumann theorem]
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
* [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
* The [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
:* [https://en.wikipedia.org/wiki/Menger%27s_theorem Menger's theorem]
:* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]
* [https://en.wikipedia.org/wiki/Linear_programming Linear programming]
** [https://en.wikipedia.org/wiki/Dual_linear_program Duality]
** [https://en.wikipedia.org/wiki/Unimodular_matrix Unimodularity]
* [https://en.wikipedia.org/wiki/Matroid Matroid]

组合数学 (Spring 2025)

2025-04-07T06:36:38Z

Gispzjz: /* Assignments */

{{Infobox
|name = Infobox
|bodystyle =
|title = 组合数学 
Combinatorics
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = Wednesday, 2pm-4pm 逸A-322
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = TBA 计算机系 804
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = [[File:LW-combinatorics.jpeg|border|100px]]
|header11 =
|label11 =
|data11 = van Lint and Wilson. ''A course in Combinatorics, 2nd ed.'', Cambridge Univ Press, 2001.
|header12 =
|label12 =
|data12 = [[File:Jukna_book.jpg|border|100px]]
|header13 =
|label13 =
|data13 = Jukna. ''Extremal Combinatorics: With Applications in Computer Science, 2nd ed.'', Springer, 2011.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Combinatorics'' class of Spring 2025. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* '''(2025/03/18)''' 第一次作业已发布，请在 2024/04/02 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A1.pdf')

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** [https://lhy-gispzjz.github.io 刘弘洋] ([mailto:liuhongyang@smail.nju.edu.cn liuhongyang@smail.nju.edu.cn])
** 丁天行
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-322.
* '''Office hour''': TBA
:* '''QQ群''': 260501949 (加入时需报姓名、专业、学号)

= Syllabus =

=== 先修课程 Prerequisites ===
* 离散数学（Discrete Mathematics）
* 线性代数（Linear Algebra）
* 概率论（Probability Theory）

=== Course materials ===
* [[组合数学 (Spring 2025)/Course materials|教材和参考书清单]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
* [[组合数学 (Spring 2025)/Problem Set 1|Problem Set 1]] [[组合数学 (Spring 2024)/第一次作业提交名单|第一次作业提交名单]]

= Lecture Notes =
# [[组合数学 (Spring 2025)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2025/BasicEnumeration.pdf slides])
# [[组合数学 (Fall 2025)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2025/GeneratingFunction.pdf slides])
# [[组合数学 (Fall 2025)/Sieve methods|Sieve methods | 筛法]] ([http://tcs.nju.edu.cn/slides/comb2025/PIE.pdf slides])
# [[组合数学 (Fall 2025)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] ([http://tcs.nju.edu.cn/slides/comb2025/Polya.pdf slides])
# [[组合数学 (Fall 2025)/Cayley's formula|Cayley's formula | Cayley公式]] ([http://tcs.nju.edu.cn/slides/comb2025/Cayley.pdf slides])
# [[组合数学 (Fall 2025)/Existence problems|Existence problems | 存在性问题]] ([http://tcs.nju.edu.cn/slides/comb2025/Existence.pdf slides])

= Resources =
* [http://math.mit.edu/~fox/MAT307.html Combinatorics course] by Jacob Fox
* [https://yufeizhao.com/pm/ Probabilistic Methods in Combinatorics] and [https://yufeizhao.com/gtacbook/ Graph Theory and Additive Combinatorics] by Yufei Zhao
* [https://www.math.uvic.ca/~noelj/combinatoricsLectures.html Combinatorics Lecture Videos online]
* [https://www.math.ucla.edu/~pak/lectures/Math-Videos/comb-videos.htm Collection of Combinatorics Videos]

= Concepts =
* [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient]
* [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way]
* [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number]
* [http://en.wikipedia.org/wiki/Multiset#Formal_definition Multiset]
* [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset#Counting_multisets <math>k</math>-multisets on a set]
* [http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients Multinomial coefficients]
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind]
* [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number]
** [http://en.wikipedia.org/wiki/Young_tableau Young tableau]
* [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]
* [http://en.wikipedia.org/wiki/Catalan_number Catalan number]
* [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series]
* [http://en.wikipedia.org/wiki/Binomial_series Newton's formula]
* [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method])
* [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius inversion formula]
* [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages]
* [http://en.wikipedia.org/wiki/Ryser%27s_formula#Ryser_formula Ryser's formula]
* [http://en.wikipedia.org/wiki/Euler_totient Euler totient function]
* [https://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside's lemma]
** [https://en.wikipedia.org/wiki/Group_action Group action]
** [https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers Orbits]
* [https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Pólya enumeration theorem]
** [https://en.wikipedia.org/wiki/Permutation_group Permutation group]
** [https://en.wikipedia.org/wiki/Cycle_index Cycle index]
* [http://en.wikipedia.org/wiki/Cayley_formula Cayley's formula]
** [http://en.wikipedia.org/wiki/Prüfer_sequence Prüfer code for trees]
** [http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem Kirchhoff's matrix-tree theorem]
* [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma]
* [http://en.wikipedia.org/wiki/Sperner's_lemma Sperner's lemma] and [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer fixed point theorem]
* [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
:* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem]
* [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method]
* [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs]
* [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
* [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
* Two analytic inequalities:
:*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
:* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
* [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower lemma and conjecture]
* [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
* [https://en.wikipedia.org/wiki/Sperner%27s_theorem Sperner's theorem]
** [https://en.wikipedia.org/wiki/Sperner_family Sperner system] or '''antichain'''
* [https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma Sauer–Shelah lemma]
** [https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension Vapnik–Chervonenkis dimension]
* [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal–Katona theorem]
* [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
:*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
:*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
:*[https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem Van der Waerden's theorem]
:*[https://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem Hales–Jewett theorem]
* [https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem Hall's theorem ] (the marriage theorem)
:* [https://en.wikipedia.org/wiki/Doubly_stochastic_matrix Birkhoff–Von Neumann theorem]
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
* [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
* The [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
:* [https://en.wikipedia.org/wiki/Menger%27s_theorem Menger's theorem]
:* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]
* [https://en.wikipedia.org/wiki/Linear_programming Linear programming]
** [https://en.wikipedia.org/wiki/Dual_linear_program Duality]
** [https://en.wikipedia.org/wiki/Unimodular_matrix Unimodularity]
* [https://en.wikipedia.org/wiki/Matroid Matroid]

组合数学 (Spring 2025)

2025-03-30T16:32:02Z

Gispzjz: /* Announcement */

{{Infobox
|name = Infobox
|bodystyle =
|title = 组合数学 
Combinatorics
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = Wednesday, 2pm-4pm 逸A-322
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = TBA 计算机系 804
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = [[File:LW-combinatorics.jpeg|border|100px]]
|header11 =
|label11 =
|data11 = van Lint and Wilson. ''A course in Combinatorics, 2nd ed.'', Cambridge Univ Press, 2001.
|header12 =
|label12 =
|data12 = [[File:Jukna_book.jpg|border|100px]]
|header13 =
|label13 =
|data13 = Jukna. ''Extremal Combinatorics: With Applications in Computer Science, 2nd ed.'', Springer, 2011.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Combinatorics'' class of Spring 2025. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* '''(2025/03/18)''' 第一次作业已发布，请在 2024/04/02 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com] (文件名为'学号_姓名_A1.pdf')

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** [https://lhy-gispzjz.github.io 刘弘洋] ([mailto:liuhongyang@smail.nju.edu.cn liuhongyang@smail.nju.edu.cn])
** 丁天行
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-322.
* '''Office hour''': TBA
:* '''QQ群''': 260501949 (加入时需报姓名、专业、学号)

= Syllabus =

=== 先修课程 Prerequisites ===
* 离散数学（Discrete Mathematics）
* 线性代数（Linear Algebra）
* 概率论（Probability Theory）

=== Course materials ===
* [[组合数学 (Spring 2025)/Course materials|教材和参考书清单]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
* [[组合数学 (Spring 2025)/Problem Set 1|Problem Set 1]]

= Lecture Notes =
# [[组合数学 (Spring 2025)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2025/BasicEnumeration.pdf slides])
# [[组合数学 (Fall 2025)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2025/GeneratingFunction.pdf slides])
# [[组合数学 (Fall 2025)/Sieve methods|Sieve methods | 筛法]] ([http://tcs.nju.edu.cn/slides/comb2025/PIE.pdf slides])
# [[组合数学 (Fall 2025)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] ([http://tcs.nju.edu.cn/slides/comb2025/Polya.pdf slides])
# [[组合数学 (Fall 2025)/Cayley's formula|Cayley's formula | Cayley公式]] ([http://tcs.nju.edu.cn/slides/comb2025/Cayley.pdf slides])
# [[组合数学 (Fall 2025)/Existence problems|Existence problems | 存在性问题]] ([http://tcs.nju.edu.cn/slides/comb2025/Existence.pdf slides])

= Resources =
* [http://math.mit.edu/~fox/MAT307.html Combinatorics course] by Jacob Fox
* [https://yufeizhao.com/pm/ Probabilistic Methods in Combinatorics] and [https://yufeizhao.com/gtacbook/ Graph Theory and Additive Combinatorics] by Yufei Zhao
* [https://www.math.uvic.ca/~noelj/combinatoricsLectures.html Combinatorics Lecture Videos online]
* [https://www.math.ucla.edu/~pak/lectures/Math-Videos/comb-videos.htm Collection of Combinatorics Videos]

= Concepts =
* [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient]
* [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way]
* [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number]
* [http://en.wikipedia.org/wiki/Multiset#Formal_definition Multiset]
* [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset#Counting_multisets <math>k</math>-multisets on a set]
* [http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients Multinomial coefficients]
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind]
* [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number]
** [http://en.wikipedia.org/wiki/Young_tableau Young tableau]
* [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]
* [http://en.wikipedia.org/wiki/Catalan_number Catalan number]
* [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series]
* [http://en.wikipedia.org/wiki/Binomial_series Newton's formula]
* [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method])
* [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius inversion formula]
* [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages]
* [http://en.wikipedia.org/wiki/Ryser%27s_formula#Ryser_formula Ryser's formula]
* [http://en.wikipedia.org/wiki/Euler_totient Euler totient function]
* [https://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside's lemma]
** [https://en.wikipedia.org/wiki/Group_action Group action]
** [https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers Orbits]
* [https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Pólya enumeration theorem]
** [https://en.wikipedia.org/wiki/Permutation_group Permutation group]
** [https://en.wikipedia.org/wiki/Cycle_index Cycle index]
* [http://en.wikipedia.org/wiki/Cayley_formula Cayley's formula]
** [http://en.wikipedia.org/wiki/Prüfer_sequence Prüfer code for trees]
** [http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem Kirchhoff's matrix-tree theorem]
* [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma]
* [http://en.wikipedia.org/wiki/Sperner's_lemma Sperner's lemma] and [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer fixed point theorem]
* [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
:* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem]
* [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method]
* [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs]
* [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
* [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
* Two analytic inequalities:
:*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
:* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
* [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower lemma and conjecture]
* [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
* [https://en.wikipedia.org/wiki/Sperner%27s_theorem Sperner's theorem]
** [https://en.wikipedia.org/wiki/Sperner_family Sperner system] or '''antichain'''
* [https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma Sauer–Shelah lemma]
** [https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension Vapnik–Chervonenkis dimension]
* [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal–Katona theorem]
* [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
:*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
:*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
:*[https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem Van der Waerden's theorem]
:*[https://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem Hales–Jewett theorem]
* [https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem Hall's theorem ] (the marriage theorem)
:* [https://en.wikipedia.org/wiki/Doubly_stochastic_matrix Birkhoff–Von Neumann theorem]
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
* [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
* The [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
:* [https://en.wikipedia.org/wiki/Menger%27s_theorem Menger's theorem]
:* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]
* [https://en.wikipedia.org/wiki/Linear_programming Linear programming]
** [https://en.wikipedia.org/wiki/Dual_linear_program Duality]
** [https://en.wikipedia.org/wiki/Unimodular_matrix Unimodularity]
* [https://en.wikipedia.org/wiki/Matroid Matroid]

组合数学 (Spring 2025)/Problem Set 1

2025-03-20T04:39:08Z

Gispzjz:

== Problem 1 ==

Fix positive integers <math>n</math> and <math>k</math>. Let <math>S</math> be a set with <math>|S|=n</math>. Find the numbers of <math>k</math>-tuples <math>(T_1,T_2,\dots,T_k)</math> of subsets <math>T_i</math> of <math>S</math> subject to each of the following conditions separately. Briefly explain your answer.
* <math>T_1\subseteq T_2\subseteq \cdots \subseteq T_k.</math>
* The <math> T_i</math>s are pairwise disjoint.
* <math> T_1\cup T_2\cup \cdots T_k=S</math>.

== Problem 2 ==
Give a combinatorial proof to show that, for <math>0 \leq k \leq n</math>,

<center><math> \binom{n}{2} = \binom{k}{2} + k(n-k) + \binom{n-k}{2}. </math></center>

Hint: <math>\binom{n}{2}</math> is the number of edges in a complete graph on <math>n</math> vertices.

== Problem 3 ==
Fix <math>n, x</math>, show combinatorially that
<math>
\sum_{m=0}^{n} \binom{m}{x}\binom{n-m}{x} = \binom{n+1}{2x+1}.
</math>

Hint: Count the number of ways to choose a subset of size <math>2x+1</math> from <math>\{0,1,2,\dots,n\}</math> by considering the middle element of the subset.

== Problem 4 ==
Let <math>f(n,j,k)</math> represent the number of ways to decompose <math>n</math> into the sum of <math>k</math> non-negative numbers <math>n = a_1 + a_2 + \dots + a_k</math>, such that each <math>a_i </math> is less than <math>j</math>.

We have the following formula for <math>f(n,j,k)</math>:

<center><math>f(n,j,k) = \sum_{r+sj=n} (-1)^s \binom{k+r-1}{r}\binom{k}{s},</math></center>

where the sum is taken over all pairs of <math>(r,s)\in \mathbb{N}</math>.

<ul>
<li>Provide a proof using generating functions.</li>
<li>Provide a proof using the inclusion-exclusion principle.</li>
</ul>

== Problem 5 ==

For any integer <math>n\geq 1</math>, let <math>F_n</math> denote the <math>n</math>-th Fibonacci number.

* Show that <math>F_{n+1}=\sum\limits_{k=0}^{n}\binom{n-k}{k}</math>.

* Show that the number of ordered pairs <math>(S,T)</math> of subsets of <math>[n]</math> satisfying <math>s > |T|</math> for all <math>s \in S</math> and <math>t > |S|</math> for all <math>t \in T</math> is equal to <math>F_{2n+2}</math>. (Hint: The formula proven in Problem 3 might be useful.)

== Problem 6 ==
Identify necklaces of two types of colored beads with their duals obtained by switching the colors of the beads. (We can now distinguish between the two colors, but we can't tell which is which.) Count the number of dintinct configurations with <math> n=10 </math> and dihedral equivalence.

For example, with <math> n=6 </math> and dihedral equivalence, there are <math>8</math> distinct configurations: <math>000000,000001,000011,000101,001001,000111,001011,010101</math>.

组合数学 (Spring 2025)/Problem Set 1

2025-03-16T15:32:30Z

Gispzjz: /* Problem 4 */

== Problem 1 ==

Fix positive integers <math>n</math> and <math>k</math>. Let <math>S</math> be a set with <math>|S|=n</math>. Find the numbers of <math>k</math>-tuples <math>(T_1,T_2,\dots,T_k)</math> of subsets <math>T_i</math> of <math>S</math> subject to each of the following conditions separately. Briefly explain your answer.
* <math>T_1\subseteq T_2\subseteq \cdots \subseteq T_k.</math>
* The <math> T_i</math>s are pairwise disjoint.
* <math> T_1\cup T_2\cup \cdots T_k=S</math>.

== Problem 2 ==
Give a combinatorial proof to show that, for <math>0 \leq k \leq n</math>,

<center><math> \binom{n}{2} = \binom{k}{2} + k(n-k) + \binom{n-k}{2}. </math></center>

Hint: <math>\binom{n}{2}</math> is the number of edges in a complete graph on <math>n</math> vertices.

== Problem 3 ==
Fix <math>n, x</math>, show combinatorially that
<math>
\sum_{m=0}^{n} \binom{m}{x}\binom{n-m}{x} = \binom{n+1}{2x+1}.
</math>

Hint: Count the number of ways to choose a subset of size <math>2x+1</math> from <math>\{0,1,2,\dots,n\}</math> by considering the middle element of the subset.

== Problem 4 ==
Let <math>f(n,j,k)</math> represent the number of ways to decompose <math>n</math> into the sum of <math>k</math> non-negative numbers <math>n = a_1 + a_2 + \dots + a_k</math>, such that each <math>a_i </math> is less than <math>j</math>.

We have the following formula for <math>f(n,j,k)</math>:

<center><math>f(n,j,k) = \sum_{r+sj=n} (-1)^s \binom{k+r-1}{r}\binom{k}{s},</math></center>

where the sum is taken over all pairs of <math>(r,s)\in \mathbb{N}</math>.

<ul>
<li>Provide a proof using generating functions.</li>
<li>Provide a proof using the inclusion-exclusion principle.</li>
</ul>

== Problem 5 ==

For any integer <math>n\geq 1</math>, let <math>F_n</math> denote the <math>n</math>-th Fibonacci number.

* Show that <math>F_{n+1}=\sum\limits_{k=0}^{n}\binom{n-k}{k}</math>.

* Show that the number of ordered pairs <math>(S,T)</math> of subsets of <math>[n]</math> satisfying <math>s > |T|</math> for all <math>s \in S</math> and <math>t > |S|</math> for all <math>t \in T</math> is equal to <math>F_{2n+2}</math>. (Hint: The formula proven in Problem 4 might be useful.)

== Problem 6 ==
Identify necklaces of two types of colored beads with their duals obtained by switching the colors of the beads. (We can now distinguish between the two colors, but we can't tell which is which.) Count the number of dintinct configurations with <math> n=10 </math> and dihedral equivalence.

For example, with <math> n=6 </math> and dihedral equivalence, there are <math>8</math> distinct configurations: <math>000000,000001,000011,000101,001001,000111,001011,010101</math>.

组合数学 (Spring 2025)/Problem Set 1

2025-03-16T15:30:23Z

Gispzjz: /* Problem 4 */

== Problem 1 ==

Fix positive integers <math>n</math> and <math>k</math>. Let <math>S</math> be a set with <math>|S|=n</math>. Find the numbers of <math>k</math>-tuples <math>(T_1,T_2,\dots,T_k)</math> of subsets <math>T_i</math> of <math>S</math> subject to each of the following conditions separately. Briefly explain your answer.
* <math>T_1\subseteq T_2\subseteq \cdots \subseteq T_k.</math>
* The <math> T_i</math>s are pairwise disjoint.
* <math> T_1\cup T_2\cup \cdots T_k=S</math>.

== Problem 2 ==
Give a combinatorial proof to show that, for <math>0 \leq k \leq n</math>,

<center><math> \binom{n}{2} = \binom{k}{2} + k(n-k) + \binom{n-k}{2}. </math></center>

Hint: <math>\binom{n}{2}</math> is the number of edges in a complete graph on <math>n</math> vertices.

== Problem 3 ==
Fix <math>n, x</math>, show combinatorially that
<math>
\sum_{m=0}^{n} \binom{m}{x}\binom{n-m}{x} = \binom{n+1}{2x+1}.
</math>

Hint: Count the number of ways to choose a subset of size <math>2x+1</math> from <math>\{0,1,2,\dots,n\}</math> by considering the middle element of the subset.

== Problem 4 ==
Let <math>f(n,j,k)</math> represent the number of ways to decompose <math>n</math> into the sum of <math>k</math> natural numbers <math>n = a_1 + a_2 + \dots + a_k</math>, such that each <math>a_i < j</math>.

We have the following formula for <math>f(n,j,k)</math>:

<center><math>f(n,j,k) = \sum_{r+sj=n} (-1)^s \binom{k+r-1}{r}\binom{k}{s},</math></center>

where the sum is taken over all pairs of <math>(r,s)\in \mathbb{N}</math>.

<ul>
<li>Provide a proof using generating functions.</li>
<li>Provide a proof using the inclusion-exclusion principle.</li>
</ul>

== Problem 5 ==

For any integer <math>n\geq 1</math>, let <math>F_n</math> denote the <math>n</math>-th Fibonacci number.

* Show that <math>F_{n+1}=\sum\limits_{k=0}^{n}\binom{n-k}{k}</math>.

* Show that the number of ordered pairs <math>(S,T)</math> of subsets of <math>[n]</math> satisfying <math>s > |T|</math> for all <math>s \in S</math> and <math>t > |S|</math> for all <math>t \in T</math> is equal to <math>F_{2n+2}</math>. (Hint: The formula proven in Problem 4 might be useful.)

== Problem 6 ==
Identify necklaces of two types of colored beads with their duals obtained by switching the colors of the beads. (We can now distinguish between the two colors, but we can't tell which is which.) Count the number of dintinct configurations with <math> n=10 </math> and dihedral equivalence.

For example, with <math> n=6 </math> and dihedral equivalence, there are <math>8</math> distinct configurations: <math>000000,000001,000011,000101,001001,000111,001011,010101</math>.

组合数学 (Spring 2025)/Problem Set 1

2025-03-16T15:29:55Z

Gispzjz: /* Problem 4 */

== Problem 1 ==

Fix positive integers <math>n</math> and <math>k</math>. Let <math>S</math> be a set with <math>|S|=n</math>. Find the numbers of <math>k</math>-tuples <math>(T_1,T_2,\dots,T_k)</math> of subsets <math>T_i</math> of <math>S</math> subject to each of the following conditions separately. Briefly explain your answer.
* <math>T_1\subseteq T_2\subseteq \cdots \subseteq T_k.</math>
* The <math> T_i</math>s are pairwise disjoint.
* <math> T_1\cup T_2\cup \cdots T_k=S</math>.

== Problem 2 ==
Give a combinatorial proof to show that, for <math>0 \leq k \leq n</math>,

<center><math> \binom{n}{2} = \binom{k}{2} + k(n-k) + \binom{n-k}{2}. </math></center>

Hint: <math>\binom{n}{2}</math> is the number of edges in a complete graph on <math>n</math> vertices.

== Problem 3 ==
Fix <math>n, x</math>, show combinatorially that
<math>
\sum_{m=0}^{n} \binom{m}{x}\binom{n-m}{x} = \binom{n+1}{2x+1}.
</math>

Hint: Count the number of ways to choose a subset of size <math>2x+1</math> from <math>\{0,1,2,\dots,n\}</math> by considering the middle element of the subset.

== Problem 4 ==
Let <math>f(n,j,k)</math> represent the number of ways to decompose <math>n</math> into the sum of <math>k</math> natural numbers <math>n = a_1 + a_2 + \dots + a_k</math>, such that each <math>a_i < j</math>.

We have the following formula for <math>f(n,j,k)</math>:

<center><math>f(n,j,k) = \sum_{r+sj=n} (-1)^s \binom{k+r-1}{r}\binom{k}{s},</math></center>

where the sum is taken over all pairs of <math>(r,s)\in \mathrm{N}</math>.

<ul>
<li>Provide a proof using generating functions.</li>
<li>Provide a proof using the inclusion-exclusion principle.</li>
</ul>

== Problem 5 ==

For any integer <math>n\geq 1</math>, let <math>F_n</math> denote the <math>n</math>-th Fibonacci number.

* Show that <math>F_{n+1}=\sum\limits_{k=0}^{n}\binom{n-k}{k}</math>.

* Show that the number of ordered pairs <math>(S,T)</math> of subsets of <math>[n]</math> satisfying <math>s > |T|</math> for all <math>s \in S</math> and <math>t > |S|</math> for all <math>t \in T</math> is equal to <math>F_{2n+2}</math>. (Hint: The formula proven in Problem 4 might be useful.)

== Problem 6 ==
Identify necklaces of two types of colored beads with their duals obtained by switching the colors of the beads. (We can now distinguish between the two colors, but we can't tell which is which.) Count the number of dintinct configurations with <math> n=10 </math> and dihedral equivalence.

For example, with <math> n=6 </math> and dihedral equivalence, there are <math>8</math> distinct configurations: <math>000000,000001,000011,000101,001001,000111,001011,010101</math>.

组合数学 (Spring 2025)/Problem Set 1

2025-03-16T15:29:45Z

Gispzjz:

== Problem 1 ==

Fix positive integers <math>n</math> and <math>k</math>. Let <math>S</math> be a set with <math>|S|=n</math>. Find the numbers of <math>k</math>-tuples <math>(T_1,T_2,\dots,T_k)</math> of subsets <math>T_i</math> of <math>S</math> subject to each of the following conditions separately. Briefly explain your answer.
* <math>T_1\subseteq T_2\subseteq \cdots \subseteq T_k.</math>
* The <math> T_i</math>s are pairwise disjoint.
* <math> T_1\cup T_2\cup \cdots T_k=S</math>.

== Problem 2 ==
Give a combinatorial proof to show that, for <math>0 \leq k \leq n</math>,

<center><math> \binom{n}{2} = \binom{k}{2} + k(n-k) + \binom{n-k}{2}. </math></center>

Hint: <math>\binom{n}{2}</math> is the number of edges in a complete graph on <math>n</math> vertices.

== Problem 3 ==
Fix <math>n, x</math>, show combinatorially that
<math>
\sum_{m=0}^{n} \binom{m}{x}\binom{n-m}{x} = \binom{n+1}{2x+1}.
</math>

Hint: Count the number of ways to choose a subset of size <math>2x+1</math> from <math>\{0,1,2,\dots,n\}</math> by considering the middle element of the subset.

== Problem 4 ==
Let <math>f(n,j,k)</math> represent the number of ways to decompose <math>n</math> into the sum of <math>k</math> natural numbers <math>n = a_1 + a_2 + \dots + a_k</math>, such that each <math>a_i < j</math>.

We have the following formula for <math>f(n,j,k)</math>:

<center><math>f(n,j,k) = \sum_{r+sj=n} (-1)^s \binom{k+r-1}{r}\binom{k}{s},</math></center>

where the sum is taken over all pairs of <math>(r,s)\in \mathcal{N}</math>.

<ul>
<li>Provide a proof using generating functions.</li>
<li>Provide a proof using the inclusion-exclusion principle.</li>
</ul>

== Problem 5 ==

For any integer <math>n\geq 1</math>, let <math>F_n</math> denote the <math>n</math>-th Fibonacci number.

* Show that <math>F_{n+1}=\sum\limits_{k=0}^{n}\binom{n-k}{k}</math>.

* Show that the number of ordered pairs <math>(S,T)</math> of subsets of <math>[n]</math> satisfying <math>s > |T|</math> for all <math>s \in S</math> and <math>t > |S|</math> for all <math>t \in T</math> is equal to <math>F_{2n+2}</math>. (Hint: The formula proven in Problem 4 might be useful.)

== Problem 6 ==
Identify necklaces of two types of colored beads with their duals obtained by switching the colors of the beads. (We can now distinguish between the two colors, but we can't tell which is which.) Count the number of dintinct configurations with <math> n=10 </math> and dihedral equivalence.

For example, with <math> n=6 </math> and dihedral equivalence, there are <math>8</math> distinct configurations: <math>000000,000001,000011,000101,001001,000111,001011,010101</math>.

组合数学 (Spring 2025)/Problem Set 1

2025-03-16T15:25:16Z

Gispzjz:

== Problem 1 ==

Fix positive integers <math>n</math> and <math>k</math>. Let <math>S</math> be a set with <math>|S|=n</math>. Find the numbers of <math>k</math>-tuples <math>(T_1,T_2,\dots,T_k)</math> of subsets <math>T_i</math> of <math>S</math> subject to each of the following conditions separately. Briefly explain your answer.
* <math>T_1\subseteq T_2\subseteq \cdots \subseteq T_k.</math>
* The <math> T_i</math>s are pairwise disjoint.
* <math> T_1\cup T_2\cup \cdots T_k=S</math>.

== Problem 2 ==
Give a combinatorial proof to show that, for <math>0 \leq k \leq n</math>,

<center><math> \binom{n}{2} = \binom{k}{2} + k(n-k) + \binom{n-k}{2}. </math></center>

Hint: <math>\binom{n}{2}</math> is the number of edges in a complete graph on <math>n</math> vertices.

== Problem 3 ==
Fix <math>n, x</math>, show combinatorially that
<math>
\sum_{m=0}^{n} \binom{m}{x}\binom{n-m}{x} = \binom{n+1}{2x+1}.
</math>

Hint: Count the number of ways to choose a subset of size <math>2x+1</math> from <math>\{0,1,2,\dots,n\}</math> by considering the middle element of the subset.

== Problem 4 ==
Let <math>f(n,j,k)</math> represent the number of ways to decompose <math>n</math> into the sum of <math>k</math> natural numbers <math>n = a_1 + a_2 + \dots + a_k</math>, such that each <math>a_i < j</math>.

We have the following formula for <math>f(n,j,k)</math>:

<center><math>f(n,j,k) = \sum_{r+sj=n} (-1)^s \binom{k+r-1}{r}\binom{k}{s},</math></center>

where the sum is taken over all pairs of natural numbers <math>(r,s)</math>.

<ul>
<li>Provide a proof using generating functions.</li>
<li>Provide a proof using the inclusion-exclusion principle.</li>
</ul>

== Problem 5 ==

For any integer <math>n\geq 1</math>, let <math>F_n</math> denote the <math>n</math>-th Fibonacci number.

* Show that <math>F_{n+1}=\sum\limits_{k=0}^{n}\binom{n-k}{k}</math>.

* Show that the number of ordered pairs <math>(S,T)</math> of subsets of <math>[n]</math> satisfying <math>s > |T|</math> for all <math>s \in S</math> and <math>t > |S|</math> for all <math>t \in T</math> is equal to <math>F_{2n+2}</math>. (Hint: The formula proven in Problem 4 might be useful.)

== Problem 6 ==
Identify necklaces of two types of colored beads with their duals obtained by switching the colors of the beads. (We can now distinguish between the two colors, but we can't tell which is which.) Count the number of dintinct configurations with <math> n=10 </math> and dihedral equivalence.

For example, with <math> n=6 </math> and dihedral equivalence, there are <math>8</math> distinct configurations: <math>000000,000001,000011,000101,001001,000111,001011,010101</math>.

组合数学 (Spring 2025)

2025-03-16T15:14:56Z

Gispzjz: /* Announcement */

{{Infobox
|name = Infobox
|bodystyle =
|title = 组合数学 
Combinatorics
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = Wednesday, 2pm-4pm 逸A-322
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = TBA 计算机系 804
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = [[File:LW-combinatorics.jpeg|border|100px]]
|header11 =
|label11 =
|data11 = van Lint and Wilson. ''A course in Combinatorics, 2nd ed.'', Cambridge Univ Press, 2001.
|header12 =
|label12 =
|data12 = [[File:Jukna_book.jpg|border|100px]]
|header13 =
|label13 =
|data13 = Jukna. ''Extremal Combinatorics: With Applications in Computer Science, 2nd ed.'', Springer, 2011.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Combinatorics'' class of Spring 2025. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* '''(2025/03/18)''' 第一次作业已发布，请在 2024/04/02 上课之前提交到 [mailto:njucomb25@163.com njucomb25@163.com]

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** [https://lhy-gispzjz.github.io 刘弘洋] ([mailto:liuhongyang@smail.nju.edu.cn liuhongyang@smail.nju.edu.cn])
** 丁天行
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-322.
* '''Office hour''': TBA
:* '''QQ群''': 260501949 (加入时需报姓名、专业、学号)

= Syllabus =

=== 先修课程 Prerequisites ===
* 离散数学（Discrete Mathematics）
* 线性代数（Linear Algebra）
* 概率论（Probability Theory）

=== Course materials ===
* [[组合数学 (Spring 2025)/Course materials|教材和参考书清单]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
* [[组合数学 (Spring 2025)/Problem Set 1|Problem Set 1]]

= Lecture Notes =
# [[组合数学 (Spring 2025)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2025/BasicEnumeration.pdf slides])
# [[组合数学 (Fall 2025)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2025/GeneratingFunction.pdf slides])
# [[组合数学 (Fall 2025)/Sieve methods|Sieve methods | 筛法]] ([http://tcs.nju.edu.cn/slides/comb2025/PIE.pdf slides])
# [[组合数学 (Fall 2025)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] ([http://tcs.nju.edu.cn/slides/comb2025/Polya.pdf slides])

= Resources =
* [http://math.mit.edu/~fox/MAT307.html Combinatorics course] by Jacob Fox
* [https://yufeizhao.com/pm/ Probabilistic Methods in Combinatorics] and [https://yufeizhao.com/gtacbook/ Graph Theory and Additive Combinatorics] by Yufei Zhao
* [https://www.math.uvic.ca/~noelj/combinatoricsLectures.html Combinatorics Lecture Videos online]
* [https://www.math.ucla.edu/~pak/lectures/Math-Videos/comb-videos.htm Collection of Combinatorics Videos]

= Concepts =
* [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient]
* [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way]
* [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number]
* [http://en.wikipedia.org/wiki/Multiset#Formal_definition Multiset]
* [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset#Counting_multisets <math>k</math>-multisets on a set]
* [http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients Multinomial coefficients]
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind]
* [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number]
** [http://en.wikipedia.org/wiki/Young_tableau Young tableau]
* [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]
* [http://en.wikipedia.org/wiki/Catalan_number Catalan number]
* [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series]
* [http://en.wikipedia.org/wiki/Binomial_series Newton's formula]
* [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method])
* [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius inversion formula]
* [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages]
* [http://en.wikipedia.org/wiki/Ryser%27s_formula#Ryser_formula Ryser's formula]
* [http://en.wikipedia.org/wiki/Euler_totient Euler totient function]
* [https://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside's lemma]
** [https://en.wikipedia.org/wiki/Group_action Group action]
** [https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers Orbits]
* [https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Pólya enumeration theorem]
** [https://en.wikipedia.org/wiki/Permutation_group Permutation group]
** [https://en.wikipedia.org/wiki/Cycle_index Cycle index]
* [http://en.wikipedia.org/wiki/Cayley_formula Cayley's formula]
** [http://en.wikipedia.org/wiki/Prüfer_sequence Prüfer code for trees]
** [http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem Kirchhoff's matrix-tree theorem]
* [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma]
* [http://en.wikipedia.org/wiki/Sperner's_lemma Sperner's lemma] and [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer fixed point theorem]
* [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
:* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem]
* [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method]
* [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs]
* [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
* [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
* Two analytic inequalities:
:*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
:* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
* [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower lemma and conjecture]
* [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
* [https://en.wikipedia.org/wiki/Sperner%27s_theorem Sperner's theorem]
** [https://en.wikipedia.org/wiki/Sperner_family Sperner system] or '''antichain'''
* [https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma Sauer–Shelah lemma]
** [https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension Vapnik–Chervonenkis dimension]
* [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal–Katona theorem]
* [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
:*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
:*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
:*[https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem Van der Waerden's theorem]
:*[https://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem Hales–Jewett theorem]
* [https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem Hall's theorem ] (the marriage theorem)
:* [https://en.wikipedia.org/wiki/Doubly_stochastic_matrix Birkhoff–Von Neumann theorem]
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
* [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
* The [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
:* [https://en.wikipedia.org/wiki/Menger%27s_theorem Menger's theorem]
:* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]
* [https://en.wikipedia.org/wiki/Linear_programming Linear programming]
** [https://en.wikipedia.org/wiki/Dual_linear_program Duality]
** [https://en.wikipedia.org/wiki/Unimodular_matrix Unimodularity]
* [https://en.wikipedia.org/wiki/Matroid Matroid]

组合数学 (Spring 2025)/Problem Set 1

2025-03-16T15:11:08Z

Gispzjz: /* Problem 2 */

== Problem 1 ==

Fix positive integers <math>n</math> and <math>k</math>. Let <math>S</math> be a set with <math>|S|=n</math>. Find the numbers of <math>k</math>-tuples <math>(T_1,T_2,\dots,T_k)</math> of subsets <math>T_i</math> of <math>S</math> subject to each of the following conditions separately. Briefly explain your answer.
* <math>T_1\subseteq T_2\subseteq \cdots \subseteq T_k.</math>
* The <math> T_i</math>s are pairwise disjoint.
* <math> T_1\cup T_2\cup \cdots T_k=S</math>.

== Problem 2 ==
Give a combinatorial proof to show that, for <math>0 \leq k \leq n</math>,

<center><math> \binom{n}{2} = \binom{k}{2} + k(n-k) + \binom{n-k}{2}. </math></center>

Hint: <math>\binom{n}{2}</math> is the number of edges in a complete graph on <math>n</math> vertices.

== Problem 3 ==
Fix <math>n, j, k</math>. How many integer sequences are there of the form <math>1\leq a_1<a_2<\dots<a_k\leq n</math>, where <math>a_{i+1} - a_i \geq j</math> for all <math>1\leq i\leq k-1</math>?

== Problem 4 ==
Fix <math>n, x</math>, show combinatorially that
<math>
\sum_{m=0}^{n} \binom{m}{x}\binom{n-m}{x} = \binom{n+1}{2x+1}.
</math>

Hint: Count the number of ways to choose a subset of size <math>2x+1</math> from <math>\{0,1,2,\dots,n\}</math> by considering the middle element of the subset.

== Problem 5 ==

For any integer <math>n\geq 1</math>, let <math>F_n</math> denote the <math>n</math>-th Fibonacci number.

* Show that <math>F_{n+1}=\sum\limits_{k=0}^{n}\binom{n-k}{k}</math>.

* Show that the number of ordered pairs <math>(S,T)</math> of subsets of <math>[n]</math> satisfying <math>s > |T|</math> for all <math>s \in S</math> and <math>t > |S|</math> for all <math>t \in T</math> is equal to <math>F_{2n+2}</math>. (Hint: The formula proven in Problem 4 might be useful.)

== Problem 6 ==
Identify necklaces of two types of colored beads with their duals obtained by switching the colors of the beads. (We can now distinguish between the two colors, but we can't tell which is which.) Count the number of dintinct configurations with <math> n=10 </math> and dihedral equivalence.

For example, with <math> n=6 </math> and dihedral equivalence, there are <math>8</math> distinct configurations: <math>000000,000001,000011,000101,001001,000111,001011,010101</math>.

组合数学 (Spring 2025)/Problem Set 1

2025-03-16T15:08:18Z

Gispzjz: /* Problem 4 */

== Problem 1 ==

Fix positive integers <math>n</math> and <math>k</math>. Let <math>S</math> be a set with <math>|S|=n</math>. Find the numbers of <math>k</math>-tuples <math>(T_1,T_2,\dots,T_k)</math> of subsets <math>T_i</math> of <math>S</math> subject to each of the following conditions separately. Briefly explain your answer.
* <math>T_1\subseteq T_2\subseteq \cdots \subseteq T_k.</math>
* The <math> T_i</math>s are pairwise disjoint.
* <math> T_1\cup T_2\cup \cdots T_k=S</math>.

== Problem 2 ==

== Problem 3 ==
Fix <math>n, j, k</math>. How many integer sequences are there of the form <math>1\leq a_1<a_2<\dots<a_k\leq n</math>, where <math>a_{i+1} - a_i \geq j</math> for all <math>1\leq i\leq k-1</math>?

== Problem 4 ==
Fix <math>n, x</math>, show combinatorially that
<math>
\sum_{m=0}^{n} \binom{m}{x}\binom{n-m}{x} = \binom{n+1}{2x+1}.
</math>

Hint: Count the number of ways to choose a subset of size <math>2x+1</math> from <math>\{0,1,2,\dots,n\}</math> by considering the middle element of the subset.

== Problem 5 ==

For any integer <math>n\geq 1</math>, let <math>F_n</math> denote the <math>n</math>-th Fibonacci number.

* Show that <math>F_{n+1}=\sum\limits_{k=0}^{n}\binom{n-k}{k}</math>.

* Show that the number of ordered pairs <math>(S,T)</math> of subsets of <math>[n]</math> satisfying <math>s > |T|</math> for all <math>s \in S</math> and <math>t > |S|</math> for all <math>t \in T</math> is equal to <math>F_{2n+2}</math>. (Hint: The formula proven in Problem 4 might be useful.)

== Problem 6 ==
Identify necklaces of two types of colored beads with their duals obtained by switching the colors of the beads. (We can now distinguish between the two colors, but we can't tell which is which.) Count the number of dintinct configurations with <math> n=10 </math> and dihedral equivalence.

For example, with <math> n=6 </math> and dihedral equivalence, there are <math>8</math> distinct configurations: <math>000000,000001,000011,000101,001001,000111,001011,010101</math>.

组合数学 (Spring 2025)/Problem Set 1

2025-03-16T15:08:05Z

Gispzjz: /* Problem 4 */

== Problem 1 ==

Fix positive integers <math>n</math> and <math>k</math>. Let <math>S</math> be a set with <math>|S|=n</math>. Find the numbers of <math>k</math>-tuples <math>(T_1,T_2,\dots,T_k)</math> of subsets <math>T_i</math> of <math>S</math> subject to each of the following conditions separately. Briefly explain your answer.
* <math>T_1\subseteq T_2\subseteq \cdots \subseteq T_k.</math>
* The <math> T_i</math>s are pairwise disjoint.
* <math> T_1\cup T_2\cup \cdots T_k=S</math>.

== Problem 2 ==

== Problem 3 ==
Fix <math>n, j, k</math>. How many integer sequences are there of the form <math>1\leq a_1<a_2<\dots<a_k\leq n</math>, where <math>a_{i+1} - a_i \geq j</math> for all <math>1\leq i\leq k-1</math>?

== Problem 4 ==
Fix <math>n, x</math>, show combinatorially that
<math>
\sum_{m=0}^{n} \binom{m}{x}\binom{n-m}{x} = \binom{n+1}{2x+1}.
</math>
(Hint: Count the number of ways to choose a subset of size <math>2x+1</math> from <math>\{0,1,2,\dots,n\}</math> by considering the middle element of the subset.)

== Problem 5 ==

For any integer <math>n\geq 1</math>, let <math>F_n</math> denote the <math>n</math>-th Fibonacci number.

* Show that <math>F_{n+1}=\sum\limits_{k=0}^{n}\binom{n-k}{k}</math>.

* Show that the number of ordered pairs <math>(S,T)</math> of subsets of <math>[n]</math> satisfying <math>s > |T|</math> for all <math>s \in S</math> and <math>t > |S|</math> for all <math>t \in T</math> is equal to <math>F_{2n+2}</math>. (Hint: The formula proven in Problem 4 might be useful.)

== Problem 6 ==
Identify necklaces of two types of colored beads with their duals obtained by switching the colors of the beads. (We can now distinguish between the two colors, but we can't tell which is which.) Count the number of dintinct configurations with <math> n=10 </math> and dihedral equivalence.

For example, with <math> n=6 </math> and dihedral equivalence, there are <math>8</math> distinct configurations: <math>000000,000001,000011,000101,001001,000111,001011,010101</math>.

组合数学 (Spring 2025)/Problem Set 1

2025-03-16T15:07:48Z

Gispzjz: /* Problem 5 */

== Problem 1 ==

Fix positive integers <math>n</math> and <math>k</math>. Let <math>S</math> be a set with <math>|S|=n</math>. Find the numbers of <math>k</math>-tuples <math>(T_1,T_2,\dots,T_k)</math> of subsets <math>T_i</math> of <math>S</math> subject to each of the following conditions separately. Briefly explain your answer.
* <math>T_1\subseteq T_2\subseteq \cdots \subseteq T_k.</math>
* The <math> T_i</math>s are pairwise disjoint.
* <math> T_1\cup T_2\cup \cdots T_k=S</math>.

== Problem 2 ==

== Problem 3 ==
Fix <math>n, j, k</math>. How many integer sequences are there of the form <math>1\leq a_1<a_2<\dots<a_k\leq n</math>, where <math>a_{i+1} - a_i \geq j</math> for all <math>1\leq i\leq k-1</math>?

== Problem 4 ==
Fix <math>n, x</math>, show combinatorially that
<math>
\sum_{m=0}^{n} \binom{m}{x}\binom{n-m}{x} = \binom{n+1}{2x+1}.
</math>

Hint: Count the number of ways to choose a subset of size <math>2x+1</math> from <math>\{0,1,2,\dots,n\}</math> by considering the middle element of the subset.

== Problem 5 ==

For any integer <math>n\geq 1</math>, let <math>F_n</math> denote the <math>n</math>-th Fibonacci number.

* Show that <math>F_{n+1}=\sum\limits_{k=0}^{n}\binom{n-k}{k}</math>.

* Show that the number of ordered pairs <math>(S,T)</math> of subsets of <math>[n]</math> satisfying <math>s > |T|</math> for all <math>s \in S</math> and <math>t > |S|</math> for all <math>t \in T</math> is equal to <math>F_{2n+2}</math>. (Hint: The formula proven in Problem 4 might be useful.)

== Problem 6 ==
Identify necklaces of two types of colored beads with their duals obtained by switching the colors of the beads. (We can now distinguish between the two colors, but we can't tell which is which.) Count the number of dintinct configurations with <math> n=10 </math> and dihedral equivalence.

For example, with <math> n=6 </math> and dihedral equivalence, there are <math>8</math> distinct configurations: <math>000000,000001,000011,000101,001001,000111,001011,010101</math>.

组合数学 (Spring 2025)/Problem Set 1

2025-03-16T15:06:41Z

Gispzjz: /* Problem 4 */

== Problem 1 ==

Fix positive integers <math>n</math> and <math>k</math>. Let <math>S</math> be a set with <math>|S|=n</math>. Find the numbers of <math>k</math>-tuples <math>(T_1,T_2,\dots,T_k)</math> of subsets <math>T_i</math> of <math>S</math> subject to each of the following conditions separately. Briefly explain your answer.
* <math>T_1\subseteq T_2\subseteq \cdots \subseteq T_k.</math>
* The <math> T_i</math>s are pairwise disjoint.
* <math> T_1\cup T_2\cup \cdots T_k=S</math>.

== Problem 2 ==

== Problem 3 ==
Fix <math>n, j, k</math>. How many integer sequences are there of the form <math>1\leq a_1<a_2<\dots<a_k\leq n</math>, where <math>a_{i+1} - a_i \geq j</math> for all <math>1\leq i\leq k-1</math>?

== Problem 4 ==
Fix <math>n, x</math>, show combinatorially that
<math>
\sum_{m=0}^{n} \binom{m}{x}\binom{n-m}{x} = \binom{n+1}{2x+1}.
</math>

Hint: Count the number of ways to choose a subset of size <math>2x+1</math> from <math>\{0,1,2,\dots,n\}</math> by considering the middle element of the subset.

== Problem 5 ==

For any integer <math>n\geq 1</math>, let <math>F_n</math> denote the <math>n</math>-th Fibonacci number.

* Show that <math>F_{n+1}=\sum\limits_{k=0}^{n}\binom{n-k}{k}</math>.

* Show that the number of ordered pairs <math>(S,T)</math> of subsets of <math>[n]</math> satisfying <math>s > |T|</math> for all <math>s \in S</math> and <math>t > |S|</math> for all <math>t \in T</math> is equal to <math>F_{2n+2}</math>.

== Problem 6 ==
Identify necklaces of two types of colored beads with their duals obtained by switching the colors of the beads. (We can now distinguish between the two colors, but we can't tell which is which.) Count the number of dintinct configurations with <math> n=10 </math> and dihedral equivalence.

For example, with <math> n=6 </math> and dihedral equivalence, there are <math>8</math> distinct configurations: <math>000000,000001,000011,000101,001001,000111,001011,010101</math>.

组合数学 (Spring 2025)/Problem Set 1

2025-03-16T15:06:17Z

Gispzjz: /* Problem 4 */

== Problem 1 ==

Fix positive integers <math>n</math> and <math>k</math>. Let <math>S</math> be a set with <math>|S|=n</math>. Find the numbers of <math>k</math>-tuples <math>(T_1,T_2,\dots,T_k)</math> of subsets <math>T_i</math> of <math>S</math> subject to each of the following conditions separately. Briefly explain your answer.
* <math>T_1\subseteq T_2\subseteq \cdots \subseteq T_k.</math>
* The <math> T_i</math>s are pairwise disjoint.
* <math> T_1\cup T_2\cup \cdots T_k=S</math>.

== Problem 2 ==

== Problem 3 ==
Fix <math>n, j, k</math>. How many integer sequences are there of the form <math>1\leq a_1<a_2<\dots<a_k\leq n</math>, where <math>a_{i+1} - a_i \geq j</math> for all <math>1\leq i\leq k-1</math>?

== Problem 4 ==
Fix <math>n, x</math>, show combinatorially that
<math>
\sum_{m=0}^{n} \binom{m}{x}\binom{n-m}{x} = \binom{n+1}{2x+1}.
</math>

Hint: Count the number of ways to choose a subset of size <math>2x+1</math> from <math>\{0,1,2,\dots,n\}</math> by considering the middle element of the subset. For each possible middle element <math>m</math>, how many ways can you choose <math>x</math> elements from <math>\{0,1,\dots,m-1\}</math> and <math>x</math> elements from <math>\{m+1,m+2,\dots,n\}</math>?

== Problem 5 ==

For any integer <math>n\geq 1</math>, let <math>F_n</math> denote the <math>n</math>-th Fibonacci number.

* Show that <math>F_{n+1}=\sum\limits_{k=0}^{n}\binom{n-k}{k}</math>.

* Show that the number of ordered pairs <math>(S,T)</math> of subsets of <math>[n]</math> satisfying <math>s > |T|</math> for all <math>s \in S</math> and <math>t > |S|</math> for all <math>t \in T</math> is equal to <math>F_{2n+2}</math>.

== Problem 6 ==
Identify necklaces of two types of colored beads with their duals obtained by switching the colors of the beads. (We can now distinguish between the two colors, but we can't tell which is which.) Count the number of dintinct configurations with <math> n=10 </math> and dihedral equivalence.

For example, with <math> n=6 </math> and dihedral equivalence, there are <math>8</math> distinct configurations: <math>000000,000001,000011,000101,001001,000111,001011,010101</math>.

组合数学 (Spring 2025)/Problem Set 1

2025-03-16T15:06:04Z

Gispzjz: /* Problem 4 */

== Problem 1 ==

Fix positive integers <math>n</math> and <math>k</math>. Let <math>S</math> be a set with <math>|S|=n</math>. Find the numbers of <math>k</math>-tuples <math>(T_1,T_2,\dots,T_k)</math> of subsets <math>T_i</math> of <math>S</math> subject to each of the following conditions separately. Briefly explain your answer.
* <math>T_1\subseteq T_2\subseteq \cdots \subseteq T_k.</math>
* The <math> T_i</math>s are pairwise disjoint.
* <math> T_1\cup T_2\cup \cdots T_k=S</math>.

== Problem 2 ==

== Problem 3 ==
Fix <math>n, j, k</math>. How many integer sequences are there of the form <math>1\leq a_1<a_2<\dots<a_k\leq n</math>, where <math>a_{i+1} - a_i \geq j</math> for all <math>1\leq i\leq k-1</math>?

== Problem 4 ==
Fix <math>n, x</math>, show combinatorially that
<math>
\sum_{m=0}^{n} \binom{m}{x}\binom{n-m}{x} = \binom{n+1}{2x+1}.

Hint: Count the number of ways to choose a subset of size <math>2x+1</math> from <math>\{0,1,2,\dots,n\}</math> by considering the middle element of the subset. For each possible middle element <math>m</math>, how many ways can you choose <math>x</math> elements from <math>\{0,1,\dots,m-1\}</math> and <math>x</math> elements from <math>\{m+1,m+2,\dots,n\}</math>?
</math>

== Problem 5 ==

For any integer <math>n\geq 1</math>, let <math>F_n</math> denote the <math>n</math>-th Fibonacci number.

* Show that <math>F_{n+1}=\sum\limits_{k=0}^{n}\binom{n-k}{k}</math>.

* Show that the number of ordered pairs <math>(S,T)</math> of subsets of <math>[n]</math> satisfying <math>s > |T|</math> for all <math>s \in S</math> and <math>t > |S|</math> for all <math>t \in T</math> is equal to <math>F_{2n+2}</math>.

== Problem 6 ==
Identify necklaces of two types of colored beads with their duals obtained by switching the colors of the beads. (We can now distinguish between the two colors, but we can't tell which is which.) Count the number of dintinct configurations with <math> n=10 </math> and dihedral equivalence.

For example, with <math> n=6 </math> and dihedral equivalence, there are <math>8</math> distinct configurations: <math>000000,000001,000011,000101,001001,000111,001011,010101</math>.

组合数学 (Spring 2025)/Problem Set 1

2025-03-16T15:05:43Z

Gispzjz: /* Problem 4 */

== Problem 1 ==

Fix positive integers <math>n</math> and <math>k</math>. Let <math>S</math> be a set with <math>|S|=n</math>. Find the numbers of <math>k</math>-tuples <math>(T_1,T_2,\dots,T_k)</math> of subsets <math>T_i</math> of <math>S</math> subject to each of the following conditions separately. Briefly explain your answer.
* <math>T_1\subseteq T_2\subseteq \cdots \subseteq T_k.</math>
* The <math> T_i</math>s are pairwise disjoint.
* <math> T_1\cup T_2\cup \cdots T_k=S</math>.

== Problem 2 ==

== Problem 3 ==
Fix <math>n, j, k</math>. How many integer sequences are there of the form <math>1\leq a_1<a_2<\dots<a_k\leq n</math>, where <math>a_{i+1} - a_i \geq j</math> for all <math>1\leq i\leq k-1</math>?

== Problem 4 ==
Fix <math>n, x</math>, show combinatorially that
<math>
\sum_{m=0}^{n} \binom{m}{x}\binom{n-m}{x} = \binom{n+1}{2x+1}. Hint: Count the number of ways to choose a subset of size <math>2x+1</math> from <math>\{0,1,2,\dots,n\}</math> by considering the middle element of the subset. For each possible middle element <math>m</math>, how many ways can you choose <math>x</math> elements from <math>\{0,1,\dots,m-1\}</math> and <math>x</math> elements from <math>\{m+1,m+2,\dots,n\}</math>?
</math>

== Problem 5 ==

For any integer <math>n\geq 1</math>, let <math>F_n</math> denote the <math>n</math>-th Fibonacci number.

* Show that <math>F_{n+1}=\sum\limits_{k=0}^{n}\binom{n-k}{k}</math>.

* Show that the number of ordered pairs <math>(S,T)</math> of subsets of <math>[n]</math> satisfying <math>s > |T|</math> for all <math>s \in S</math> and <math>t > |S|</math> for all <math>t \in T</math> is equal to <math>F_{2n+2}</math>.

== Problem 6 ==
Identify necklaces of two types of colored beads with their duals obtained by switching the colors of the beads. (We can now distinguish between the two colors, but we can't tell which is which.) Count the number of dintinct configurations with <math> n=10 </math> and dihedral equivalence.

For example, with <math> n=6 </math> and dihedral equivalence, there are <math>8</math> distinct configurations: <math>000000,000001,000011,000101,001001,000111,001011,010101</math>.

组合数学 (Spring 2025)/Problem Set 1

2025-03-16T15:04:32Z

Gispzjz: /* Problem 4 */

组合数学 (Spring 2025)/Problem Set 1

2025-03-16T15:03:53Z

Gispzjz: /* Problem 4 */

组合数学 (Spring 2025)/Problem Set 1

2025-03-16T15:03:43Z

Gispzjz: /* Problem 4 */

组合数学 (Spring 2025)/Problem Set 1

2025-03-16T15:03:30Z

Gispzjz: /* Problem 4 */