现代工程数学 完整版全套优质课件（可编辑）

1、现代工程数学 完整版全套优质课件 教材和参考书教材Introductory Combinatorics(组合数学)R. A. Bruadli 著 机械工业出版社第三版(中文)38 元 第三版(英文)35 元第四版(中文)45 元 第四版(英文)59 元销售经理余勇:参考书组合数学引论 孙淑玲 许胤龙 中国科学技术大学出版社组合数学 卢开澄 清华大学出版社组合数学第 1 章 什么是组合数学第 2 章 鸽巢原理第 3 章 排列与组合第 4 章 生成排列和组合第 5 章 二项式系数第 6 章 容斥原理及应用第 7 章 递推关系和生成函数第 8 章 特殊计数序列第10章 组合设计第1章 什么是组合数学

2、组合数学是研究“安排”的学科。主要研究以下四类问题。1. 存在性问题(是否存在某种安排)2. 计数问题(安排的个数、枚举、分类)3. 构造问题(寻找安排的算法)4. 优化问题(找出一定条件下的最优安排)排课表问题需安排甲、乙、丙、丁四位教师教英语、日语、德语、法语四门课,每人教一门。甲和乙能教英语、日语,丙能教英语、德语、法语,丁只能教德语,是否能够排出课表?甲、乙、丙、丁分别教英语、日语、法语、德语。棋盘完美覆盖问题一个多米诺骨牌可覆盖同一行或同一列两相邻方格。若用若干多米诺骨牌覆盖棋盘所有方格,并且多米诺骨牌不重叠,则称该覆盖为完美覆盖。mn 棋盘有完美覆盖 iff m 和 n 中至少有一

3、个是偶数。当 m 是偶数时,每块多米诺骨牌竖放。当 m 是奇数且 n 是偶数时,每块多米诺骨牌横放。当 m 和 n 都是奇数时,棋盘的方格数 mn 是奇数。幻方2在由 1, 2, , n 组成的 nn 方阵中,若每行之和、每列之和、每条对角线之和都相等,则称该方阵为 n 阶幻方。对于 n2,存在 n 阶幻方。例如,左下方方阵是 3 阶幻方。若右下方方阵是 2 阶幻方,则 u + v u + y,所以 v y,矛盾。无 2 阶幻方。8 1 6?u v3 5 7x y4 9 2?计数问题3 将三角形顶点染红、蓝两色,共有 2 8 种方法,若一种染色旋转后可变为另一种,则认为这两种染色相同,那么仅有

4、 4 种方法(分别有 0, 1, 2, 3 个顶点染红色)。有多少种方法将正整数 n 表示成正整数之和,即 n 有多少个分拆。如 4 有 5 个分拆:4,3 + 1,2 + 2,2 + 1 + 1,1 + 1 + 1 + 1构造问题构造 n 阶幻方的方法,其中 n 是奇数。将 1 放在第一行中间。自左下至右上沿对角线顺次放随后各数,将最后一行认为是第一行上面的行,第一列认为是最后一列右面的列。若要放数的位置已有数,则将数放在原数下方。8 1 63 5 74 9 2?优化问题A , ?, A 地分别生产某种商品a , ?, a 吨,B , ?, B 地1 m 1 m 1 nm n分别销售该种商品

5、b , ?,b 吨, ab (供需平衡)。1 niji ?1 j ?1从 A 到B 的运价为每吨c 元。如何安排运输最经 济?i j ijm n设从 A 到B 的运量为 x 吨。求 min c x?i j ij ij iji ?1 j ?1n m约束条件 xa , xb?ij i ij jj ?1 i ?1第 2 章 鸽巢原理本章主要讨论简单形式和加强形式的鸽巢原理及其应用。本章还简单讨论鸽巢原理的推广:Ramsey 定理。2.1 鸽巢原理:简单形式2.2 鸽巢原理:加强形式2.3 Ramsey定理作业2.1 鸽巢原理:简单形式定理2.1.1若将多于 n 个物体放入 n 个盒子,则至少有一个盒

6、子中的物体数大于 1。存在从 A 到 B 的单射(一对一的函数)当且仅当| A | B | 。存在从 A 到 B 的满射(映上的函数)当且仅当| A | B | 。存在从 A 到 B 的双射(一一对应)当且仅当| A | | B | 。鸽巢原理应用从 1, 2, , 200 中任意选出 101 个数,必有两个数其中一个能够整除另一个。k 证明 将数表示成形式 2a,其中 a 是奇数。小于 200 的奇数只有 100 个,即 1, 3, , 199,所以这 k j 101 个数中必有两数表示为 2a 和 2a ,k j2a | 2a 当且仅当 k j鸽巢原理应用设 n 是正整数,必存在由数字 0

