《离散数学基本的组合计数公式》由会员分享，可在线阅读，更多相关《离散数学基本的组合计数公式（52页珍藏版）》请在金锄头文库上搜索。
1、组合数学的研究内容 l 组合存在性 l 组合计数 l 组合枚举 l 组合优化 本书的内容 l 基本的组合计数公式 l 递推方程与生成函数第四部分 组合数学1第十二章 基本的组合计数公式主要内容 l 加法法则与乘法法则 l 排列与组合 l 二项式定理与组合恒等式 l 多项式定理212.1 加法法则与乘法法则l 加法法则l 乘法法则l 分类处理与分步处理3加法法则加法法则：事件A 有 m 种产生方式，事件 B 有n 种产生方式，则 “事件A或B” 有 m+n 种产生方式.使用条件：事件 A 与 B 产生方式不重叠适用问题：分类选取推广：事件 A1有 p1种产生方式，事件 A2有 p2 种产生方式，
2、, 事件 Ak 有 pk 种产生的方式，则 “事件A1或 A2或 Ak” 有 p1+p2+pk 种产生的方式. 4乘法法则乘法法则：事件A 有 m 种产生方式，事件 B 有n 种产生方式，则 “事件A与B” 有 m n 种产生方式.使用条件：事件 A 与 B 产生方式彼此独立适用问题：分步选取推广：事件 A1有 p1种产生方式，事件 A2有 p2 种产生方式，, 事件 Ak 有 pk 种产生的方式，则 “事件A1与 A2与 Ak” 有 p1 p2 pk 种产生的方式. 5分类处理与分步处理l 分类处理：对产生方式的集合进行划分，分别计数，然 后使用加法法则l 分步处理：一种产生方式分解为若干独
3、立步骤，对每步 分别进行计数，然后使用乘法法则l 分类与分步结合使用先分类，每类内部分步先分步，每步又分类6实例：关系计数例1 设A为 n 元集，问 (1) A上的自反关系有多少个？ (2) A上的对称关系有多少个？ (3) A上的反对称关系有多少个？ (4) A上的函数有多少个？其中双射函数有多少个？. (2) 考虑对称关系的矩阵. i 行 j 列(ij)的元素 rij = rji. 能够独立 选择0或1的位置有(n2n)/2个. 加上主对角线的n个位置，总计 (n2+n)/2个位置，每个位置2种选择，根据乘法法则，构成矩阵的方法数是 (1) 在自反关系矩阵中，主对角线元素都是1，其他位置的
4、元 素可以是1，也可以是0，有2种选择. 这种位置有n2n个，根 据乘法法则，自反关系的个数7解答(3) 非主对角线位置分成 (n2n)/2组，每组包含元素rij和rji. 根 据反对称的性质，rij与rji的取值有以下3种可能：rij=1, rji=0； rij=0, rji=1； rij=rji=0. 所有这些位置元素的选择方法数为 . 再考虑到主对角线元素的选取，由乘法法则总方法数为(4) 设A=x1,x2,xn，任何A上的函数 f:AA具有下述形式：f=, 其中每个yi（i=1,2,n）有n种可能的选择，根据乘法法则， 有nn个不同的函数. 若 f 是双射的，那么y1确定以后，y2只有
5、 n1种可能的取值 , yn只有1种取值. 构成双射函数的方法数 是n(n1)(n2)1 = n!. 8A 0 netid (7 位)hosted (24位)B 1 0 netid (14位) hostid (16位) C 1 10 netid (21位) hostid (8 位) D 1 110 (28位) E 1 1110 (27位)例2：Ipv4网址计数32位地址 网络标识+主机标识 (1) A类：最大网络； B类：中等网络； C：小网络；D：多路广播； E：备用 (2) 限制条件：1111111在A类中的netid部分无效hostid部分不允许全0或全1 9netid hostid A
6、类： 0+7位， 24位 B类： 10+14位， 16位 C类： 110+21位， 8位 限制条件：1111111在A类中的netid部分无效hostid部分不允许全0或全1 A类：netid 271, hosted 2242，NA127167772142130706178 B类：netid 214, hosted 2162， NB16384655341073709056 C类：netid 221, hosted 282, NC2097152254532676608 NNA+NB+NC3737091842解答10选取问题：设 n 元集合 S，从 S 中选取 r 个元素.根据是否有序 , 是否允
7、许重复, 将该问题分为四个子类型不重复选取重复选取 有序选取集合的排列多重集的排列无序选取集合的组合多重集的组合12.2 排列与组合11定义12.1 设S为n元集， (1) 从 S 中有序选取的 r 个元素称为 S 的一个 r 排列，S 的 不同 r 排列总数记作 P(n,r), r=n的排列是S的全排列. (2) 从 S 中无序选取的 r 个元素称为 S 的一个 r 组合，S 的 不同 r 组合总数记作 C(n,r)集合的排列定理1.1 设n, r为自然数，规定0!=1，则12下面考虑 n r 的情况. (1) 排列的第一个元素有 n 种选择的方式. 排列的第二个元素 有n1种选法, , 第
8、 r 个元素的方式数 n r+1. 根据乘法 法则，总的选法数为n(n 1)( n2)(n r+1) =(2) 分两步构成 r 排列. 首先无序地选出r个元素，然后再构 造这r个元素的全排列. 无序选择r个元素的方法数是C(n,r) ；针对每种选法，能构造 r!个不同的全排列. 根据乘法法 则，不同的 r 排列数满足 P(n, r)=C(n,r) r!组合数C(n,r)也称为二项式系数，记作证明13推论 设n, r为正整数，则(1) C(n,r)=(2) C(n,r) = C(n, nr) (3) C(n,r)=C(n1,r1)+C(n1,r)推论例3 证明 C(n,r) = C(n,nr)
9、证 设 S =1, 2, , n是n元集合，对于S 的任意 r 组合 A=a1, a2, , ar，都存在一个S 的 nr 组合SA与之对应. 显然不同 的 r 组合对应了不同的 nr 组合，反之也对，因此 S 的 r 组合 数恰好与 S 的 nr 组合数相等. 公式(3) 称为 Pascal公式，也对应了杨辉三角形证明方法：公式代入并化简，组合证明14杨辉三角111121133114641510 1011615 20515611n=0n=1n=2n=3n=4n=5n=6r=0r=1r=2r=3r=4r=5r=615多重集的排列与组合定义12.2 多重集 S=n1a1, n2a2, , nka
10、k，n=n1+n2+nk 表 示 S 中元素的总数. (1) 从S 中有序选取的r个元素称为多重集 S 的一个 r 排列. r=n 的排列称为 S 的全排列 (2) 从 S 中无序选取的 r 个元素称作多重集 S 的一个r 组合 注意： l 多重集中元素的重复度，0 分类. 给定 k，选 A方法数是C(n,k)； 选 B 中剩下的 nk 个元素, 每个元素有2 种选法，有2nk 个 不同的 B 集合. 由乘法法则，这样的有C(n,k)2nk 个， 再使用加法法则和二项式定理，从而得到4. 设 S 是 n 元集，N 表示满足 ABS 的有序对 的个 数，用二项式定理证明N=3n方法二. S中的每个元素可以有3种选法：同时加入A和B，不 加入 A 但加入B，A 和 B 都不加入； 因此，n 个元素总共 3n 种选法. 49练习55. 证明方法一. 利用已知等式将上述两式相加得50练习5方法二 利用积分51练习66. 求和52
