TCS Wiki - User contributions [en]

组合数学 (Spring 2026)

2026-04-21T12:26:21Z

652024330006: /* 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 逸B-313
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = Tuesday, 2-3pm 计算机系 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 2026. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* '''(2026/03/25)''' 第一次作业已发布，请在 2026/04/08 上课之前提交到 [mailto:njucomb26@163.com njucomb26@163.com] (文件名为'学号_姓名_A1.pdf')
* '''(2026/04/21)''' 第二次作业已发布，请在 2026/05/13 上课之前提交到 [mailto:njucomb26@163.com njucomb26@163.com] (文件名为'学号_姓名_A2.pdf')

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** 丁天行([mailto:652024330006@smail.nju.edu.cn 652024330006@smail.nju.edu.cn])
** 周灿
** 方子伊
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-313.
* '''Office hour''': TBA
:* '''QQ群''': 1090691552 (加入时需报姓名、专业、学号)

= 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 2026)/Problem Set 1|Problem Set 1]]
* [[组合数学 (Spring 2026)/Problem Set 2|Problem Set 2]]

= Lecture Notes =
# [[组合数学 (Spring 2026)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2026/BasicEnumeration.pdf slides])
# [[组合数学 (Spring 2026)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2026/GeneratingFunction.pdf slides])
# [[组合数学 (Fall 2026)/Sieve methods|Sieve methods | 筛法]] ([http://tcs.nju.edu.cn/slides/comb2026/PIE.pdf slides])
# Guest lecture by Prof. Penghui Yao on entropy and counting ([http://tcs.nju.edu.cn/slides/comb2026/entropy.pdf notes])
# [[组合数学 (Fall 2026)/Cayley's formula|Cayley's formula | Cayley公式]] ([http://tcs.nju.edu.cn/slides/comb2026/Cayley.pdf slides])
# [[组合数学 (Fall 2026)/Existence problems|Existence problems | 存在性问题]]
# [[组合数学 (Fall 2026)/The probabilistic method|The probabilistic method | 概率法]] ([http://tcs.nju.edu.cn/slides/comb2026/ProbMethod.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 2026)

2026-04-21T12:25:37Z

652024330006: /* 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 逸B-313
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = Tuesday, 2-3pm 计算机系 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 2026. Students who take this class should check this page periodically for content updates and new announcements.

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

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** 丁天行([mailto:652024330006@smail.nju.edu.cn 652024330006@smail.nju.edu.cn])
** 周灿
** 方子伊
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-313.
* '''Office hour''': TBA
:* '''QQ群''': 1090691552 (加入时需报姓名、专业、学号)

= 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 2026)/Problem Set 1|Problem Set 1]]
* [[组合数学 (Spring 2026)/Problem Set 2|Problem Set 2]]

= Lecture Notes =
# [[组合数学 (Spring 2026)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2026/BasicEnumeration.pdf slides])
# [[组合数学 (Spring 2026)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2026/GeneratingFunction.pdf slides])
# [[组合数学 (Fall 2026)/Sieve methods|Sieve methods | 筛法]] ([http://tcs.nju.edu.cn/slides/comb2026/PIE.pdf slides])
# Guest lecture by Prof. Penghui Yao on entropy and counting ([http://tcs.nju.edu.cn/slides/comb2026/entropy.pdf notes])
# [[组合数学 (Fall 2026)/Cayley's formula|Cayley's formula | Cayley公式]] ([http://tcs.nju.edu.cn/slides/comb2026/Cayley.pdf slides])
# [[组合数学 (Fall 2026)/Existence problems|Existence problems | 存在性问题]]
# [[组合数学 (Fall 2026)/The probabilistic method|The probabilistic method | 概率法]] ([http://tcs.nju.edu.cn/slides/comb2026/ProbMethod.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 2026)/Problem Set 2

2026-04-21T11:55:28Z

652024330006: /* Problem 4 */

== Problem 1 ==

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 2 ==