7、 和 7 组成的正整数能被 n 整除。证明 7, 77, ?, 77 ?7是n ?1个不同正整数,它们被n除n ?1个余数只有n种可能,所以必有两数被 n除余数相同。设ij, 77 ?7和77 ?7被n除余数相同。则它们的差为i个 j个77 ?700 ?0,这是能被n整除的数。j ?i个 i个中国剩余定理设 m 和 n 是互素的正整数,即它们的最大公约数是 1,0a m ,0b n,必存在正整数 x 使得,m 除 x 余 a,n 除 x 余 b。证明 考虑 n 个数 a, m + a, , n1m + a若其中两数 im + a 和 jm + a 被 n 除余数相同,则n | ijm ,n |

8、 i ?j,0 | i ?j | n,矛盾。a, m + a, , n1m + a 被 n 除余数各不相同,其中有 mk + a 被 n 除余 b,取 x mk + a 。2.2 鸽巢原理:加强形式定理2.2.1 设 q , q 是正整数。将1 n q + + qn + 11 n 个物体放入 n 个盒子,或者第 1 个盒子中至少有 q 个物体,或者第 n 个盒子中至少有 q1 n 个物体。证明 否则物体总数至多q ?1 + + q1 q + + qn 1 n 1 n 取 q q 2,就退化为简单形式的鸽巢原1 n 理。2证明由n ?1 个实数组成的序列a , ?,a ,或者有长度21n ?1为

9、n ?1 的递增子序列,或者有 长度为n ?1 的递减子序列。证明 设 m 为从 a 开始的最长递增子序列长度。若无长i i度为n ?1 的递增子序列,则每个 mn ,m , ?,m 中必2i 1n ?1有n ?1 个相同的。设 m m ,其中k k 。k k 1 n ?11 n ?1我们证明a , ?,a 是递减子序列。若 aa ,则将k k k k1 n ?1 i i ?1a 放在从 a 开始的最长递增子序列 前面就得到更长的k ki i ?1递增子序列,这与mm 矛盾。k ki i ?12.3 Ramsey 定理用 K 表示 n 阶完全无向图,用红、蓝两种颜色为n K 的边染色,若每条边

10、都染成红(蓝)色,则称n 它为红(蓝) K 。n K K K K2 3 4 5设正整数 p, m, n2,引进记号 K ?K , K :p m n若用红、蓝两种颜色为 K 的边任意染色,则总存p 在红 K 或蓝 K 。m nRamsey 定理 若正整数 m, n2,则存在正整数 p 使得 K ?K , K 。并称使 K ?K , K 成立的最小p m n p m n 正整数 p 为 Ramsey数 rm, n。K ?K , K 不成立。5 3 3 由此可知,r 3, 3 5。r 3, 3 6设 K 的六个顶点分别为 v , , v 。 v 与 6 1 6 1 v , , v 的连边中必有三个是

11、同色的,不妨设 2 6 v 与 v , v , v 的连边都是红色,若三角形 v v v1 2 3 4 2 3 4 中某边是红色的,则有红三角形。若三角形 v v v 中边都是蓝色的,则有蓝三角形。2 3 4 因此, K ?K , K 。6 3 3 r 3, 36,因此,r 3, 3 6。显然,rm, n rn, m。 rm, 2 m 。若 K 中都是红边,则有红 K ;若 K 中有蓝边,m m m 则有蓝 K 。所以 KK , K 。2 m m 2 若 K 中都是红边,则既没有红 K ,也没有蓝 m ?1 mK 。所以 KK , K 不成立。2 m ?1 m 240r 3, 10 r 10,

12、 343,即KK , K 成立且 KK , K 不成立。43 3 10 39 3 10 对于 i 40, 41, 42,不知 KK , K 是否成立。i 3 10 r k, l 表可以将Ramsey 定理推广到任意多种颜色的情况。引进记号 KKn , , Knp 1 k表示:用 k 种颜色 c , c 为 K 的边任意染色,或1 k p 者有一个被染成 c 色的 Kn ,或者有一个被染1 1成 c 色的 Kn 。k kRamsey 定理 若 n , n2,则存在正整数p使得1 kKKn , , Knp 1 k使得 KKn , , Kn 成立的最小正整数 p 称为p 1 kRamsey 数 rn

