组合数学 第3章
- 格式：pptx
- 大小：184.43 KB
- 文档页数：26
下载文档原格式
合集下载
组合数学_第3章3.2
第三章鸽巢原理
3.1 鸽巢原理的简单形式
3.2 鸽巢原理的加强形式 3.3 Ramsey定理
回顾:鸽巢原理的简单形式
定理3.1.1 如果把n＋1个物体放进 n个盒子， 那么至少有一个盒子包含两个或者更多的物体。
鸽巢原理的应用——数论
1. 如果从{1, 2, …, 2n}中任意选择n+1个不同的整数，那么一 定存在两个整数，它们之间差为1。
(2) 至少需要 677/������������ = ������������个教室。
例: 如果有5个可能的成绩A,B,C,D,E,F，那么 在一个班里最少有多个学生才能保证至少6个 学生得到相同的分数？
解: 由鸽巢原理的加强形式知，若有N个学生，则一 定有一个成绩，使得, 得到该成绩的学生个数至少为 N/������ 。 由题意知使得 N/������ =6的最小整数为N=26。 如果学生人数为25，则每个成绩的人数可能出现都为 5的情况，不满足题意。 因此最少有26个学生才能保证至少6个学生得到相同 的分数
=20000
例. 设A= a1a2···a20 是 10个0和10个1 组成的20位２进 制数。B=b1b2···b20 是 任意的 20位 2 进制数。令
设m和n都是正整数。如果m个物体放入n个盒 子，则至少有一个盒子包含至少 m/n 个物体。 加强形式的特殊形式： q1=q2=…=qn= m/n
例: (1) 在100个人当中至少有多少人生在同一 个月？
(2) 一个大学一周有38个时间段排课，一共677 门不同的课，至少需要多少个教室？
解: (1) 在100个人当中至少有 100/������������ =9个人 生在同一个月。
例 (中国剩余定理) 令 m, n是互素的正整数，a和b分别是 小于m和n的非负整数。那么，存在正整数x，使得x除以
3.1 鸽巢原理的简单形式
3.2 鸽巢原理的加强形式 3.3 Ramsey定理
回顾:鸽巢原理的简单形式
定理3.1.1 如果把n＋1个物体放进 n个盒子， 那么至少有一个盒子包含两个或者更多的物体。
鸽巢原理的应用——数论
1. 如果从{1, 2, …, 2n}中任意选择n+1个不同的整数，那么一 定存在两个整数，它们之间差为1。
(2) 至少需要 677/������������ = ������������个教室。
例: 如果有5个可能的成绩A,B,C,D,E,F，那么 在一个班里最少有多个学生才能保证至少6个 学生得到相同的分数？
解: 由鸽巢原理的加强形式知，若有N个学生，则一 定有一个成绩，使得, 得到该成绩的学生个数至少为 N/������ 。 由题意知使得 N/������ =6的最小整数为N=26。 如果学生人数为25，则每个成绩的人数可能出现都为 5的情况，不满足题意。 因此最少有26个学生才能保证至少6个学生得到相同 的分数
=20000
例. 设A= a1a2···a20 是 10个0和10个1 组成的20位２进 制数。B=b1b2···b20 是 任意的 20位 2 进制数。令
设m和n都是正整数。如果m个物体放入n个盒 子，则至少有一个盒子包含至少 m/n 个物体。 加强形式的特殊形式： q1=q2=…=qn= m/n
例: (1) 在100个人当中至少有多少人生在同一 个月？
(2) 一个大学一周有38个时间段排课，一共677 门不同的课，至少需要多少个教室？
解: (1) 在100个人当中至少有 100/������������ =9个人 生在同一个月。
例 (中国剩余定理) 令 m, n是互素的正整数，a和b分别是 小于m和n的非负整数。那么，存在正整数x，使得x除以
3.1.3 组合和组合数( 组合和组合数的性质)(课件)高二数学(人教B版2019选择性必修第二册)
的选择方式？
对于（1），可分为两步：第一步，完成（2）中的事情，即选择两所学校；
第二步，讲选出的学校进行全排列（有22 种方法）.因为（1）的答案为23 ，
所以如果设问题（2）的答案是x，那么就能得到
23 =x22
从而得到 =
23
.
22
二 组合数
组合数的定义
从n个不同对象中取出m(m≤n)个对象的所有组合的个数，称为从n个不同对象中取
这个问题可以用我们本节所学的组合知识来解。
03 新知探索
一、组合
【尝试与发现】下面这两个问题的答案一样吗？
（1）小张要在三所大学中选择2所，分别作为自己的第一志愿和第二志愿，校长
共有多少种不同的选择方式？
（2）小张要在三所大学中选择2所，作为自己的努力的目标，小张有多少种不同
的选择方式？
选择合适的符号，分别表示出上述两题中所有的选择方式，并总结两者之间
02 新知导入
02 新知导入
【情境与问题】
高考不分文理科后，思想整理、历史、地理、物理、化学、生物这6科是选考的，
考生可以从中任选3科作为自己的高考科目，那么选考的组合方式一共有多少种
可能得情况呢？
如果用{思想政治、地理、历史}表示其中一种选考组合，你能用类似的方法表示
出所有的组合方式吗？你有更简单的表示方法吗？
【答案】D
D．5或7
四 课堂练习
【练习3】某校拟从2名教师和4名学生共6名党史知识学习优秀者中随机选取3名
，组成代表队，参加市党史知识竞赛，则要求代表队中既有教师又有学生的选法
共有
种．
【答案】16
四 课堂练习
【练习4】
【解析】
四 课堂练习
对于（1），可分为两步：第一步，完成（2）中的事情，即选择两所学校；
第二步，讲选出的学校进行全排列（有22 种方法）.因为（1）的答案为23 ，
所以如果设问题（2）的答案是x，那么就能得到
23 =x22
从而得到 =
23
.
22
二 组合数
组合数的定义
从n个不同对象中取出m(m≤n)个对象的所有组合的个数，称为从n个不同对象中取
这个问题可以用我们本节所学的组合知识来解。
03 新知探索
一、组合
【尝试与发现】下面这两个问题的答案一样吗？
（1）小张要在三所大学中选择2所，分别作为自己的第一志愿和第二志愿，校长
共有多少种不同的选择方式？
（2）小张要在三所大学中选择2所，作为自己的努力的目标，小张有多少种不同
的选择方式？
选择合适的符号，分别表示出上述两题中所有的选择方式，并总结两者之间
02 新知导入
02 新知导入
【情境与问题】
高考不分文理科后，思想整理、历史、地理、物理、化学、生物这6科是选考的，
考生可以从中任选3科作为自己的高考科目，那么选考的组合方式一共有多少种
可能得情况呢？
如果用{思想政治、地理、历史}表示其中一种选考组合，你能用类似的方法表示
出所有的组合方式吗？你有更简单的表示方法吗？
【答案】D
D．5或7
四 课堂练习
【练习3】某校拟从2名教师和4名学生共6名党史知识学习优秀者中随机选取3名
，组成代表队，参加市党史知识竞赛，则要求代表队中既有教师又有学生的选法
共有
种．
【答案】16
四 课堂练习
【练习4】
【解析】
四 课堂练习
组合数学讲义及答案 3章 递推关系
n k k k r ，求{an}所满足的递推关 k 0
n n n n - 1 n - 2 2 r r ＋…＋ 2 r 2 n 为偶数： a n ＝ n 0 1 2 2
an 3an1 2an2 2a1 1
（二） 分 类 （1） 按常量部分： ① 齐 次 递 推 关 系 ： 指 常 量 ＝ 0 ， 如
Fn Fn1 Fn 2 ；
② 非齐次递推关系，即常量≠0，如 hn 2hn 1 1 。 （2） 按 a i 的运算关系：
结论：对于常系数线性递推关系的定解问题，其解必是唯
一的。 求解方法：首推特征根法。 思想：来源于解常系数线性微分方程，因为两者在结构上 很类似，所以其解的结构和求解的方法也类似。
8／75
《组合数学》
第三章 递推关系
§ 3.2.1
解的性质
1 2 【性质1】 设数列 bn 和 bn
2 2 2 2 2 an an 1 an2 a0 n 0 an 3an1 2an2 2a1 1 0
定义 3.1.1＇ （显式） 对数列 a i i 0，把 an 与其之前 若干项联系起来的等式对所有 n≥k 均成立（k 为某个给定的 自然数） ，称该等式为 a i 的递推关系，记为 a n F a n1 , a n 2 ,, a n k (3.1.1)＇ 例
分两种情况：当 n 为偶数时，令 n＝2m，则
n 1 n 2 ＝ ＝m－1 2 2 m 2m k k an＝ k r k 0 m 1 2m 2m k k m m ＝ ＋ 0 k r ＋ m r k 1 2m m 1 2m k 1 k ＝ 0 ＋ r k k 1 m 1 2m k 1 k m m ＋ k 1 r ＋ m r k 1
chap3排列组合
n1 ! n 2 ! n k !
例
例. 求MISSISSIPPI中字母的排列数. 例. S = {3a, 2b, 4c }, 求S的8排列的个数. 例. 一面包房生产8种炸面包圈, 若一打面包一盒, 求不同盒数. 例. 不定方程 x1+ x2+ x3+ x4 = 20, 其中 x13, x21, x30, x45, 求其整数解的数目.
乘法原理应用
例: 确定3452117138的正整数因子的个数. 解: 其正整数因子的形式为 3i 5j 11m 13n, 其中 0 i 4, 0 j 2, 0 m 7, 0 n 8, 根据乘法原理正整数因子的个数是 5389=1080.
例
例. 求1000~9999之间具有不同数字的奇数的个数 解:1.个位有 |{1,3,5,7,9}| = 5 种选择 2.千位有 |{1,…,9}| -1 = 8 种选择 3.百位有 |{0,1,…,9}| -2 = 8 种选择 4.十位有 |{0,1,…,9}| -3 = 7 种选择 总个数 = 5887= 2240. 换次序: 1. 百位有 |{0,1,…,9}| = 10 种选择 2. 个位有 |{1,3,5,7,9}| - ? 种选择
排列数与组合数
用P(n,r)表示n元素集合的r-排列的个数 用C(n,r)表示n元素集合的r-组合的个数 定理: 0 r n, P(n,r) = n!/(n-r)! 定理: 0 r n, C(n,r) = n!/(n-r)!/r! 通常记C(n,r)为 n n!
r ( n r )! r !
本章小结
集合: 排列组合 容易 多重集: 无个数限制的排列组合 容易 有限多重集的全排列 容易 有限多重集的部分排列组合 困难
例
例. 求MISSISSIPPI中字母的排列数. 例. S = {3a, 2b, 4c }, 求S的8排列的个数. 例. 一面包房生产8种炸面包圈, 若一打面包一盒, 求不同盒数. 例. 不定方程 x1+ x2+ x3+ x4 = 20, 其中 x13, x21, x30, x45, 求其整数解的数目.
乘法原理应用
例: 确定3452117138的正整数因子的个数. 解: 其正整数因子的形式为 3i 5j 11m 13n, 其中 0 i 4, 0 j 2, 0 m 7, 0 n 8, 根据乘法原理正整数因子的个数是 5389=1080.
例
例. 求1000~9999之间具有不同数字的奇数的个数 解:1.个位有 |{1,3,5,7,9}| = 5 种选择 2.千位有 |{1,…,9}| -1 = 8 种选择 3.百位有 |{0,1,…,9}| -2 = 8 种选择 4.十位有 |{0,1,…,9}| -3 = 7 种选择 总个数 = 5887= 2240. 换次序: 1. 百位有 |{0,1,…,9}| = 10 种选择 2. 个位有 |{1,3,5,7,9}| - ? 种选择
排列数与组合数
用P(n,r)表示n元素集合的r-排列的个数 用C(n,r)表示n元素集合的r-组合的个数 定理: 0 r n, P(n,r) = n!/(n-r)! 定理: 0 r n, C(n,r) = n!/(n-r)!/r! 通常记C(n,r)为 n n!
r ( n r )! r !
本章小结
集合: 排列组合 容易 多重集: 无个数限制的排列组合 容易 有限多重集的全排列 容易 有限多重集的部分排列组合 困难
组合数学与图论
● 02
第2章 图论基础
什么是图论
图论是研究图结构的 数学分支，用于描述 对象之间的关系。图 由节点和边组成，节 点表示对象，边表示 对象之间的关系。
基本概念
无向图
边没有方向的图
权重图
边带有权重的图
度
节点相连的边数 称为节点的度
91%
有向图
边有方向的图
图的表示方法
01 邻接矩阵
02 邻接表
判断图中的节点是否都是连通的
02 组合数学方法
连通性定理和算法可以用于判断和求解
03
总结
组合数学和图论相互结合，能够解决图的同构、 着色、匹配和连通性等各种问题，通过组合数学 方法的运用，可以更好地探索图论中的难题。
● 04
第四章 组合数学与图论在计 算机科学中的应用
图数据库与图搜索
图数据库是一种专门用于存储和查询图结构数据 的数据库系统。在计算机科学中，图搜索算法如 Dijkstra算法、A*算法等被广泛应用于图数据库 的查询和分析，帮助用户快速准确地获取所需信 息。
03
● 05
第五章 组合数学与图论在统 计学中的应用
基于图的统计分 析
利用组合数学和图论 的方法进行统计学分 析，如图的频繁模式 挖掘、图数据的聚类 分析等。这些方法能 够帮助研究人员从大 量数据中提取出有用 的信息并进行深入分 析。
网络数据采样与推断
节点采样
通过在网络中随 机选择节点来获
取样本数据
使得相邻节点颜 色不同
图的匹配问题
图的匹配问题是指在 图中找到一些相互不 相邻的边，使得边的 数量最大化。组合数 学的匹配定理和匹配 算法可以用于解决图 的匹配问题。
图的连通性问题
组合数学第三章习题解答
j 0
m
i 0 nm
(c )
C (m l 1, m 1) C (m l , m) C (m l , m 1) C (m l , m 2) ...
(1)l C (m l , m l )
(a)
C (n m, n k ) C (n m, k m)
设这66个元素为a1<a2<a3<...<a66
构造b1=a2-a1, b2=a3-a1,…, b65=a66-a1, 令B={b1,b2,…,b65} 这65个元素属于1到326，如果这65个元素有任何一个属于P1， 则定理得证。 否则： B p2 p3 p4 p5 (2)因为。 65 1 1 17 4 因此至少有一个集合含至少B中17个元素，设这个集合为p2。 设这6个元素为： bi1 bi2 ... bi1 7
证明(a)
(a) A B与A B关于B互为余集， 因此 A B B A B
(b) A BC C AC B C A B C A B C与(C B) (C A)互为余集. A B C C (C B) (C A) C C A C B A B C
否则： e1 , e2 p5 构造： e2 e1 同样可证明e2-e1既可表示成p1中数之差，也可表示成p2p3p4中 数之差。 e2-e1是1到326中的数，设f=d2-d1
e p1 p2 p3 p4
因此：1到326的326个整数任意分成5部分，其中必有一部分 其中有一个数是另两个数之差，设ai=aj-ah,那么反过来： aj=ai+ah
3.12,一年级有100名学生参加中文、英文和数学的考试，其中92 人通过中文考试，75人通过英语考试，65人通过数学考试；其中 65人通过中英文考试，54人通过中文和数学考试，45人通过英语 和数学考试，求通过三门学科考试的学生数？
m
i 0 nm
(c )
C (m l 1, m 1) C (m l , m) C (m l , m 1) C (m l , m 2) ...
(1)l C (m l , m l )
(a)
C (n m, n k ) C (n m, k m)
设这66个元素为a1<a2<a3<...<a66
构造b1=a2-a1, b2=a3-a1,…, b65=a66-a1, 令B={b1,b2,…,b65} 这65个元素属于1到326，如果这65个元素有任何一个属于P1， 则定理得证。 否则： B p2 p3 p4 p5 (2)因为。 65 1 1 17 4 因此至少有一个集合含至少B中17个元素，设这个集合为p2。 设这6个元素为： bi1 bi2 ... bi1 7
证明(a)
(a) A B与A B关于B互为余集， 因此 A B B A B
(b) A BC C AC B C A B C A B C与(C B) (C A)互为余集. A B C C (C B) (C A) C C A C B A B C
否则： e1 , e2 p5 构造： e2 e1 同样可证明e2-e1既可表示成p1中数之差，也可表示成p2p3p4中 数之差。 e2-e1是1到326中的数，设f=d2-d1
e p1 p2 p3 p4
因此：1到326的326个整数任意分成5部分，其中必有一部分 其中有一个数是另两个数之差，设ai=aj-ah,那么反过来： aj=ai+ah
3.12,一年级有100名学生参加中文、英文和数学的考试，其中92 人通过中文考试，75人通过英语考试，65人通过数学考试；其中 65人通过中英文考试，54人通过中文和数学考试，45人通过英语 和数学考试，求通过三门学科考试的学生数？
组合数学第三讲-文档资料
6
6
5
4
+）
。。。
记
1 5 1 5 ， ，则有： 2 2
1 2 2 2 ( ) x ( ) x 5
解：先找出算法，进一步对算法复杂度进行估计。 先考虑 n 2 的情况。 先将上面的圆盘移到 C 柱上，在将下面的盘移到 B 柱 上，在将 C 柱的移到 B 柱上，共作 3 次转移，问题解决。 考虑 n 3 的情况。 第一步用 3 次转移将上面的两个移到 C 柱上，在将第三 个盘移到 B 柱上，再用 3 次将 C 柱上的两个圆盘移到 B 柱上， 问题解决。
, cn ,
为 { ci } 。
例 2.3
(1 a1 x)(1 a2 x) 1 (a1 a2
令 a1 a2
(1 an x) an ) x (a1a2 a1a3 an1an ) x 2 a1a2 an x n
an 1，即可得：
C(n, n) xn
, C (n, n) 的母函数。
(1 x)n C(n,0) C(n,1) x C(n, 2) x2
n 函数 (1 x) 称为序列 C (n,0), C (n,1), C (n, 2),
例2.4 对于河内塔问题利用母函数求递推关系的解
解： H (n) 2H (n 1) 1 ， H (1) 1 ，记 H (n) H n ，补充定义 H 0 0 。 令序列 {H n } 的母函数为：
x A B 1 1 (1 x)(1 2 x) 1 2 x 1 x 1 2 x 1 x
得：
) (1 x x 2 )
x (1 2 x 22 x 2 (1 x)(1 2 x)
卢开澄组合数学--第三章习题解答
9. 题目 由推导过程知 解：
ln( G ( x )) 1 1 2
2
x 1 x 1 3
2
(1
1 2
2
2
1 3
2
)
x 1 x
6
2
ln( G ( x ))
6
ln( G ( x )) ln pn n ln ln pn x 1 x x 1 x
an an 1 1 C ,
2 n
a1 2, a0 1
n n 设 an A0 A1n A2 A3 2 3
解得
A0 A 1 A2 A3
1 1 1 1
n n an 1 n 2 3
(1 x x x x x )
2 3 4 5
其中 x 项系数为所求
8
11. 题目 解： 用归纳法可证明： 1）当k=1时命题成立 2）设当k=N时命题成立 即N可唯一表示成不同且不相邻的F 数之和。 则当k=N+1时，明显可以分成N的序列 再加上1（ F2），但这可能会不能满足 “不同且不相邻”的条件。 下面予以讨论
n 1
[(4 2 2 1) ( 4
n n
n 1
22
n 1
1)]
2 )
n
6. 题目 解：
参见第四题解答前半部分。
7. 题目 解：题设中序列的母函数为：
G ( x ) C ( n, n) C ( n 1, n) x C ( n k , n) x
13. 题目 解： 设符合条件的n位二进制数的个数为hn 这些数中一共有a n个0 当n位二进制数最高位为1时,符合条件 的n位二进制数的个数为 hn 1
3、组合数学第三章排列组合(1)
一次考试，问有多少种排法。
P（5，3）
（2）同（1），若不限制每天考试的次数，问有多 少种排法？
53
例3.8 排列26个字母，使得在a 和 b之间正好有7个 字母，问有多少种排法？
例3 用26个字母排列，是元音 a,e,i,o,u 组不相继 出现，有多少种排法？
（1）排列所有辅音：P(21,21)=21！ （2）在辅音前后的22个空档中排元音:
n2 +... + nk .
2若r=n,则N= n! ; n1 !n2 !...nk !
3若r < n且对一切i,i =1, 2,..., k,有ni ? r,则N=kr ; 4若r < n,且存在着某个ni < r,则对N没有一般的求解公式。
§3.5 多重集的组合
多重集S中r个元素进行无序选择，构成一个多重 集的r-组合。 篮子里有2个苹果，1个桔子，3个香蕉，篮子里 的水果构成“多重集”。
解1 (1)任意坐： n=9! (2)不相邻：A先就坐，B不相邻：7 其余8人排序：8！ m=7*8！ (3) P=m/n=7*8!/9!=7/9
例6 10个人为圆桌任意就坐，求指定的两个人 A与B不相邻的概率。
解2 (1)任意坐： n=9! (2)A,B相邻：A先就坐，B左右相邻：2 其余8人排序：8！ k=2*8！ (3)不相邻：m=9!-2*8! (4) 两人不相邻的概率 P=m/n=（9!-2*8!)/9!=1-2/9=7/9
证明
(1) 从{ 1,2,…,n }中选出2-组合有
C
2 n
(2) 另一种选法：
最大数为k的2-组合共有k-1个，k=1,2,…,n
有加法原理，共有 0+1+2+…+(n-1) 个2-组合
P（5，3）
（2）同（1），若不限制每天考试的次数，问有多 少种排法？
53
例3.8 排列26个字母，使得在a 和 b之间正好有7个 字母，问有多少种排法？
例3 用26个字母排列，是元音 a,e,i,o,u 组不相继 出现，有多少种排法？
（1）排列所有辅音：P(21,21)=21！ （2）在辅音前后的22个空档中排元音:
n2 +... + nk .
2若r=n,则N= n! ; n1 !n2 !...nk !
3若r < n且对一切i,i =1, 2,..., k,有ni ? r,则N=kr ; 4若r < n,且存在着某个ni < r,则对N没有一般的求解公式。
§3.5 多重集的组合
多重集S中r个元素进行无序选择，构成一个多重 集的r-组合。 篮子里有2个苹果，1个桔子，3个香蕉，篮子里 的水果构成“多重集”。
解1 (1)任意坐： n=9! (2)不相邻：A先就坐，B不相邻：7 其余8人排序：8！ m=7*8！ (3) P=m/n=7*8!/9!=7/9
例6 10个人为圆桌任意就坐，求指定的两个人 A与B不相邻的概率。
解2 (1)任意坐： n=9! (2)A,B相邻：A先就坐，B左右相邻：2 其余8人排序：8！ k=2*8！ (3)不相邻：m=9!-2*8! (4) 两人不相邻的概率 P=m/n=（9!-2*8!)/9!=1-2/9=7/9
证明
(1) 从{ 1,2,…,n }中选出2-组合有
C
2 n
(2) 另一种选法：
最大数为k的2-组合共有k-1个，k=1,2,…,n
有加法原理，共有 0+1+2+…+(n-1) 个2-组合
组合数学第四版卢开澄标准答案-第三章资料
第三章3.12.一年级有100名学生参加中文，英语和数学的考试，其中92人通过中文考试，75人通过英语考试，65人通过数学考试；其中65人通过中，英文考试，54人通过中文和数学考试，45人通过英语和数学考试，试求通过3门学科考试的学生数。
[解].令：A 1={通过中文考试的学生}A 2={通过英语考试的学生}A 3={通过数学考试的学生}于是 |Z| =100，|A 1|=92，|A 2|=75，|A 3|=65|A 1∩A 2|=65，|A 1∩A 3|=54，|A 2∩A 3|=45此题没有给出：有多少人通过三门中至少一门；有多少人一门都没通过。
但是由 max{ |A 1|,|A 2|,|A 3| }=max{92,75,65}=92故可以认为：至少有92人通过三门中至少一门考试，即100≥|A 1∪A 2∪A 3|≥92至多有8人没通过一门考试，即0≤|1A ∩2A ∩3A | ≤8于是，根据容斥原理，有|A 1∪A 2∪A 3|=(|A 1|+|A 2|+|A 3|)-(|A 1∩A 2|+|A 1∩A 3|+|A 2∩A 3|)+|A 1∩A 2∩A 3|即 |A 1∩A 2∩A 3|=|A 1∪A 2∪A 3|-(|A 1|+|A 2|+|A 3|)+(|A 1∩A 2|+|A 1∩A 3|+|A 2∩A 3|)=|A 1∪A 2∪A 3|-(92+75+65)+(65+54+45)=|A 1∪A 2∪A 3|-232+164=|A 1∪A 2∪A 3|-68从而由 92-68≤|A 1∪A 2∪A 3|-68≤100-68即 24≤|A 1∪A 2∪A 3|-68≤32可得 24≤|A 1∩A 2∩A 3| ≤32故此，通过3门学科考试的学生数在24到32人之间。
也可用容斥原理，即|1A ∩2A ∩3A |=|Z|-(|A 1|+|A 2|+|A 3|)+(|A 1∩A 2|+|A 1∩A 3|+|A 2∩A 3|)-|A 1∩A 2∩A 3|=100-(92+75+65)+(65+54+45)-|A 1∩A 2∩A 3|=100-232+164-|A 1∩A 2∩A 3|=32－|A 1∩A 2∩A 3|从而有 |A 1∩A 2∩A 3|=32-|1A ∩2A ∩3A |由已知 0≤|1A ∩2A ∩3A |≤8，可得24≤|A 1∩A 2∩A 3|≤32故此，通过3门学科考试的学生数在24到32之间。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
射雕英雄传中的问题
黄蓉给瑛姑出题: 今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何.
答案: 三人同行七十稀, 五树梅花廿一支, 七子团圆正半月, 除百零五便得知.
同余方程组 x a1 mod 3, x a2 mod 5, x a3 mod 7
的解是 x = 70a1 + 21a2 + 15a3 mod 105
x a mod m, x b mod n ------------------(*) 有唯一解 x a·t·n + b·s·m mod mn. -------------(**) • 例: 同余方程组 x a1 mod 3-----(1),
x a2 mod 5-----(2), x a3 mod 7-----(3) 由2·3+(-1)·5=1, 得(1)(2)的解是
特点: 对所有具体互相认识情况(215)都成立. 该Ramsey问题等价于: 六个顶点的完全图的边, 用红,蓝二色任意着色, 则至少存在一红色边三角形, 或一蓝色边三角形.
完全图K6, C(6,2)条边图示证 Nhomakorabea(P47)
从6人任取一人A.
G
A
H
和A互相认识 的人的集合G
和A互不认识 的人的集合H
5个人的反例(P47)
x a1·(-1)·5 + a2·2·3 mod 15 -5 a1 + 6 a2 mod 15---(4) 由1·15+(-2)·7=1, 得(4)(3)的解是
x (-5 a1 + 6 a2)·(-2)·7 + a3·1·15 mod 105 70a1 + 21a2 + 15a3 mod 105
组合数学
第三章 鸽巢原理
主要内容： 1. 鸽巢原理及其应用 2. 中国剩余定理 3. 加强形式的鸽巢原理 4. Ramsey定理
鸽巢原理(P42)
定理: 若有n个鸽巢, n+1只鸽子, 则至少有一个鸽巢里至少有两只鸽子.
注意这里的任意性. 例1. 一年365天, 今有366个人,
则其中至少有两个人生日相同. 例2. 抽屉里有10双手套, 从中取11只出来,
其中至少有两只是完整配对的. 关键: 选鸽巢和鸽子
应用举例(P43)
例. 在边长为1的正方形内任取5点,则 其中至少有2点的距离不超过 2 / 2
Halloween treats 例. 设a1,a2,…,am是正整数序列, 则至少存在
整数k和l, 0k<l m, 使得m|(ak+1+ak+2+…+ al). 鸽子: rk=a1+a2+…+ak mod m, k=1,2,…,m, 鸽巢: {0,1,…,m-1} (a) 若有rh=0, 即m|(a1+a2+…+ ah); (b) 否则, r1,r2,…,rm取值为{1,2,…,m-1}, 所以
mk1 mk2 mkn1 若ak1 ak2则必有mk1 > mk2,于是:
ak1 ak2 akn1 ak 5 4 6 3 4 2 3 1 9 2
mk 3 3 2 3 2 3 2 2 1 1
Ramsey问题(P47)
命题: 6人中或者至少存在3人互相认识, 或者至少存在3人互相不认识.
即 r(a,b) <
Ramsey定理的证明(P48)
r(a,b)=r(b,a), r(a,2)=r(2,a)=a 性质: 当a,b2时, r(a,b)r(a-1,b)+r(a,b-1).
韩信点兵(-2), 孙子算经(4), 数书九章(秦九韶13)
加强形式(P45)
条 鸽巢n个, 鸽子m1+m2+…+mn-n+1只, 件 其中 m1,m2,…,mn, n都是正整数,
结 论
鸽巢1鸽子数 m1,
或,鸽巢2鸽子数 ……
m2,
或,鸽巢n鸽子数 mn, 至少有一个成立.
证明:否则, 总鸽子数(m1-1)+(m2-1)+…+(mn-1) 与总鸽子数为m1+m2+…+mn-n+1矛盾.
Erdös-Szekeres定理(P46)
定理: 在由n2+1个实数构成的序列中, 必然 含有长为n+1的单调(增或减)子序列.
证明:设序列为 a1, a2, … , an2+1, 令mk是从ak开始的最长单调增子序列的长度. 若没有长于n+1的单增序列,则m1,…,mn2+1[1,n] 由加强鸽巢原理, 存在k1<k2<…<kn+1使得
K6 K3, K3, (K5 K3, K3)
Ramsey数与Ramsey定理(P48)
Ramsey数r(a,b)定义为: r(a,b) = min{ n | n个人中必有 a个互相认识,
或者b个互相不认识} = min{ n | KnKa, Kb } 例如: r(3,3)=6, r(3,4)=9, r(4,4)=18. Ramsey定理: a,b2, p KpKa, Kb.
a, m+a, 2m+a, …, (n-1)m+a. 这n个数模n的余数两两不同. (n鸽n巢,没有同巢) 由鸽巢原理, (1)(2)在[0,mn)内有唯一解.
中国剩余定理(构造性证明)
• Thm m,n>0 s,t,使得 s·m + t·n = gcd(m,n). • Thm 设m,n互素, 0am-1, 0bn-1,则方程组
ai+21=aj .
中国剩余定理(存在性证明)
• 令m,n互素, 0 a m-1, 0 b n-1, 则方程组 x a mod m----(1) x b mod n-----(2)
在[0,mn)内有唯一解. • 例. x 2 mod 3, x 1 mod 5 解: x 11 mod 15 • 证明: (1)在[0,mn)内只有n个解(模m余a)
存在k<l使得rk=rl , 即m|(ak+1+ak+2+…+ al).
应用:国际象棋大师(P43)
一位国际象棋大师有11周的时间备战比赛, 他决定每天至少下1盘棋,但每周不超过12盘. 则存在连续若干天,他恰好下了21盘棋. 证明: 令ai为到第i天下的总盘数, (ai+21=aj?) 1 a1 < a2 < …< a77 1112=132, 22 a1+21 < a2+21 < …< a77+21 132+21=153 总共有153种取值[1,153], 却有154个数(77+77) 所以存在i<j使得