Use the Lovász Local Lemma to show that, for <math> n \geq k \geq 3 </math>, 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 3 ==

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> is an integer. 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 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=i-a_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''' submultisets <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 ''submultiset'' by ''consecutive subsequence'', and the statement is still true. )

== Problem 5 ==

Let <math>a</math> and <math>b</math> be positive integers, and let <math>(A_1,B_1),(A_2,B_2),\ldots,(A_m,B_m)</math> be <math>m</math> ordered pairs of finite subsets of the positive integers. Suppose that for every <math>i=1,2,\ldots,m</math>, <math>|A_i|=a, |B_i|=b, A_i\cap B_i=\varnothing.</math>

Prove that if <math>m>\binom{a+b}{a},</math> then there exist two distinct indices <math>i\neq j</math> such that <math>A_i\cap B_j=\varnothing.</math>

== Problem 6 ==

For an integer <math>n \geq 2</math>, write <math>[n]=\{1,2,\ldots,n\}.</math>

A set <math>A\subseteq [n]</math> is called subset-sum-distinct if the <math>2^{|A|}</math> sums <math>\sum_{a\in S}a, S\subseteq A,</math> are pairwise distinct, where the empty sum is understood to be <math>0</math>.

Define <math>f(n)</math> to be the largest integer <math>k</math> for which there exists a subset-sum-distinct set <math>A\subseteq [n]</math> with <math>|A|=k</math>.

Prove the following two upper bounds.

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\log_2\log_2 n+c.</math>

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\frac12\log_2\log_2 n+c.</math>

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

2026-04-21T11:10:47Z

652024330006: /* Problem 4 */

== Problem 1 ==

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 2 ==

Use the Lovász Local Lemma to show that, for <math> n \geq k \geq 3 </math>, 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 3 ==

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> is an integer. 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 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''' submultisets <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 ''submultiset'' by ''consecutive subsequence'', and the statement is still true. )

== Problem 5 ==

Let <math>a</math> and <math>b</math> be positive integers, and let <math>(A_1,B_1),(A_2,B_2),\ldots,(A_m,B_m)</math> be <math>m</math> ordered pairs of finite subsets of the positive integers. Suppose that for every <math>i=1,2,\ldots,m</math>, <math>|A_i|=a, |B_i|=b, A_i\cap B_i=\varnothing.</math>

Prove that if <math>m>\binom{a+b}{a},</math> then there exist two distinct indices <math>i\neq j</math> such that <math>A_i\cap B_j=\varnothing.</math>

== Problem 6 ==

For an integer <math>n \geq 2</math>, write <math>[n]=\{1,2,\ldots,n\}.</math>

A set <math>A\subseteq [n]</math> is called subset-sum-distinct if the <math>2^{|A|}</math> sums <math>\sum_{a\in S}a, S\subseteq A,</math> are pairwise distinct, where the empty sum is understood to be <math>0</math>.

Define <math>f(n)</math> to be the largest integer <math>k</math> for which there exists a subset-sum-distinct set <math>A\subseteq [n]</math> with <math>|A|=k</math>.

Prove the following two upper bounds.

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\log_2\log_2 n+c.</math>

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\frac12\log_2\log_2 n+c.</math>

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

2026-04-21T11:09:14Z

652024330006: /* Problem 6 */

== Problem 1 ==

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 2 ==

Use the Lovász Local Lemma to show that, for <math> n \geq k \geq 3 </math>, 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 3 ==

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> is an integer. 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 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 ==

Let <math>a</math> and <math>b</math> be positive integers, and let <math>(A_1,B_1),(A_2,B_2),\ldots,(A_m,B_m)</math> be <math>m</math> ordered pairs of finite subsets of the positive integers. Suppose that for every <math>i=1,2,\ldots,m</math>, <math>|A_i|=a, |B_i|=b, A_i\cap B_i=\varnothing.</math>

Prove that if <math>m>\binom{a+b}{a},</math> then there exist two distinct indices <math>i\neq j</math> such that <math>A_i\cap B_j=\varnothing.</math>

== Problem 6 ==

For an integer <math>n \geq 2</math>, write <math>[n]=\{1,2,\ldots,n\}.</math>

A set <math>A\subseteq [n]</math> is called subset-sum-distinct if the <math>2^{|A|}</math> sums <math>\sum_{a\in S}a, S\subseteq A,</math> are pairwise distinct, where the empty sum is understood to be <math>0</math>.

Define <math>f(n)</math> to be the largest integer <math>k</math> for which there exists a subset-sum-distinct set <math>A\subseteq [n]</math> with <math>|A|=k</math>.

Prove the following two upper bounds.

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\log_2\log_2 n+c.</math>

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\frac12\log_2\log_2 n+c.</math>

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

2026-04-21T11:08:50Z

652024330006: /* Problem 3 */

== Problem 1 ==

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 2 ==

Use the Lovász Local Lemma to show that, for <math> n \geq k \geq 3 </math>, 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 3 ==

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> is an integer. 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 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 ==

Let <math>a</math> and <math>b</math> be positive integers, and let <math>(A_1,B_1),(A_2,B_2),\ldots,(A_m,B_m)</math> be <math>m</math> ordered pairs of finite subsets of the positive integers. Suppose that for every <math>i=1,2,\ldots,m</math>, <math>|A_i|=a, |B_i|=b, A_i\cap B_i=\varnothing.</math>

