《离散数学8.12组合计数基础》由会员分享，可在线阅读，更多相关《离散数学8.12组合计数基础（23页珍藏版）》请在金锄头文库上搜索。
1、第第8 8章章 组合计数基础组合计数基础1第第8章章 组合计数基础组合计数基础引言引言 组合问题的处理技巧组合问题的处理技巧8.1 基本计数规则基本计数规则8.2 排列与组合排列与组合8.3 二项式定理与组合恒等式二项式定理与组合恒等式8.4 多项式定理多项式定理2组合问题的处理技巧组合问题的处理技巧一一对应一一对应数学归纳法数学归纳法上下界逼近上下界逼近3一一对应与上下界逼近一一对应与上下界逼近例例1 1 在允许移动被切割的物体的情况下，在允许移动被切割的物体的情况下，最少用多少次切割可以将最少用多少次切割可以将 3 3 3 的立的立方体切成方体切成 27个单位边长的立方体？个单位边长的立方
2、体？ 中间的小立方体的中间的小立方体的6个面都是切割产生的面，每次切割个面都是切割产生的面，每次切割至多产生一个面，至少需要至多产生一个面，至少需要6次切割。存在一种切割方次切割。存在一种切割方法恰好用法恰好用 6 次切割。次切割。例例2 100个选手淘汰赛，为产生冠军至少需要多少轮比赛？个选手淘汰赛，为产生冠军至少需要多少轮比赛？ 方法方法1：50+25+12+6+3+2+1=99 方法方法2：比赛次数与淘汰人数之间存在一一对应，总计淘：比赛次数与淘汰人数之间存在一一对应，总计淘汰汰99人，因此至少需要人，因此至少需要99场比赛场比赛.48.1 基本计数规则基本计数规则8.1.1 加法法则加
3、法法则8.1.2 乘法法则乘法法则8.1.3 分类处理与分步处理分类处理与分步处理5加法法则加法法则加法法则加法法则：事件：事件A 有有 m 种产生方式，事件种产生方式，事件 B 有有n 种产生种产生方式，则方式，则 “事件事件A或或B” 有有 m+n 种产生方式种产生方式.使用条件：事件使用条件：事件 A 与与 B 产生方式不重叠产生方式不重叠适用问题：分类选取适用问题：分类选取推广：事件推广：事件 A1有有 p1种产生方式，事件种产生方式，事件 A2有有 p2 种产生方种产生方式，式，, 事件事件 Ak 有有 pk 种产生的方式，则种产生的方式，则 “事件事件A1或或 A2或或 Ak” 有
4、有 p1+p2+pk 种产生的方式种产生的方式. 6乘法法则乘法法则乘法法则乘法法则：事件：事件A 有有 m 种产生方式，事件种产生方式，事件 B 有有n 种产生种产生方式，则方式，则 “事件事件A与与B” 有有 m n 种产生方式种产生方式.使用条件：事件使用条件：事件 A 与与 B 产生方式彼此独立产生方式彼此独立适用问题：分步选取适用问题：分步选取推广：事件推广：事件 A1有有 p1种产生方式，事件种产生方式，事件 A2有有 p2 种产生方种产生方式，式，, 事件事件 Ak 有有 pk 种产生的方式，则种产生的方式，则 “事件事件A1与与 A2与与 Ak” 有有 p1 p2 pk 种产生
5、的方式种产生的方式. 7分类处理与分步处理分类处理与分步处理分类处理：对产生方式的集合进行划分，分别计数，然分类处理：对产生方式的集合进行划分，分别计数，然后使用加法法则后使用加法法则分步处理：一种产生方式分解为若干独立步骤，对每步分步处理：一种产生方式分解为若干独立步骤，对每步分别进行计数，然后使用乘法法则分别进行计数，然后使用乘法法则分类与分步结合使用：分类与分步结合使用： 先分类，每类内部分步先分类，每类内部分步 先分步，每步又分类先分步，每步又分类8应用实例应用实例例例3 设设A, B, C 是是3个城市，从个城市，从A 到到 B 有有3条道路，从条道路，从B 到到C 有有2条道路，从
6、条道路，从A 直接到直接到 C 有有4条道路，问从条道路，问从 A 到到 C 有有多少种不同的方式？多少种不同的方式？解：解： N=3 2+4 = 10例例4 求求1400的不同的正因子个数的不同的正因子个数 1400=23 52 7 解：正因子为：解：正因子为：2i 5j 7k，其中，其中 0 i 3, 0 j 2, 0 k 1 N=(3+1)(2+1)(1+1)=2498.2 排列与组合排列与组合引言引言 选取问题选取问题8.2.1 集合的排列与组合集合的排列与组合8.2.2 多重集的排列与组合多重集的排列与组合10选取问题选取问题 -组合计数模型组合计数模型1设设 n 元集合元集合 S，
7、从，从 S 中选取中选取 r 个元素个元素.根据是否有序，是否允许重复可以将该问题分为四个子类根据是否有序，是否允许重复可以将该问题分为四个子类型型不重复不重复选选取取重复重复选选取取有序有序选选取取集合的排列集合的排列多重集的排列多重集的排列无序无序选选取取集合的集合的组组合合多重集的多重集的组组合合11集合的排列集合的排列定义定义 从从 n 元集元集 S 中有序、不重复选取的中有序、不重复选取的 r 个元素称为个元素称为 S 的一个的一个 r 排列排列，S 的所有的所有 r 排列的数目记作排列的数目记作 P(n,r)定理定理8.1 证明证明 使用乘法法则使用乘法法则推论推论 S 的环排列数
8、的环排列数 = 12集合的组合集合的组合定义定义 从从 n 元集元集 S 中无序、不重复选取的中无序、不重复选取的 r 个元素称为个元素称为 S 的一个的一个 r 组合，组合，S 的所有的所有 r 组合的数目记作组合的数目记作 C(n,r)定理定理8.2 推论推论 设设n, r为正整数，则为正整数，则 (1) C(n, r)= (2) C(n, r) = C(n, n r) (3) C(n, r)=C(n 1,r 1)+C(n 1,r)13证明方法证明方法方法方法1：公式代入并化简：公式代入并化简方法方法2：组合证明：组合证明实例：证明实例：证明 C(n, r) = C(n, n r) 证证
9、设设 S =1, 2, , n是是n元集合，对于元集合，对于S 的任意的任意 r-组合组合A=a1, a2, , ar，都存在一个，都存在一个S 的的 n r 组合组合S A与之对应与之对应. 显然不同的显然不同的 r 组合对应了不同的组合对应了不同的 n r 组合，反之也对，因组合，反之也对，因此此 S 的的 r 组合数恰好与组合数恰好与 S 的的(n r)组合数相等组合数相等. C(n, r)=C(n 1,r 1)+C(n 1,r) 称为称为 Pascal公式公式，也对应，也对应了了杨杨辉三角形辉三角形， 两种证明方法都适用两种证明方法都适用. 14杨辉三角杨辉三角15基本计数公式的应用基
10、本计数公式的应用解解 分类选取分类选取 A = 1, 4, ,298 B = 2, 5, ,299 C = 3, 6, , 300分别取自分别取自 A, B, C: 各各 C(100,3)A, B, C 各取各取 1 个（分步处理）：个（分步处理）： C(100,1)3 N= C(100,3) + 1003 = 1485100例例1 从从1300中任取中任取3个数使得其和能被个数使得其和能被3整除有多少种整除有多少种方法？方法？16基本计数公式的应用基本计数公式的应用(续续)解解: 1000!=1000 999 998 2 1将上面的每个因子分解，若分解式中共有将上面的每个因子分解，若分解式中
11、共有i 个个5, j 个个2，那么那么min(i, j)就是就是0的个数的个数. 1, ,1000中有中有 500个是个是 2 的倍数，的倍数，j 500; 200个是个是 5 的倍数，的倍数， 40个是个是 25 的倍数（多加的倍数（多加 40 个个 5），）， 8个是个是 125 的倍数（再多加的倍数（再多加 8 个个 5），）， 1个是个是 625 的倍数（再多加的倍数（再多加 1 个个 5）i = 200+40+8+1 = 249. min(i, j)=249. 例例2 求求1000！的末尾有多少个！的末尾有多少个0？17基本计数公式的应用基本计数公式的应用(续续)例例3 设设A为为
12、n 元集，问元集，问(1) A上的自反关系有多少个？上的自反关系有多少个？(2) A上的反自反关系有多少个？上的反自反关系有多少个？(3) A上的对称关系有多少个？上的对称关系有多少个？(4) A上的反对称关系有多少个？上的反对称关系有多少个？(5) A上既不对称也不是反对称上既不对称也不是反对称 的关系有多少个？的关系有多少个？18多重集的排列多重集的排列定理定理8.3 多重集多重集S=n1 a1, n2 a2, , nk ak，0 ni + (1) 全排列全排列 r = n, n1 + n2 + + nk = n 证明：分步选取证明：分步选取. 先放先放a1, 有有C(n,n1) 种方法；
13、再放种方法；再放a2, 有有C(n n1,n2)种方法种方法, . , 放放ak,有有C(n n1 n2 nk 1,nk) 种方法种方法 (2) 若若r ni 时，每个位置都有时，每个位置都有 k 种选法，得种选法，得 kr.19多重集的组合多重集的组合定理定理8.4 多重集多重集 S=n1 a1, n2 a2, , nk ak，0ni +当当 r ni , S的的r 组合数为组合数为 N = C(k+r 1,r), 证明证明 一个一个 r 组合为组合为 x1 a1, x2 a2, , xk ak，其中其中 x1 + x2 + + xk = r , xi 为非负整数为非负整数. 这个不定方程的
14、这个不定方程的非负整数解对应于下述排列非负整数解对应于下述排列 11 0 11 0 11 0 0 11 x1个个 x2个个 x3个个 xk个个r 个个1，k 1个个 0 的全排列数为的全排列数为20实例实例例例5 排列排列26个字母，使得个字母，使得 a 与与 b 之间恰有之间恰有7个字母，求方个字母，求方法数法数.解：解： 设盒子的球数依次记为设盒子的球数依次记为 x1, x2, , xn, 则满足则满足 x1 + x2 + + xn = r， x1, x2, , xn 为非负整数为非负整数 N = C(n+r 1, r) 例例4 r 个相同的球放到个相同的球放到 n 个不同的盒子里，每个盒
15、子球数个不同的盒子里，每个盒子球数不限，求放球方法数不限，求放球方法数.解：解： 固定固定a 和和 b, 中间选中间选7个字母，有个字母，有2 P(24,7)种方法，种方法，将它看作大字母与其余将它看作大字母与其余17个字母全排列有个字母全排列有18！种，共！种，共 N = 2 P(24,7) 18!21实例实例(续续)例例6 (1) 10个男孩，个男孩，5个女孩站成一排，若没有女孩相邻，个女孩站成一排，若没有女孩相邻， 有多少种方法？有多少种方法？ (2) 如果站成一个圆圈，有多少种方法？如果站成一个圆圈，有多少种方法？解解: (1) P(10,10) P(11,5) (2) P(10,10
16、) P(10,5)/10解：相当于解：相当于2n 不同的球放到不同的球放到 n 个相同的盒子，每个盒子个相同的盒子，每个盒子2个，放法为个，放法为例例7 把把 2n 个人分成个人分成 n 组，每组组，每组2人，有多少分法？人，有多少分法？22实例实例(续续)解解 使用一一对应的思想求解这个问题使用一一对应的思想求解这个问题. a1, a2, , ak ：k个不相邻的数个不相邻的数, 属于集合属于集合1, 2, , nb1, b2, , bk：k个允许相邻的数个允许相邻的数, 属于集合属于集合1, , n (k 1) 对应规则是对应规则是 bi = ai (i 1). i =1, 2, , k 因此因此 N = C(n k+1,k) 例例8 从从S=1, 2, , n中选择中选择 k 个不相邻的数，有多少种个不相邻的数，有多少种方法？方法？23
