软件2011组合数学—第一章绪论

取到含有最后一枚硬币者胜。
绪论
2. 方法
3.
直觉可知，胜负受硬币数目
多少影响不大，但应与奇偶性有关。
4.
分析的一般规那么：为了深入理
解和强化直觉，往往可先考虑小的或特
殊的情形，然后再扩展你的看法以解决
一般的问题。
5.
绪论
A. 两堆的情况 (1)假设两堆大小一样，先拿者负。后者模
拟前者动作即可； (2)假设两堆大小不同，先拿者胜。他只要
当n为奇数时，有一种简单的构造方 法。
⑴1置1行中间；
⑵顺序将各数置于右上方位置。假设 当前数位于1行n列或当前数的右上角已 填入了其它数，那么下一个数填在当前 数下方；假设当前数的右上方超出了矩 阵，那么下一个数循环填在另一侧。
绪论
例：5阶幻方。
17 24 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 18 25 2 9
绪论
组合数学是一个古老而又年轻的 数学分支。
据传说，大禹在4000多年前就观 察到神龟背上的幻方…...
绪论
幻方可以 看作是一个3 阶方阵，其元 素是1到9的正 整数，每行、 每列以及两条 对角线的和都 是15。
492 357 816
绪论
北宋数学家〔约11世纪〕贾宪 著有?黄帝 九章细草?、?算法斅(xiao)古集?〔即“古算法 导引〞〕都已失传。杨辉著?详解九章算法? 〔1261年〕中曾引贾宪的“开方作法根源〞 图〔即指数为正整数的二项式展开系数表，现 称“杨辉三角形〞〕和“增乘开方法〞〔求高 次幂的正根法〕。前者比pascal三角形早600 年，后者比霍纳〔William Geoge Horner， 1786—1837〕的方法〔1819年〕早770年。

ppt精选版
27
Ramsey数
推广为一般问题：给定任意正整数a和b， 总存在一个最小整数 r(a,b)，使得r(a,b) 个人中或者有 a 个人互相认识，或者 有 b 个人互相不认识。称 r(a,b) 为 Ramsey数。
ppt精选版
28
Erdös -Szekeres 定理
Ramsey定理是由Erdös和Szekeres于1935年提 出的。它是下述定理的一个推广：
ppt精选版
13
Euler 定理
如果一个图包含一条经过每条边恰好一次的闭途 径，则称这个图为欧拉图。
对任意的非空连通图，若它是欧拉的, 当且仅当它 没有奇度点。
Königsberg桥对应的图
ppt精选版
14
36 军官问题 (欧拉 1779)
The Great Frederic的阅兵难题-------欧拉的困惑
1 1，1 1，2，1 1，3，3，1 1，4，6，4，1 1，5，10，10，5，1 1，6，15，20，15，6，1
ppt精选版
12
七桥问题
近代图论的历史可追溯到18世纪的七桥问 题—穿过Königsberg城的七座桥，要求每座桥 通过一次且仅通过一次。
Euler1736年证明了不可能存在这样的路线。
ppt精选版
21
中国邮递员问题
1962年中国组合数学家管梅谷教授提出了著 名的“中国邮递员问题”。
一个邮递员从邮局出发，要走完他所管辖 的每一条街道，然后返回邮局。那么如何 选择一条尽可能短的路线。
ppt精选版
22
中国邮递员问题
这个问题可以转化为：给定一个具有非负 权的赋权图G，
（1）用添加重复边的方法求G的一个Euler赋

＝{a，b}，B＝{b，c，d}；其二是，A包含B，如A＝{a，b，c}，
B＝{b，c}．
2．∈与⊆、a 与{a}、{0}与 Ø 的区别 (1)∈与⊆的区别：∈表示元素与集合之间的 1 3 关系，因此，有3∈Q， 3 ∉Q 等；⊆表示集合与 集合之间的关系，因此，有 Q⊆R，Ø⊆R 等． (2)a 与{a}的区别： 一般地， 表示一个对象， a 而{a}表示由一个元素组成的集合(常称单元素 集)，a 是集合{a}的一个元素．因此有 2∈{2}， 不能写成 2＝{2}．
集时要注意不但要求 A⊆B，同时在 B 中至少要有一个元素不属
于 A.
难点
如何区分∅,{∅},0,{0}
(1)∅∈{∅}，此时∅作为元素，而{∅}则为元素是∅的集合；
(2)∅ {∅}中，∅和{∅}均作为集合来理解．
这样就符合空集是任何非空集合的真子集这一事实，同时 ．．．．．． 不要把数 0 或集合{0}与空集∅混淆，数 0 不是集合，{0}是含有 一个元素 0 的集合，而∅是不含任何元素的集合，更不要把空集 错误地写成{空集}或{∅}．
m进行讨论，然后借助于数轴分析A⊆B成立的条件．
【解析】 ∵B⊆A， ①当 B＝Ø 时，m＋1<2m－1，解得 m>2；
－3<2m－1 ②当 B≠Ø 时，有m＋1<4 ， m＋1≥2m－1
解得－1<m≤2. 综上可知 m 的取值范围是{m|m>－1}．
(1)分析集合关系时，首先要分析、简化每个集合．(2)此类 问题通常借助数轴，利用数轴分析法，将各个集合在数轴上表


(1)两个集合相等，则所含元素完全相同，与顺序无关，但要注意
检验，排除与集合元素互异性或与已知相矛盾的情形． (2)若两个集合中元素均无限多个，要看两集合的代表元素是否一

组合数学概述
(Combinatorial mathematics)
•Nim游戏： 是一种两人玩的游戏，玩家双方对一 堆硬币。假设k堆硬币，每堆分别为n1,n2,…nk枚硬 币。这一游戏的目标就是取得最后一枚硬币。游戏 规则如下： 1）玩家轮番出场； 2）当轮到一个玩家取子时，他们都要从选择的 硬币堆中至少取走一枚硬币；（这位玩家可以把所 选硬币堆都取走，于是剩下一个空堆，这时它“退 出”） 当所有的硬币堆都空了的时候，游戏结束。走最后 一步的玩家，即取走最后一枚硬币的玩家获胜。
则集合A的r-圆排列为
P n, r n! M r r (n r )!
注意：把一个圆排列旋转可得到另一个圆排列，这两个圆排列 是相同的。 例1 由数字1,2,3,4,5,6可以构成多少个数字互不相同的四位
数.
例2 将具有9个字母的单词FRAGMENTS进行排列,要求A总 是紧跟在字母R的右边,问有多少种这样的排法. 答案：
相关课程
《数学分析》《高等代数》《离散数学》
参考教材:



孙世新编,《组合数学》,电子科技大学出版; 社,2006年 孙淑玲编,《组合数学》,(第三版)中国科学技 术大学出版社,2012年; 卢开澄,卢华明编,《组合数学》,清华大学出版 社,2002年; Richard A.Brualdi著,冯速等译,《组合数学》 (第五版),机械工业出版社,2012年.
例 题
例1、有一所学版本的法汉词典；第二类是四种 不同类型的数学参考书；第三类是二 种不同的奖杯。这位优胜者只能挑选 一样奖品。那么，这位优胜者挑选奖 品的方法有多少种？
解：设S是所有这些奖品的集合，Si是第 i类奖品的集合 (i=1,2,3)，显然，Si∩Sj=Φ (i≠j) ，根据加法法则有