Prove that if <math>m>\binom{a+b}{a},</math> then there exist two distinct indices <math>i\neq j</math> such that <math>A_i\cap B_j=\varnothing.</math>

== Problem 6 ==

For a positive integer <math>n \geq 2</math>, write <math>[n]=\{1,2,\ldots,n\}.</math>

A set <math>A\subseteq [n]</math> is called subset-sum-distinct if the <math>2^{|A|}</math> sums <math>\sum_{a\in S}a, S\subseteq A,</math> are pairwise distinct, where the empty sum is understood to be <math>0</math>.

Define <math>f(n)</math> to be the largest integer <math>k</math> for which there exists a subset-sum-distinct set <math>A\subseteq [n]</math> with <math>|A|=k</math>.

Prove the following two upper bounds.

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\log_2\log_2 n+c.</math>

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\frac12\log_2\log_2 n+c.</math>

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

2026-04-21T11:08:05Z

652024330006: /* Problem 2 */

== Problem 1 ==

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 2 ==

Use the Lovász Local Lemma to show that, for <math> n \geq k \geq 3 </math>, 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 3 ==

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 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 ==

Let <math>a</math> and <math>b</math> be positive integers, and let <math>(A_1,B_1),(A_2,B_2),\ldots,(A_m,B_m)</math> be <math>m</math> ordered pairs of finite subsets of the positive integers. Suppose that for every <math>i=1,2,\ldots,m</math>, <math>|A_i|=a, |B_i|=b, A_i\cap B_i=\varnothing.</math>

Prove that if <math>m>\binom{a+b}{a},</math> then there exist two distinct indices <math>i\neq j</math> such that <math>A_i\cap B_j=\varnothing.</math>

== Problem 6 ==

For a positive integer <math>n \geq 2</math>, write <math>[n]=\{1,2,\ldots,n\}.</math>

A set <math>A\subseteq [n]</math> is called subset-sum-distinct if the <math>2^{|A|}</math> sums <math>\sum_{a\in S}a, S\subseteq A,</math> are pairwise distinct, where the empty sum is understood to be <math>0</math>.

Define <math>f(n)</math> to be the largest integer <math>k</math> for which there exists a subset-sum-distinct set <math>A\subseteq [n]</math> with <math>|A|=k</math>.

Prove the following two upper bounds.

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\log_2\log_2 n+c.</math>

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\frac12\log_2\log_2 n+c.</math>

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

2026-04-21T11:07:05Z

652024330006: /* Problem 1 */

== Problem 1 ==

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 2 ==

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 3 ==

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 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 ==

Let <math>a</math> and <math>b</math> be positive integers, and let <math>(A_1,B_1),(A_2,B_2),\ldots,(A_m,B_m)</math> be <math>m</math> ordered pairs of finite subsets of the positive integers. Suppose that for every <math>i=1,2,\ldots,m</math>, <math>|A_i|=a, |B_i|=b, A_i\cap B_i=\varnothing.</math>

Prove that if <math>m>\binom{a+b}{a},</math> then there exist two distinct indices <math>i\neq j</math> such that <math>A_i\cap B_j=\varnothing.</math>

== Problem 6 ==

For a positive integer <math>n \geq 2</math>, write <math>[n]=\{1,2,\ldots,n\}.</math>

A set <math>A\subseteq [n]</math> is called subset-sum-distinct if the <math>2^{|A|}</math> sums <math>\sum_{a\in S}a, S\subseteq A,</math> are pairwise distinct, where the empty sum is understood to be <math>0</math>.

Define <math>f(n)</math> to be the largest integer <math>k</math> for which there exists a subset-sum-distinct set <math>A\subseteq [n]</math> with <math>|A|=k</math>.

Prove the following two upper bounds.

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\log_2\log_2 n+c.</math>

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\frac12\log_2\log_2 n+c.</math>

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

2026-04-21T11:06:37Z

652024330006: /* Problem 6 */

== Problem 1 ==

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 2 ==

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 3 ==

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 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 ==

Let <math>a</math> and <math>b</math> be positive integers, and let <math>(A_1,B_1),(A_2,B_2),\ldots,(A_m,B_m)</math> be <math>m</math> ordered pairs of finite subsets of the positive integers. Suppose that for every <math>i=1,2,\ldots,m</math>, <math>|A_i|=a, |B_i|=b, A_i\cap B_i=\varnothing.</math>

Prove that if <math>m>\binom{a+b}{a},</math> then there exist two distinct indices <math>i\neq j</math> such that <math>A_i\cap B_j=\varnothing.</math>