13、 , n 。1 k r3, 3, 3 17无向图中的边是顶点集 的2 元子集,可以将 Ramsey 定理t推广到为t 元子集染色。用 K 表示一个 n 元集的所有t 元n子集的集合。Ramsey定理 设 t 是正整数,q , ?, qt ,则存在正整数1 kp 使得t t tKK , ?, Kp q q1 k即当用k 种颜色c , ?,c 为一个 p 元集 A 的所有t 元子集任1 k意染色时,或者总有一个 A 的q 元子集的所有t 元子集都1染成c 色,或者总有一个 A 的q 元子集的所有t 元子1 k集都染成c 色。kt t t使得 KK , ?, K 成立的最小正整数 p 称为Ramse

14、y 数p q q1 kr q , ?, q 。t 1 kRamsey 定理是加强形式鸽巢原理的推广。令 t 1,将 “为 1 元子集 u 染色 c ” 看作 “将 u i 放入第 i 个盒子中”,可以得出r q , q q + + qk + 11 1 k 1 k 作业5,10,15,16第 3 章 排列与组合3.1 两个基本的计数原理3.2 集合的排列3.3 集合的组合3.4 多重集的排列3.5 多重集的组合作业3.1 两个基本的计数原理加法原理设 S SSS 是 m 个两两不相交集合1 2 m 之并,则 | S | | S | + | S | + + | S |。1 2 m乘法原理| AB

15、| | A | B |其中 AB a, b: a ?A, b ?B相等原理如果在集合 A 和 B 之间存在一一对应,则 | A | | B | 。例 确定 10! 的正整数因子数8 4 2 10! 2310 2357i j k lm | 10! iff m 2357 , 其中 0i8, 0j4, 0k2, 0l110! 的正整数因子数 9532 270 恰有一位数字是 5 的 10000 的正整数有多少个?解法1 其中有一个一位数:5。在二位数中,若十位为 5,则个位有 9 种取法;若个位为 5,则十位有 8 种取法(不能取 0)。共有 9 + 8 17 个二位数。在三位数中,若百位为 5,则

16、十位和个位各有 9 种取法;若十(个)位为 5,则百位有 8 种取法(不能取 0) ,个(十)位有 9 种取法。共有99 + 289 225 个三位数。在四位数中,若千位为 5,则百位、十位、个位各有 9 种取法;若百(十、个)位为 5,则千位有 8 种取法(不能取 0),其余各位各有 9 种取法。共有 999 + 3899 2673 个四位数。总共有 1 + 17 + 225 + 2673 2916 个数。解法2 将每个数都看作四位数,例如,将 1 看作 0001,某位数字是 5,其余位有 9 种选择,数字 5可以在个、十、百、千位,所以,满足条件的数总共有 4999 2916 个。3.2

17、集合的排列集合 S 的 r 排列是长度为 r 的 S 中不同元素的序列。包含集合 S 的每个元素的排列称为S 的全排列。 如 a, b, c的 2 排列有 6 个:ab, ba, ac, ca, bc, cb。n 元集的 r 排列的数目记为 Pn, r。若 r n,则 Pn, r 0。Pn, 0 1(空序列), Pn, 1 n。排列数的计算公式定理3.21 若rn , 则n !Pn, rnn ?1 ?nr ?1nr !证明 第 1 个元素有 n 种选择,第 2 个元素有n ?1 种选择,。各位非 0、互异、数字 5 和 6 不相邻的 7 位数有多少个?解法1 不出现 5 和 6 的满足条件的

18、7 位数是集合 A 1, 2, 3, 4, 7, 8, 9 的全排列,有 P7, 7 个。以下用代表不是 5 和 6 的数字,用?代表数字 5 或 6。考虑只出现 5,不出现 6 的数。从 A 中取出 6 个数字排好,再在 7 个位置之一插入 5,有 7P7, 6个。? ? ? ? ? ? ?出现 6 不出现 5 的数也有 7P7, 6 个。考虑 5 和 6 都出现的情况。第 1 位是 5。将不是 6 的 5 位排好,将 6 插入 5 个位置之一,有 5P7, 5 个。5 ? ? ? ? ?最后位是 5,有 5P7, 5 个。5 在中间位置。将不是 5 和 6 的 5 位排好, 将 5 插入 4 个位置之一,将 6 插入 5 个位置之一,有 45P7, 5 个。? 5 ? ? ? ?P7, 72 ?7P7, 62 ?54 ?5P7, 514 ?7 ! 30 ?7 !7 ! 30 ?7 !1! 2!解法 29! 9 ?8 ?7 !共有P9, 7 36 ?7 ! 个各位互异的数。2! 2考虑5 和6 相邻的数的个数。先排 列好不是5 和6 的5 位数字,再在6 个位置之一插入56 或者 65 ,所以,12 ?7 !这样的数有2 ?6P7, 5? 6 ?7 ! 个。2!? ?