热门搜索:

  • /?68
  • 下载费用:2 金币 ?

现代工程数学第1、2、3章PPT.pdf

关?键?词:
工程数学
资源描述:
教材和参考书 教材 Introductory Combinatorics(组合数学) R. A. Bruadli 着 机械工业出版社 第四版(中文)45 元 第四版(英文)59 元 销售经理余勇:13801271785 参考书 组合数学引论 孙淑玲 许胤龙 中国科学技术大 学出版社 组合数学 卢开澄 清华大学出版社 成绩 作业 40% 考试 60% 组合数学 第 1 章 什么是组合数学 第 2 章 鸽巢原理 第 3 章 排列与组合 第 4 章 生成排列和组合 第 5 章 二项式系数 第 6 章 容斥原理及应用 第 7 章 递推关系和生成函数 第 8 章 特殊计数序列 第1章 什么是组合数学 组合数学是研究“安排”的学科。主要研究以下四 类 问题。 1. 存在性问题(是否存在某种安排) 2. 计数问题(安排的个数、枚举、分类) 3. 构造问题(寻找安排的算法) 4. 优化问题(找出一定条件下的最优安排) 排课表问题 需安排甲、乙、丙、丁四位教师教英语、日语、德 语、法语四门课,每人教一门。 甲和乙能教英语、日语, 丙能教英语、德语、法语, 丁只能教德语, 是否能够排出课表? 甲、乙、丙、丁分别教英语、日语、法语、德语。 棋盘完美覆盖问题 一个多米诺骨牌可覆盖同一行或同一列两相邻方格。 若用若干多米诺骨牌覆盖棋盘所有方格,并且多米 诺骨牌不重叠,则称该覆盖为完美覆盖。 m × n 棋盘有完美覆盖 iff m 和 n 中至少有一个是 偶数。 当 m 是偶数时,每块多米诺骨牌竖放。 当 m 是奇数且 n 是偶数时,每块多米诺骨牌横放。 当 m 和 n 都是奇数时,棋盘的方格数 mn 是奇数。 幻方 在由 1, 2, …, n 2 组成的 n × n 方阵中,若每行之 和、每列之和、每条对角线之和都相等,则称 该方阵为 n 阶幻方。对于 n ≠ 2,存在 n 阶幻 方。例如,左下方方阵是 3 阶幻方。若右下方 方阵是 2 阶幻方,则 u + v = u + y,所以 v = y, 矛盾。无 2 阶幻方。 ! ! ! “ # $ $ $ % & 2 9 4 7 5 3 6 1 8 ! “ # $ % & y x v u计数问题 将三角形顶点染红、蓝两色,共有 2 3 = 8 种方法, 若一种染色旋转后可变为另一种,则认为这两种染 色相同,那么仅有 4 种方法(分别有 0, 1, 2, 3 个顶 点染红色)。 有多少种方法将正整数 n 表示成正整数之和,即 n 有多少个分拆。如 4 有 5 个分拆: 4,3 + 1,2 + 2,2 + 1 + 1,1 + 1 + 1 + 1 构造问题 构造 n 阶幻方的方法,其中 n 是奇数。 将 1 放在第一行中间。 自左下至右上沿对角线顺次放随后各数,将最后 一行认为是第一行上面的行,第一列认为是最后 一列右面的列。 若要放数的位置已有数,则将数放在原数下方。 ! ! ! “ # $ $ $ % & 2 9 4 7 5 3 6 1 8优化问题 j m i ij i n j ij m i n j ij ij ij j i ij j i n j j m i i n n m m b x a x x c x B A c B A b a b b B B a a A A = = = ∑ ∑ ∑ ∑ ∑ ∑ = = = = = = 1 1 1 1 1 1 1 1 1 1 min , , , , , , , , , 约束 条件 吨。 求 的运 量为 到 设从 济? 元。 如何安 排运输最 经 运价 为每吨 的 到 (供 需平衡 )。从 吨, 地分 别销售 该种商品 吨, 地分 别生产 某种商品 ? ? ? ?第 2 章 鸽巢原理 本章主要讨论简单形式和加强形式的鸽巢原理 及其应用。 本章还简单讨论鸽巢原理的推广:Ramsey 定理。 2.1 鸽巢原理:简单形式 2.2 鸽巢原理:加强形式 2.3 Ramsey定理 作业 2.1 鸽巢原理:简单形式 定理2.1.1 若将多于 n 个物体放入 n 个盒子,则 至少有一个盒子中的物体数大于 1。 设 f : A → B ,将 A 看做物体的集合, B 看做盒 子的集合,物体 a 放在盒 子 f(a) 中。 如果 | A | > | B |,则 f 不是从 A 到 B 的单射 (一对一的函数) 。 鸽巢原理应用 从 1, 2, …, 200 中任意选出 101 个数,必有两个数 其中一个能够整除另一个。 证明 将数表示成形式 2 k × a,其中 a 是奇数。小 于 200 的奇数只有 100 个,即 1, 3, …, 199,所以 这 101 个数中必有两数表示为 2 k × a 和 2 j × a , 2 k × a | 2 j × a 当且仅当 k ≤ j 鸽巢原理应用 设 n 是正整数,必存在由数字 0 和 7 组成的正 整数能被 n 整除。 整除 的数。 ,这 是能被 差为 除余 数相同 。则 它们的 被 和 , 除余 数相同 。设 被 种可 能,所 以必 有两数 余数 只有 除 个不 同正整 数, 它们被 是 , , , 个 个 个 个 个 n n j i n n n n i i j j i n ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 00 7 77 7 77 7 77 1 7 77 77 7 1 ? +5。 r (3, 3) = 6 设 K 6 的六个顶点分别为 v 1 , …, v 6 。 v 1 与 v 2 , …, v 6 的连边中必有三个是同色的,不妨设 v 1 与 v 2 , v 3 , v 4 的连边都是红色,若三角形 v 2 v 3 v 4 中某边是红色的,则有红三角形。若三角 形 v 2 v 3 v 4 中边都是蓝色的,则有蓝三角形。 因此, K 6 → K 3 , K 3 。 r (3, 3) ≤ 6,因此, r (3, 3) = 6。 显然,r(m, n) = r(n, m)。 r(m, 2) = m 。 若 K m 中都是红边,则有红 K m;若 K m 中有蓝 边,则有蓝 K 2 。所以 K m → K m , K 2 。 若 K m-1 中都是红边,则既没有红 K m,也没有蓝 K 2 。所以 K m-1 → K m , K 2 不成立。 40 ≤ r(3, 10) = r(10, 3) ≤ 43,即 K 43 → K 3 , K 10 成立且 K 39 → K 3 , K 10 不成立。 对于 i = 40, 41, 42,不知 K i → K 3 , K 10 是否成立。 r (k, l) 表 可以将 Ramsey 定理推广到任意多种颜色的情况。 引进记号 K p → K n 1 , …, K n k表示:用 k 种颜色 c 1 ,…, c k 为 K p 的边任意染色, 或者有一个被染成 c 1 色的 K n 1,…,或者有一个 被染成 c k 色的 K n k。 Ramsey 定理 若 n 1 ,…, n k ≥ 2,则有正整数 p 使 得 K p → K n 1 , …, K n k使得 K p → K n 1 , …, K n k 成立的最小正整数 p 称为 Ramsey 数 r(n 1 ,…, n k )。 r(3, 3, 3) = 17 。 数 称为 成立 的最小 正整数 使得 色。 集都 染成 元子 元子 集的所 有 的 ,或 者总有 一个 色, 染成 元子 集都 元子 集的所 有 的 个 意染 色时, 或者总有 一 元子 集任 的所 有 元集 为一 个 种颜 色 即当 用 使得 ,则 存在正 整数 是正 整数, 设 子集 的集合 。 元 元集 的所有 表示 一个 元子 集染色 。用 推广 到为 定理 元子 集,可 以将 的 无向 图中的 边是顶点 集 ) , , ( Ramsey , , , , , , , , Ramsey 2 1 1 1 1 1 1 1 k t t q t q t p k k k t q t q t p k t n q q r p K K K c t q A c t q A t A p c c k K K K p t q q t t n K t k k ? ? ? ? ? ? → → ≥ RamseyRamsey 定理是加强形式鸽巢原理的推广。 令 t = 1,将 “为 1 元子集 {u} 染色 c i ” 看作 “将 u 放入第 i 个盒子中”,可以得出 r 1 (q 1 ,…, q k ) = q 1 + … + q k - k + 1 作业 7,11,14,17 第 3 章 排列与组合 3.1 四个基本的计数原理 3.2 集合的排列 3.3 集合的组合 3.4 多重集的排列 3.5 多重集的组合 作业 3.1 四个基本的计数原理 加法原理 设 S = S 1 ∪ S 2 ∪ … ∪ S m 是 m 个两两不相交集合 之并,即若 i ≠ j,则 S i∩ S j= ? 。那么, | S | = | S 1 | + | S 2 | + … + | S m|。 乘法原理 | A 1× … × A m| = | A | × … × | A m| 其中 A 1× … × A m= {(a 1 ,…, a m ): a 1 ∈ A 1 ,…, a m ∈ A m } 减法原理 设 A 是有限集合 U 的子集, A 的补 集 则 A 的元素个数 | A| 由以下公式给出: 除法原理 如果有限集 S 被分成包含同样多个元 素的 k 部分,那么部分的数目 k 由以下公式给出: } : { A x U x A ? ∈ = | | | | | | A U A ? = 数 在一 个部 分中 的元 素个 | |S k =相等原理 如果在集合 A 和 B 之间存在一一对应, 则 | A | = | B | 。 例 n 元集 S = {1, …, n} 的子集个数等于由 0 和 1 组成的长度为 n 的串的个数。 证明 可在 S 的子集的集合与由 0 和 1 组成的长 度为 n 的串的集合之间建立一一对应如下: 让 S 的每个子集 A 对应串 a 1 …a n,其中 对于每个 i∈ S , ! “ # $ % = A i A i a i 若 若 0 1例 确定 10! 的正整数因子数 10! = 2 × 3 × … × 10 = 2 8 × 3 4 × 5 2 × 7 m | 10! iff m = 2 i × 3 j × 5 k × 7 l, 其中 0 ≤ i ≤ 8, 0 ≤ j ≤ 4, 0 ≤ k ≤ 2, 0 ≤ l ≤ 1 10! 的正整数因子数 = |{(i, j, k, l): 0 ≤ i ≤ 8, 0 ≤ j ≤ 4, 0 ≤ k ≤ 2, 0 ≤ l ≤ 1}| = 9 × 5 × 3 × 2 = 270 恰有一位数字是 5 的 n,则 P(n, r) = 0。 P(n, 0) = 1(空序列), P(n, 1) = n。 排列数的计算公式 ! ) ( ! ) 1 ( ) 1 ( ) , ( r n n r n n n r n P ? = + ? ? = ? 定理3.2.1 若 r ≤ n,则 证明 第 1 个元素有 n 种选择,第 2 个元素 有n - 1 种选择,…。 n 元集的全排列数为 n!。 各位非 0、互异、数字 5 和 6 不相邻的 7 位数有多 少个? 解法1 不出现 5 和 6 的满足条件的 7 位数是集合 A ={1, 2, 3, 4, 7, 8, 9} 的全排列,有 P(7, 7) 个。 以下用□ 代表不是 5 和 6 的数字,用〇代表数字 5 或 6。 考虑只出现 5,不出现 6 的数。从 A 中取出 6 个 数字排好,再在 7 个位置之一插入 5,有 7 × P(7, 6) 个。 〇 □ 〇 □ 〇 □ 〇 □ 〇 □ 〇 □ 〇 出现 6 不出现 5 的数也有 7 × P(7, 6) 个。 考虑 5 和 6 都出现的情况。 第 1 位是 5。将不是 6 的 5 位排好,将 6 插入 5 个 位置之一,有 5 × P(7, 5) 个。 5 □ 〇 □ 〇 □ 〇 □ 〇 □ 〇 最后位是 5,有 5 × P(7, 5) 个。 5 在中间位置。将不是 5 和 6 的 5 位排好, 将 5 插入 4 个位置之一,将 6 插入 5 个位置之一,有 4 × 5 × P(7, 5) 个。 〇 □ 5 □ 〇 □ 〇 □ 〇 □ 〇 ! 7 30 ! 2 ! 7 30 ! 1 ! 7 14 ! 7 ) 5 , 7 ( ) 5 4 5 2 ( ) 6 , 7 ( 7 2 ) 7 , 7 ( × = × + × + = × × + × + × × + P P P个各 位互 异的 数。 共有 ! 7 36 2 ! 7 8 9 ! 2 ! 9 ) 7 , 9 ( × = × × = = P 个。 这样 的数有 ,所 以, 或者 个位 置之一 插入 位数 字,再 在 的 和 列好 不是 相邻 的数的 个数 。先排 和 考虑 ! 7 6 ! 2 ! 7 12 ) 5 , 7 ( 6 2 65 56 6 5 6 5 6 5 × = × = × × P 〇 □ 〇 □ 〇 □ 〇 □ 〇 □ 〇 各位不是0、互异、数字 5 和 6 不相邻的 7 位数有 36 × 7 ! - 6 × 7 ! = 30 × 7 ! 个。 解法 2 循环排列 普通排列更恰当些应叫做线 性排列。把 r 个元素排成一 个圆称为循环 r-排列,或 r-圆排列。每个循环 r-排列 对应 r 个不同的线性 r-排列。 例如,左边的循环 4-排列对 应 4 个线性 4-排列: 1234,2341,3412,4123 1 2 3 4 循环排列数 定理3.2.2 n 元集的循环 r-排列数为 r 元集的循环 r-排列数为 (r - 1) ! 。 ! ) ( ! ) , ( r n r n r r n P ? × =例 10 男生 5 女生围圆桌聚餐,任何两个女生不相 邻的坐法有多少种? 解 男生先坐好,有 9!种坐法。固定一种男生坐 法,然后让女生插入10 个空档,女生之间还存 在排序问题,故有 P (10, 5) 种排法。所以,共 有 9! × P (10, 5) 种坐法。 例 10 人围坐一圆桌,其中甲、乙两人不愿挨着 坐,共有多少种坐法? 解 若不考虑甲和乙是否挨着,有 9 ! 种坐法。若 甲固定坐在乙左边,可将甲和乙看作一人,有 8 ! 种坐法。若甲固定坐在乙右边,也有 8 ! 种 坐法。所以,满足条件的坐法有 9 ! - 2 × 8 ! 种。 3.3 集合的组合 集合 S 的 r-组合即为 S 的 r 元子集,将 n 元集 的 r-组合数记为 。 ! ! “ # $ $ % & r n ! ) ( ! ! ! ) , ( ! ) , ( 0 1 1 0 0 r n r n r r n P r n r n r r n P n r n n n n n r n n r ! = = “ “ # $ % % & ’ “ “ # $ % % & ’ = ( ( = “ “ # $ % % & ’ = “ “ # $ % % & ’ = “ “ # $ % % & ’ = “ “ # $ % % & ’ > 因此 , 对于 。 , 。 ,则 若 3.3.1推论3.3.1 设 0 ≤ r ≤ n,则 证法一 设 | S | = n ,让 S 的 r-组合 A 对应它的补集 (n - r)-组合ā ,可在 r-组合与 (n - r) -组合之间建立一一 对应。 证法二 ! ! “ # $ $ % & ’ = ! ! “ # $ $ % & r n n r n ! ! “ # $ $ % & ’ = ’ = ! ! “ # $ $ % & r n n r n r n r n ! ) ( ! !定理3.3.2 证明 n 元集有 0, 1, …,n 元子集。对于 n 元集 S = {a 1 , a 2 ,…,a n } 的每个子集 A,对每个 a i , 可有两种选择, a i ∈ A 或者 a i ? A,所以 S 有 2 n 个子集。 n n n n n 2 1 0 = ! ! “ # $ $ % & + + ! ! “ # $ $ % & + ! ! “ # $ $ % & ?种坐 法。 种坐 法。因 此, 共有 种坐 法,后 排有 人坐 前排。 前排 有 人中 选 人。 从 前后 排各坐 种坐 法。 共有 种坐 法。因 此, 种坐 法,后 排有 前排 有 人坐 前排。 人中 选 人。 从 人, 后排坐 前排 坐 排。 人既 可坐前 排又 可坐后 有 坐法 ? 人总 坐后排 。有 多少种 人总 坐前排 , 人, 其中 个。 有学生 教室 有两排 座位 ,每排 ) 7 , 8 ( ) 7 , 8 ( 2 5 ) 7 , 8 ( ) 7 , 8 ( 2 5 7 . 2 ) 6 , 8 ( ! 8 3 5 ) 6 , 8 ( ! 8 3 5 6 8 . 1 5 4 5 14 解法 P P P P P P ! ! “ “ # $ % % & ’ ! ! “ “ # $ % % & ’ = ( ( 1 4 5 14 8种坐 法。 ! ! 合起 来总共 有 种坐 法。 共有 种坐 法。因 此, 种坐 法,后 排有 前排 有 人坐 前排。 人中 选 人。 从 人, 后排坐 前排 坐 2 2 ) ! 8 ( 5 . 17 ) 6 , 8 ( 8 1 5 )) 7 , 8 ( ( 2 5 ) 6 , 8 ( 8 3 5 ) 8 , 8 ( ) 6 , 8 ( 1 5 ) 8 , 8 ( ) 6 , 8 ( 1 5 8 6 . 3 ! = ! ! “ “ # $ % % & ’ + ! “ “ # $ % % & ’ + ! ! “ “ # $ % % & ’ ! ! “ “ # $ % % & ’ P P P P P P P2 ) ! (8 17.5 ! 2 ! 4 ! 3 ! 7 ! 8 ! 8 ! 5) (7 ! 4) (8 ! 5) (8 ! 7 ! 8 ! 8 5) (7, 4) (8, 5) (8, ) 5 , 7 ( 5 7 5 ) 4 , 8 ( 4 ) 5 , 8 ( 5 5 4 5 14 解法 4 5 14 8 × = = ? ? ? = × × = ? ? P P P P P P 因此 ,坐法 数为 种坐 法。 个座 位,有 座位 中的 个 人可 选择剩 余的 的 既可 坐前排 又可坐后 排 种坐 法, 人有 总坐 后排的 种坐 法, 人有 总坐 前排的 排。 人既 可坐前 排又可坐 后 有 坐法 ? 人总 坐后排 。有多少 种 人总 坐前排 , 人, 其中 个。 有学生 教室 有两排 座位,每 排 2某班有男生 21人,女生 14人,需选举 4 人组成班 委会,要求班委会有男有女,可能有多少种选举结 果? 解法一 班委会有 i 个女生的选举结果有 种,选举结果总数为 解法二 若不要求班委会有男有女,则选举结果数 为 ,所求数为 ! ! “ # $ $ % & ’ ! ! “ # $ $ % & i i 4 21 14 374 , 45 4 21 14 3 1 = ! ! “ # $ $ % & ’ ! ! “ # $ $ % & ( = i i i ! ! “ # $ $ % & 4 35 374 , 45 4 14 4 21 4 35 = ! ! “ # $ $ % & ’ ! ! “ # $ $ % & ’ ! ! “ # $ $ % &某班有男生 21 人,女生 14 人,需选举 4 人组成班 委会,要求班委会有男有女,可能有多少种选举结 果? 解 从男、女生中各选一人,再任选两人,故选举 结果总数为 这样做对吗?如果不对,错在哪里? 232 , 155 2 33 1 14 1 21 = ! ! “ # $ $ % & ! ! “ # $ $ % & ! ! “ # $ $ % &3.4 多重集的排列 定理3.4.1 多重集 S = {∞? a 1 , ∞? a 2 ,…, ∞? a k }的 r-排 列数为 k r 。 证明 S 的 r-排列即为 a 1 , a 2 , …, a k 的长度是 r 的串,其中每个元素都有 k 种选择,所以,r- 排列数为 k r 。 ? ? ? ? 种方 法选取 , 的位 置有 的位 置选定 后, 种方 法选取 , 的位 置有 。 的全 排列数 为 ,则 多重集 设 ! ! “ # $ $ % & ’ ! ! “ # $ $ % & ( ( = + + = 2 1 2 1 1 1 2 1 1 1 1 证法 ! ! ! ! } , , { 定理 n n n a a n n a n n n n a n a n S n n n k k k k 1 3.4.2 ! ! ! ! ! 0 ! ! ! ! )! ( ! )! ( )! ( ! )! ( )! ( ! ! 2 1 2 1 1 1 1 2 1 2 1 1 1 1 2 1 2 1 1 k k k k k k k n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n ? ? ? ? ? ? = = ! ! ! ! ! ! ! ! ! ! = “ “ # $ % % & ’ ! ! ! “ “ # $ % % & ’ ! “ “ # $ % % & ’ ! !定理3.4.2 设 n = n 1 + n 2 + … + n k,则多重集 S = {n 1 ? a 1 ,…, n k ? a k } 的全排列数为 证法2 将所有 n 个元素都看作不同的,则全排列 数为 n!。交换排列中的同一元素,得到同样的排 列,所以每个排列重复了 n 1 ! n 2 ! …n k ! 次,所以 S 的全排列数为 ! ! ! ! 2 1 k n n n n ? ! ! ! ! 2 1 k n n n n ?的正 整数的 个数。 中等 于 是 其中 书上 误为 ,则 方法数 为 若这 些盒子 不被做标 签 个物 体的方 法数为 中放 入 , 个物 体, 中放 入 ,并 使得 个被 做标签 的盒子 放入 个物 体 将 。 是正 整数且 设 i n n l n n n k n n n n l l l n n n n n n B n B B B k c c n n n n n n k i k k n k k k k n k k , , ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! , , , , , , 3.4.3 定理 1 2 1 2 1 2 1 2 1 1 1 1 1 1 1 ? ? ? ? ? ? ? ? ? ? + + =证明 可在多重集 S = {n 1 ? a 1 ,…, n k ? a k } 的全排列集 合和满足要求的将物体放入做标签盒子的方法集 合之间建立一一对应如下: 对于 S 的每个全排列 d 1 …d n,若 d i 是 a j,则 将 c i 放入盒子 B j。 所以,放入做标签盒子的方法数也是 对于放入 i 个物体的 l i 个盒子,有 l i! 种方法为盒 子做标签,所以放入不做标签盒子的方法数为 ! ! ! ! 2 1 k n n n n ? ! ! ! ! ! ! ! 2 1 2 1 k n n n n l l l n ? ?例 将 4 个元素 a, b, c, d 放入红色盒子与蓝色盒 子,每个盒子放两个元素,有以下 6 种方法: 1. 红色盒子: a, b ;蓝色盒子:c, d 。 2. 红色盒子: c, d ;蓝色盒子:a, b 。 3. 红色盒子: a, c ;蓝色盒子:b, d 。 4. 红色盒子: b, d ;蓝色盒子:a, c 。 5. 红色盒子: a, d ;蓝色盒子:b, c 。 6. 红色盒子: b, c ;蓝色盒子:a, d 。 若不为盒子涂色,则第 1, 2 种方法成为一种方法, 第 3, 4 种方法成为一种方法,第 5, 6 种方法成为一 种方法,只有 3 种方法。 3 ! 2 ! 2 ! 0 ! 0 ! 2 ! 0 ! 4 ! ! ! ! ! ! ! 6 ! 2 ! 2 ! 4 ! ! ! , 0 , 0 , 2 , 0 , 4 , 2 , 2 , 2 2 1 4 3 2 1 2 1 4 3 2 1 2 1 = = = = = = = = = = = = n n l l l l n n n n l l l l n n n k例 将 5 个元素 a, b, c, d , e 放入红色盒子与蓝色 盒子,红色盒子放 1 个元素,蓝色盒子放 4 个 元素,有以下 5 种方法: 1. 红色盒子: a ;蓝色盒子: b, c, d, e 。 2. 红色盒子: b ;蓝色盒子:a, c, d, e 。 3. 红色盒子: c ;蓝色盒子: a, b, d, e 。 4. 红色盒子: d ;蓝色盒子:a, b, c, e 。 5. 红色盒子: e ;蓝色盒子:a, b, c, d 。 若不为盒子涂色,仍然有 5 种方法。 不是 整数。 ! 4 ! 1 ! 2 ! 5 ! ! ! ! 5 ! 4 ! 1 ! 0 ! 1 ! 0 ! 0 ! 1 ! 5 ! ! ! ! ! ! ! ! 5 ! 4 ! 1 ! 5 ! ! ! , 0 , 1 , 0 , 0 , 1 , 5 , 4 , 1 , 2 2 1 2 1 5 4 3 2 1 2 1 5 4 3 2 1 2 1 = = = = = = = = = = = = = = n n k n n n l l l l l n n n n l l l l l n n n k定理3.4.4 有 k 种颜色的 n 个车,其中第 i 种颜色 的有 n i 个。将这 n 个车摆放在的棋盘上使得任何 两个车不能互相攻击,摆放方法数为 证明 用 (i, j) 表示第 i 行第 j 列方格。 占据 (i 1 , j 1 ) 和 (i 2 , j 2 ) 的车不能互相攻击当且仅当 i 1≠ i 2且 j 1≠ j 2( ) ! ! ! ! 2 1 2 k n n n n ?若 n 个车摆放在 (1, j 1 ), (2, j 2 ), …, (n, j n ),则 j 1j 2 … j n 是{1, 2, … , n}的一个全排列。用 c i 表示第 i 种 颜色的车。摆放车的位置 (1, j 1 ), (2, j 2 ), …, (n, j n ) 确 定之后,{n 1 ? c 1 , n 2 ? c 2 , … , n k ? c k } 的每个全排列对 应一种摆放法。例如, c 1 c 1 c 4 c 2 c 3 c 2 c 1 c 3 对应第 1, 2, 7行摆放 c 1 ,第 4, 6 行摆放 c 2 ,第 5, 8 行摆放 c 3 ,第 3 行摆放 c 4。因此,摆放方法数为 ( ) ! ! ! ! 2 1 2 k n n n n ?例 求 S ={3? a, 2? b, 4? c}的 8 排列数。 {2? a, 2? b, 4? c} 的 8 排列数为 {3? a, 1? b, 4? c} 的 8 排列数为 {3? a, 2? b, 3? c} 的 8 排列数为 S 的 8 排列数为 420 + 280 + 560 = 1260。 420 ! 4 ! 2 ! 2 ! 8 = 280 ! 4 ! 1 ! 3 ! 8 = 560 ! 3 ! 2 ! 3 ! 8 =3.5 多重集的组合 多重集 {n 1 ? a 1 , n 2 ? a 2 ,…, n k ? a k } 的 r-组合是一个多重 集 {m 1 ? a 1 , m 2 ? a 2 ,…, m k ? a k },其中 r = m 1 + m 2 + … + m k,0 ≤ m i ≤ n i ,i = 1,…, k。 例如,{2? a, 1? b, 3? c}的 2-组合如下: {2? a},{1? a, 1? b},{1? a, 1? c},{1? b, 1? c},{2? c} 定理3.5.1 多重集 S = {∞? a 1 , ∞? a 2 ,…, ∞? a k }的 r-组合数为 证明 {x 1 ? a 1 , x 2 ? a 2 ,…, x k ? a k } 是 S 的 r 组合当且仅当 (x 1 , x 2 , …, x k ) 是方程 x 1 + x 2 + …+ x k = r 的非负整数解。 S 的 r-组合数 = 方程 x 1 + x 2 + … + x k = r 的非负整数解 的个数。令 T = {r ? 1, (k-1)? *}。 (x 1 , x 2 , …, x k ) 是 x 1 + x 2 + … + x k = r 的非负整数解 iff 是 T 的全排列。 S 的 r-组合数 = T 的全排列数。 ! ! “ # $ $ % & ’ ’ + = ! ! “ # $ $ % & ’ + 1 1 1 k k r r k r ? ? ? 个 个 个 k x x x 1 1 1 1 1 1 2 1 ? ? ? ? ? ? ?个。 列有 的非 递减序 的长 度是 元素 为 对应 : 组合 之间建 立一 一对应 的 递减 序列与 多重 集 的非 的长 度是 可以 在元素 为 减序 列有多 少个 ? 的非 递 的长 度是 元素 为 个 个 ! ! “ # $ $ % & ’ + ( ) ) ) * ) * r k r r k k x x k k r k r k r k k x x k 1 , , 1 } , , 1 { , , , , 1 , , 1 - } , , 1 { , , 1 , , 1 例 1 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? 汽车智库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:现代工程数学第1、2、3章PPT.pdf
链接地址:http://www.autoekb.com/p-1493.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

copyright@ 2008-2018 mywenku网站版权所有
经营许可证编号:京ICP备12026657号-3?

收起
展开