== Problem 6 ==

For a positive integer <math>n \geq 2</math>, write <math>[n]=\{1,2,\ldots,n\}.</math>

A set <math>A\subseteq [n]</math> is called subset-sum-distinct if the <math>2^{|A|}</math> sums <math>\sum_{a\in S}a, S\subseteq A,</math> are pairwise distinct, where the empty sum is understood to be <math>0</math>.

Define <math>f(n)</math> to be the largest integer <math>k</math> for which there exists a subset-sum-distinct set <math>A\subseteq [n]</math> with <math>|A|=k</math>.

Prove the following two upper bounds.

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\log_2\log_2 n+c.</math>

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\frac12\log_2\log_2 n+c.</math>

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

2026-04-21T10:57:40Z

652024330006: /* Problem 4 */

== Problem 1 ==

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 2 ==

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 3 ==

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 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 ==

Let <math>a</math> and <math>b</math> be positive integers, and let <math>(A_1,B_1),(A_2,B_2),\ldots,(A_m,B_m)</math> be <math>m</math> ordered pairs of finite subsets of the positive integers. Suppose that for every <math>i=1,2,\ldots,m</math>, <math>|A_i|=a, |B_i|=b, A_i\cap B_i=\varnothing.</math>

Prove that if <math>m>\binom{a+b}{a},</math> then there exist two distinct indices <math>i\neq j</math> such that <math>A_i\cap B_j=\varnothing.</math>

== Problem 6 ==

For a positive integer <math>n</math>, write <math>[n]=\{1,2,\ldots,n\}.</math>

A set <math>A\subseteq [n]</math> is called subset-sum-distinct if the <math>2^{|A|}</math> sums <math>\sum_{a\in S}a, S\subseteq A,</math> are pairwise distinct, where the empty sum is understood to be <math>0</math>.

Define <math>f(n)</math> to be the largest integer <math>k</math> for which there exists a subset-sum-distinct set <math>A\subseteq [n]</math> with <math>|A|=k</math>.

Prove the following two upper bounds.

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\log_2\log_2 n+c.</math>

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\frac12\log_2\log_2 n+c.</math>

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

2026-04-21T10:56:49Z

652024330006: /* Problem 6 */

== Problem 1 ==

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 2 ==

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 3 ==

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 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 ''consective subsequence'', and the statement is still true. )

== Problem 5 ==

Let <math>a</math> and <math>b</math> be positive integers, and let <math>(A_1,B_1),(A_2,B_2),\ldots,(A_m,B_m)</math> be <math>m</math> ordered pairs of finite subsets of the positive integers. Suppose that for every <math>i=1,2,\ldots,m</math>, <math>|A_i|=a, |B_i|=b, A_i\cap B_i=\varnothing.</math>

Prove that if <math>m>\binom{a+b}{a},</math> then there exist two distinct indices <math>i\neq j</math> such that <math>A_i\cap B_j=\varnothing.</math>

== Problem 6 ==

For a positive integer <math>n</math>, write <math>[n]=\{1,2,\ldots,n\}.</math>

A set <math>A\subseteq [n]</math> is called subset-sum-distinct if the <math>2^{|A|}</math> sums <math>\sum_{a\in S}a, S\subseteq A,</math> are pairwise distinct, where the empty sum is understood to be <math>0</math>.

Define <math>f(n)</math> to be the largest integer <math>k</math> for which there exists a subset-sum-distinct set <math>A\subseteq [n]</math> with <math>|A|=k</math>.

Prove the following two upper bounds.

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\log_2\log_2 n+c.</math>

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\frac12\log_2\log_2 n+c.</math>

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

2026-04-21T10:52:24Z

652024330006: Created page with "== Problem 1 == 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 2 == 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 possibl..."

== Problem 1 ==

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 2 ==

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 3 ==

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 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 ''consective subsequence'', and the statement is still true. )

== Problem 5 ==

Let <math>a</math> and <math>b</math> be positive integers, and let <math>(A_1,B_1),(A_2,B_2),\ldots,(A_m,B_m)</math> be <math>m</math> ordered pairs of finite subsets of the positive integers. Suppose that for every <math>i=1,2,\ldots,m</math>, <math>|A_i|=a, |B_i|=b, A_i\cap B_i=\varnothing.</math>

Prove that if <math>m>\binom{a+b}{a},</math> then there exist two distinct indices <math>i\neq j</math> such that <math>A_i\cap B_j=\varnothing.</math>

== Problem 6 ==

For a positive integer <math>n</math>, write <math>[n]={1,2,\ldots,n}.</math>

