组合计数
组合计数
12.1加法法则与来法法则口加法法则口乘法法则口分类处理与分步处理2
2 12.1 加法法则与乘法法则 加法法则 乘法法则 分类处理与分步处理
加法法则加法法则：事件A有m种产生方式，事件B有n种产生方式，则“事件A或B"有m+n种产生方式.使用条件：事件A与B产生方式不重叠适用问题：分类选取推广：事件A有Pi种产生方式，事件A2有P2种产生方式，…,事件Ak有Pk种产生的方式，则“事件A或A或.Ak”有P1+p+...+pk种产生的方式.3
3 加法法则 加法法则：事件A 有 m 种产生方式，事件 B 有n 种产生方 式，则“事件A或B” 有 m+n 种产生方式. 使用条件：事件A 与 B 产生方式不重叠 适用问题：分类选取 推广：事件A1有 p1种产生方式，事件A2有 p2 种产生方 式，., 事件 Ak 有 pk 种产生的方式，则“事件A1或 A2或. Ak ” 有 p1+p2+.+pk 种产生的方式
乘法法则乘法法则：事件A有m种产生方式，事件B有n种产生方式，则“事件A与B"有m n种产生方式使用条件：事件A与B产生方式彼此独立适用问题：分步选取推广：事件A有Pi种产生方式，事件A2有P2种产生方式，…,事件Ak有Pk种产生的方式，则“事件A与A2与.Ak”有P1P2….Pk种产生的方式.4
4 乘法法则 乘法法则：事件A 有 m 种产生方式，事件 B 有n 种产生 方式，则“事件A与B” 有 m n 种产生方式. 使用条件：事件A 与 B 产生方式彼此独立 适用问题：分步选取 推广：事件A1有 p1种产生方式，事件A2有 p2 种产生方 式，., 事件 Ak 有 pk 种产生的方式，则“事件A1与 A2 与 . Ak ” 有 p1 p2 . pk 种产生的方式
分类处理与分步处理>分类处理：对产生方式的集合进行划分，分别计数，然后使用加法法则>分步处理：一种产生方式分解为若干独立步骤，对每步分别进行计数，然后使用来法法则>分类与分步结合使用先分类，每类内部分步先分步，每步又分类5
5 分类处理与分步处理 ➢ 分类处理：对产生方式的集合进行划分，分别计数，然后 使用加法法则 ➢ 分步处理：一种产生方式分解为若干独立步骤，对每步分 别进行计数，然后使用乘法法则 ➢ 分类与分步结合使用 先分类，每类内部分步 先分步，每步又分类
实例：关系计数例1设A为n元集，问(1)A上的自反关系有多少个2解：在自反关系矩阵中，主对角线元素都是1，其他位置的元素可以是1，也可以是0，有2种选择.这种位置有n2-n个，根据乘法法则，自反关系的个数2-n6
6 实例：关系计数 例1 设A为 n 元集，问 (1) A上的自反关系有多少个？ 解：在自反关系矩阵中，主对角线元素都是1，其他位置的元 素可以是1，也可以是0，有2种选择. 这种位置有n 2−n个，根 据乘法法则，自反关系的个数 n −n 2 2
实例：关系计数例1设A为n元集，问(2)A上的对称关系有多少个2解：考虑对称关系的矩阵.i行j列(iti)的元素ri=ri.能够独立选择0或1的位置有(n2-n)/2个.加上主对角线的n个位置，总计(n2+n)/2个位置，每个位置2种选择，根据乘法法则，构成矩阵的方法数是2(n°+n)/27
7 实例：关系计数 例1 设A为 n 元集，问 (2) A上的对称关系有多少个？ 解：考虑对称关系的矩阵. i 行 j 列(i≠j)的元素rij = rji. 能够独立 选择0或1的位置有(n 2−n)/2个. 加上主对角线的n个位置，总计 (n 2+n)/2个位置，每个位置2种选择，根据乘法法则，构成矩 阵的方法数是 ( )/ 2 2 2 n +n
解答例1设A为n元集，问(3)A上的反对称关系有多少个2解： 非主对角线位置分成(n2-n)/2组，每组包含元素ri;和rji. 根据反对称的性质，ri与ri的取值有以下3种可能：rj=1, rj=0; rij=0, rji=1; rij=rj=0.所有这些位置元素的选择方法数为 3(n2-n)/2 再考虑到主对角线元素的选取，由乘法法则总方法数为2"3(n2-n)/28
8 解答 解：非主对角线位置分成(n 2−n)/2组，每组包含元素rij和rji. 根 据反对称的性质，rij与rji的取值有以下3种可能： rij=1, rji=0； rij=0, rji=1； rij=rji=0. 所有这些位置元素的选择方法数为 . 再考虑到主对角 线元素的选取，由乘法法则总方法数为 ( )/ 2 2 3 n −n ( )/ 2 2 2 3 n n −n 例1 设A为 n 元集，问 (3) A上的反对称关系有多少个？
解答例1设A为n元集，问(4)A上的函数有多少个？ 其中双射函数有多少个？解：设A={x1,X2.,Xn]，任何A上的函数f:A→A具有下述形式：f=[,,..,]其中每个y;(i=1,2,.,n）有n种可能的选择，根据乘法法则,有n"个不同的函数.若f是双射的，那么yi确定以后，y2只有n-1种可能的取值…,Yn只有1种取值.构成双射函数的方法数是n(n-1)(n-2)...1=n!9
9 解答 解：设A={x1 ,x2 ,.,xn }，任何A上的函数 f:A→A具有下述形式： f={,,.,} 其中每个yi（i=1,2,.,n）有n种可能的选择，根据乘法法则， 有n n个不同的函数. 若 f 是双射的，那么y1确定以后，y2只有 n−1种可能的取值 ,., yn只有1种取值. 构成双射函数的方法数 是n(n−1)(n−2).1 = n!. 例1 设A为 n 元集，问 (4) A上的函数有多少个？其中双射函数有多少个？
例2：Ipv4网址计数32位地址网络标识+主机标识(1) A类：最大网络;B类：中等网络；C：小网络;E：备用D：多路广播;(2)限制条件：1111111在A类中的netid部分无效hostid部分不允许全0或全1A0hostidnetid (7位)(24位)B10netid（14位）hostid(16位）C110hostid(8位）netid(21位)D0111(28位)E10(27位)1710
10 A 0 netid (7位) hostid (24位) B 1 0 netid (14位) hostid (16位) C 1 1 0 netid (21位) hostid (8位) D 1 1 1 0 (28位) E 1 1 1 1 0 (27位) 例2：Ipv4网址计数 32位地址 网络标识+主机标识 (1) A类：最大网络； B类：中等网络； C：小网络； D：多路广播； E：备用 (2) 限制条件： 1111111在A类中的netid部分无效 hostid部分不允许全0或全1