K
t p
→
K
t q1
,,
K
t qk
即当用 k 种颜色 c1,, ck 为一个 p 元集 A的所有 t 元子集任
意染色时，或者总有一个 A的 q1 元子集的所有 t 元子集都
染成c1 色，，或者总有一个 A的 qk 元子集的所有 t 元子
集都染成 ck 色。
使得
K
t p
→
K
t q1
,
,
Kt qk
若要放数的位置已有数，则将数放在原数下方。
⎡8 1 6⎤ ⎢⎢3 5 7⎥⎥ ⎢⎣4 9 2⎥⎦
优化问题
A1,, Am 地分别生产某种商品 a1,, am 吨， B1,, Bn 地分别销售该种商品 b1,,bn 吨，
m
n
∑ ∑ ai = bj （供需平衡）。从 Ai 到 Bj 的
K2
K3
K4
K5
设正整数 p, m, n ≥ 2，引进记号 Kp → Km , Kn ： 若用红、蓝两种颜色为 Kp 的边任意染色，则总存 在红 Km 或蓝 Kn 。 Ramsey 定理 若正整数 m, n ≥ 2，则存在正整数 p 使得 Kp → Km , Kn。并称使 Kp → Km , Kn 成立的 最小正整数 p 为 Ramsey数 r(m, n)。
棋盘完美覆盖问题
一个多米诺骨牌可覆盖同一行或同一列两相邻方格。 若用若干多米诺骨牌覆盖棋盘所有方格，并且多米 诺骨牌不重叠，则称该覆盖为完美覆盖。 m × n 棋盘有完美覆盖 iff m 和 n 中至少有一个是 偶数。 当 m 是偶数时，每块多米诺骨牌竖放。 当 m 是奇数且 n 是偶数时，每块多米诺骨牌横放。 当 m 和 n 都是奇数时，棋盘的方格数 mn 是奇数。
Kp → Kn1 , …, Knk 使得 Kp → Kn1 , …, Knk 成立的最小正整数 p 称为 Ramsey 数 r(n1,…, nk)。
无向图中的边是顶点集的 2 元子集，可以将 Ramsey 定理
推广到为
t
元子集染色。用
K
t n
表示一个
n
元集的所有
t
元
子集的集合。
Ramsey ఆཧ 设 t 是正整数，q1,, qk ≥ t，则存在正整数 p 使得
幻方
在由 1, 2, …, n2 组成的 n × n 方阵中，若每行之 和、每列之和、每条对角线之和都相等，则称 该方阵为 n 阶幻方。对于 n ≠ 2，存在 n 阶幻 方。例如，左下方方阵是 3 阶幻方。若右下方 方阵是 2 阶幻方，则 u + v = u + y，所以 v = y， 矛盾。无 2 阶幻方。
a, m + a, …, (n - 1)m + a 被 n 除余数各不相同，其中有 mk + a 被 n 除余 b，取 x = mk + a 。
2.2 鸽巢原理：加强形式
定理2.2.1 设 q1,…, qn 是正整数。将多于 q1 + … + qn - n
个物体放入 n 个盒子，或者第 1 个盒子中至少 有 q1 个物体，…，或者第 n 个盒子中至少有 qn 个物体。 证明 否则物体总数至多
r (3, 3) ≤ 6，因此，
r (3, 3) = 6。
显然，r(m, n) = r(n, m)。
r(m, 2) = m 。
若 Km 中都是红边，则有红 Km ；若 Km 中有蓝 边，则有蓝 K2 。所以 Km → Km , K2 。 若 Km-1 中都是红边，则既没有红 Km ，也没有蓝 K2 。所以 Km-1 → Km , K2 不成立。 40 ≤ r(3, 10) = r(10, 3) ≤ 43，即 K43 → K3 , K10 成立且 K39 → K3 , K10 不成立。 对于 i = 40, 41, 42，不知 Ki → K3 , K10 是否成立。
如果在集合 A 和 B 之间存在一一对应，
则|A|=|B|。
例 n 元集 S = {1, …, n} 的子集个数等于由 0 和 1 组成的长度为 n 的串的个数。
证明 可在 S 的子集的集合与由 0 和 1 组成的长
i =1
j =1
运价为每吨 cij 元。如何安排运输最经济？
mn
∑ ∑ 设从 Ai 到 Bj 的运量为 xij 吨。求 min
cij xij
i=1 j=1
n
m
∑ ∑ 约束条件
xij = ai ， xij = bj
j =1
i =1
第 2 章 鸽巢原理
本章主要讨论简单形式和加强形式的鸽巢原理 及其应用。 本章还简单讨论鸽巢原理的推广：Ramsey 定理。 2.1 鸽巢原理：简单形式 2.2 鸽巢原理：加强形式 2.3 Ramsey定理 作业
r (k, l) 表
可以将 Ramsey 定理推广到任意多种颜色的情况。
引进记号 Kp → Kn1 , …, Knk 表示：用 k 种颜色 c1,…, ck 为 Kp 的边任意染色， 或者有一个被染成 c1 色的 Kn1 ，…，或者有一个 被染成 ck 色的 Knk 。 Ramsey 定理 若 n1,…, nk ≥ 2，则有正整数 p 使 得
鸽巢原理应用
从 1, 2, …, 200 中任意选出 101 个数，必有两个数 其中一个能够整除另一个。 证明 将数表示成形式 2k × a，其中 a 是奇数。小 于 200 的奇数只有 100 个，即 1, 3, …, 199，所以 这 101 个数中必有两数表示为 2k × a 和 2j × a ，
2.1 鸽巢原理：简单形式
定理2.1.1 若将多于 n 个物体放入 n 个盒子，则 至少有一个盒子中的物体数大于 1。
设 f : A → B ，将 A 看做物体的集合， B 看做盒 子的集合，物体 a 放在盒 子 f(a) 中。 如果 | A | > | B |，则 f 不是从 A 到 B 的单射 （一对一的函数） 。
K5 → K3 , K3 不成立。 由此可知，r (3, 3) > 5。
r (3, 3) = 6
设 K6 的六个顶点分别为 v1, …, v6 。 v1 与 v2, …, v6 的连边中必有三个是同色的，不妨设 v1 与 v2, v3, v4 的连边都是红色，若三角形 v2v3v4 中某边是红色的，则有红三角形。若三角 形 v2v3v4 中边都是蓝色的，则有蓝三角形。 因此， K6 → K3 , K3 。
有多少种方法将正整数 n 表示成正整数之和，即 n 有多少个分拆。如 4 有 5 个分拆：
4，3 + 1，2 + 2，2 + 1 + 1，1 + 1 + 1 + 1
构造问题
构造 n 阶幻方的方法，其中 n 是奇数。 将 1 放在第一行中间。 自左下至右上沿对角线顺次放随后各数，将最后 一行认为是第一行上面的行，第一列认为是最后 一列右面的列。
2k × a | 2j × a 当且仅当 k ≤ j
鸽巢原理应用
设 n 是正整数，必存在由数字 0 和 7 组成的正 整数能被 n 整除。
证明 7，77，，777 是 n +1个不同正整数，它们被 n 除
n+1个
余数只有 n 种可能，所以必有两数被 n 除余数相同。设
i < j，777 和 777 被 n 除余数相同。则它们的差为
度为n +1的递增子序列，则每个 mi
≤
n，m1
,
,
m n
2
+1
中必
有 n +1个相同的。设 mk1 = = mkn+1，其中 k1 < < kn+1 。
我们证明 ak1 ,, akn+1 是递减子序列。若 aki < aki+1，则将
aki 放在从 aki+1 开始的最长递增子序列前面就得到更长的
问题。
1. 存在性问题（是否存在某种安排） 2. 计数问题（安排的个数、枚举、分类） 3. 构造问题（寻找安排的算法） 4. 优化问题（找出一定条件下的最优安排）
排课表问题
需安排甲、乙、丙、丁四位教师教英语、日语、德 语、法语四门课，每人教一门。 甲和乙能教英语、日语， 丙能教英语、德语、法语， 丁只能教德语， 是否能够排出课表？ 甲、乙、丙、丁分别教英语、日语、法语、德语。
i个
j个
777000，这是能被 n 整除的数。
j−i个 i个
中国剩余定理
设 m 和 n 是互素的正整数，即它们的最大公约 数是 1，0 ≤ a < m ，0 ≤ b < n，必存在正整数 x 使得，m 除 x 余 a，n 除 x 余 b。 证明 考虑 n 个数 a, m + a, …, (n - 1)m + a 若其中两数 im + a 和 jm + a 被 n 除余数相同， 则 n | (i - j)m ，n | (i - j)，0 < | i - j | < n，矛盾。
成绩 作业 40% 考试 60%
组合数学
第 1 章 什么是组合数学 第 2 章 鸽巢原理 第 3 章 排列与组合 第 4 章 生成排列和组合 第 5 章 二项式系数 第 6 章 容斥原理及应用 第 7 章 递推关系和生成函数 第 8 章 特殊计数序列
第1章 什么是组合数学
组合数学是研究“安排”的学科。主要研究以下四 类
减法原理 设 A 是有限集合 U 的子集， A 的补
集
A = {x ∈U : x ∉ A}
则 A 的元素个数| A| |A=| |由U以| −下| A公| 式给出：
除法原理 如果有限集 S 被分成包含同样多个元
素的 k 部分，那么部分的数目 k 由以下公式给出：