A set <math>A\subseteq [n]</math> is called subset-sum-distinct if the <math>2^{|A|}</math> sums <math>\sum_{a\in S}a, S\subseteq A,</math> are pairwise distinct, where the empty sum is understood to be <math>0</math>.

Define <math>f(n)</math> to be the largest integer <math>k</math> for which there exists a subset-sum-distinct set <math>A\subseteq [n]</math> with <math>|A|=k</math>.

Prove the following two upper bounds.

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\log_2\log_2 n+c.</math>

* Prove that there is an absolute constant <math> c </math> with the following property: <math>f(n)\leq \log_2 n+\frac12\log_2\log_2 n+c.</math>

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

2026-04-07T08:10:32Z

652024330006: /* 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 ==
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 3 ==
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 4 ==

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 2 might be useful.)

== Problem 5 ==

There are <math>n</math> positions labeled <math>1,2,\dots,n</math>. For each position <math>i</math>, you may either leave it empty or fill it with a positive integer not exceeding <math>i</math>. Count the number of ways to fill exactly <math>k</math> positions such that all chosen integers are distinct. Prove your answer by establishing a bijection.

组合数学 (Spring 2026)

2026-03-25T06:10:05Z

652024330006: /* 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 逸B-313
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = Tuesday, 2-3pm 计算机系 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 2026. Students who take this class should check this page periodically for content updates and new announcements.

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

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** 丁天行([mailto:652024330006@smail.nju.edu.cn 652024330006@smail.nju.edu.cn])
** 周灿
** 方子伊
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-313.
* '''Office hour''': TBA
:* '''QQ群''': 1090691552 (加入时需报姓名、专业、学号)

= 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 2026)/Problem Set 1|Problem Set 1]]

= Lecture Notes =
# [[组合数学 (Spring 2026)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2026/BasicEnumeration.pdf slides])
# [[组合数学 (Spring 2026)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2026/GeneratingFunction.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 2026)

2026-03-25T06:09:29Z

652024330006: /* 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 逸B-313
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = Tuesday, 2-3pm 计算机系 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 2026. Students who take this class should check this page periodically for content updates and new announcements.

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

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** 丁天行([mailto:652024330006@smail.nju.edu.cn 652024330006@smail.nju.edu.cn])
** 周灿
** 方子伊
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-313.
* '''Office hour''': TBA
:* '''QQ群''': 1090691552 (加入时需报姓名、专业、学号)

= 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 2026)/Problem Set 1|Problem Set 1]]

= Lecture Notes =
# [[组合数学 (Spring 2026)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2026/BasicEnumeration.pdf slides])
# [[组合数学 (Spring 2026)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2026/GeneratingFunction.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 2026)

2026-03-24T13:51:19Z

652024330006:

{{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 逸B-313
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = Tuesday, 2-3pm 计算机系 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 2026. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* TBA

= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
:*'''office''': 计算机系 804
* '''Teaching assistant''':
** 丁天行([mailto:652024330006@smail.nju.edu.cn 652024330006@smail.nju.edu.cn])
** 周灿
** 方子伊
* '''Class meeting''': Wednesday, 2pm-4pm, 逸A-313.
* '''Office hour''': TBA
:* '''QQ群''': 1090691552 (加入时需报姓名、专业、学号)

= 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 2026)/Problem Set 1|Problem Set 1]]

= Lecture Notes =
# [[组合数学 (Spring 2026)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2026/BasicEnumeration.pdf slides])
# [[组合数学 (Spring 2026)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2026/GeneratingFunction.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 2026)

2026-03-24T13:49:01Z

652024330006: /* 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 逸B-313
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = Tuesday, 2-3pm 计算机系 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 2026. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* TBA

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

= 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 2026)/Problem Set 1|Problem Set 1]]

= Lecture Notes =
# [[组合数学 (Spring 2026)/Basic enumeration|Basic enumeration | 基本计数]] ([http://tcs.nju.edu.cn/slides/comb2026/BasicEnumeration.pdf slides])
# [[组合数学 (Spring 2026)/Generating functions|Generating functions | 生成函数]] ([http://tcs.nju.edu.cn/slides/comb2026/GeneratingFunction.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 2026)/Problem Set 1

2026-03-24T13:31:22Z

652024330006: Created page with "== 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..."

== 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 ==
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 3 ==
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 4 ==

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 2 might be useful.)

== Problem 5 ==

There are <math>n</math> positions labeled <math>1,2,\dots,n</math>. For each position <math>i</math>, you may either leave it empty or fill it with an integer not exceeding <math>i</math>. Count the number of ways to fill exactly <math>k</math> positions such that all chosen integers are distinct. Prove your answer by establishing a bijection.