第十二章基本的组合计数公式

第十二章 基本的组合计数公式

漳州师范学院计算机科学与工程系

第十二章 基本的组合计数公式加法法则与乘法法则 排列与组合 二项式定理与组合恒等式 多项式定理 加法法则与乘法法则、排列和组合的定义、 知 识 点：加法法则与乘法法则、排列和组合的定义、排列和组合的生 成算法、 二项式定理、 成算法、基本恒等式、二项式定理、多项式定理 教学要求：深刻理解和掌握排列、组合的基本概念及基本应用。 教学要求：深刻理解和掌握排列、组合的基本概念及基本应用。 教学重点：排列和组合的定义的概念及基本应用。 教学重点：排列和组合的定义的概念及基本应用。 学时: 学时 4

§12.1 加法法则与乘法法则加法法则: 加法法则种产生方式,当 与 如果事件 A 有 m 种产生方式 , 事件 B 有n种产生方式 当A与 种产生方式 B产生的方式不重叠时 ”事件 或B” 有 m + n 种产生方式 产生的方式不重叠时, 事件 产生的方式不重叠时 事件A或 加法原理中事件的产生方式应是互相排斥的 加法法则 (集合形式 集合形式): 若 S=A∪B,A∩B= ,则 |S|=|A|+|B| ∪ ∩ 则 集合形式 加法法则的推广: 个事件,它们的产生方式分别 加法法则的推广 设A1,A2,……,An是n个事件 它们的产生方式分别 个事件 汽车 有p1,p2,……,pn种,当其中任何两个事件产生的方式都不重叠时 事 当其中任何两个事件产生的方式都不重叠时,事 当其中任何两个事件产生的方式都不重叠时 甲地 乙地 或 有 件” A1或A2或……或An”有p1+p2+……+pn种产生方式 陆路 火车 甲地 水路 乙地 飞机 轮船®

§12.1 加法法则与乘法法则乘法法则: 乘法法则种产生方式, 事件B 种产生方式,当 与 产 事件 A 有 m 种产生方式 事件 有n 种产生方式 当A与B产 生的方式彼此独立时, 事件 生的方式彼此独立时 “事件 A 与 B ” 有 mn 种产生方式 乘法法则中各事件的出现应是相互独立的, 也就是说B的出现不受 的出现不受A 乘法法则中各事件的出现应是相互独立的 也就是说 的出现不受 的影响, 同样A的出现也不受 的出现也不受B的影响 的影响 同样 的出现也不受 的影响 乘法法则 (集合形式 : 若 S=A×B, 则 |S|=|A|×|B| 集合形式) 集合形式 × × 乘法法则的推广: 个事件,它们的产生方式分别 乘法法则的推广 设A1,A2,……,An是n个事件 它们的产生方式分别 个事件 当其中任何两个事件产生的方式都彼此独立时, 有p1,p2,……,pn种,当其中任何两个事件产生的方式都彼此独立时 当其中任何两个事件产生的方式都彼此独立时 事件” 事件 A1与A2与……与An有p1p2……pn种产生方式 与 甲地 1 甲地 3 2 3 乙地 1 a 2 b a bs c x 丙地y t d 丁地 z 戊地

c 乙地 d 丙地

®

§12.1 加法法则与乘法法则元集,问 例12.1 设A为n元集 问 为 元集A上的自反关系有多少个 上的自反关系有多少个

A上的函数 f 可以用二元关系表示成 上的函数 n元集 上的二元关系R的关系矩阵 元集A上的二元关系 的关系矩阵 元集 上的二元关系

上、下三角区域1>,<x2,y2>,……,<xn,yn>} f={<x1,y 1 * 0 $ 1 分别有 种不同的选择, A上的反自反关系有多少个 上的反自反关系有多少个 每个y 都有n种不同的选择 每个 i都有 种不同的选择 1+2+…+(n-1) 0 1 * 0 A上的对称关系有多少个 上的对称关系有多少个 个元素 n

R是A上的反对称关系当且仅当在 R第二步确定 2,y1确定后 2只有 是 R是A上的反自反关系当且仅当 第二步确定y 上的反对称关系当且仅当在M 上的反对称关系当且仅当在 非主对角线的位置 确定后y 只有n-1种可能取值 种可能取值 是 A上的自反关系当且仅当 R是上的对称关系当且仅当 是对称矩阵。 是 上的反自反关系当且仅当 上的自反关系当且仅当 R是A上的对称关系当且仅当 R是对称矩阵。 是 上的对称关系当且仅当M 关于主对角线对称的两个位置取值不能全为1。 上,关于主对角线对称的两个位置取值不能全为 。 关于主对角线对称的两个位置取值不能全为 在MR中 对主角线上的元素全都为 …… 对主角线上的元素全都为1, 在MR中 对主角线上的元素全都为0, 对主角线上的元素全都为 主对角线的位置有n个 主对角线上的元素可以是0或 主对角线的位置有 主对角线上的元素可以是 或1,主对角线的位置有 个, 主对角线上的元素可以是0或 主对角线的位置有 主对角线的位置有n个 主对角线上的元素可以是 或1,主对角线的位置有 个, 非主对角线上的元素可以是0或 两个元素取值同时是 非主对角线上的元素可以是 或1。 n步确定 , y 只有一种取值 这两个元素的取值有 非主对角线上的元素可以是0或 。 步确定y 非主对角线上的元素可以是 或1。 步确定 对称位置上,两个元素取值同时是 在每对非主对角线的对称位置上 。 第 n n 在每对非主对角线的对称位置上 两个元素取值有三种 三种不同的情况: 三种不同的情况 非主对角线的位置有n2-n个,根据乘法2 非主对角线的位置有 对称位置上,两个元素取值有三种 非主对角线的位置有n 个 根据乘法 非主对角线的位置有 2-n个,根据乘法 -n)/2对。 个 根据乘法 0或同时是 这样的对称位置共有 根据乘法法则 或同时是1,这样的对称位置共有 或同时是 这样的对称位置共有(n 2 对 不同的情况,这样的对称位置共有 这样的对称位置共有( 不同的情况 这样的对称位置共有 n -n)/2对。 对 法则自反关系的个数是 2 n2-n 法则自反关系的

个数是 2 n2-n (0,0), (0,1), (1,0) n)/2 根据乘法法则对称关系的个数是 2 (n2+2-n)/2 n3 (n 根据乘法法则对称关系的个数是 2 n(n-1)(n-2)……1个不同的构造方法 有 个不同的构造方法 ®

A上的反对称关系有多少个 上的反对称关系有多少个 MR = 是双射时,y 2 当 f 是双射时 i y ,…,yn之间都互不相同 * 1 0 A上的函数有多少个 上的函数有多少个 构造双射的方法: 0 * 构造双射的方法 * 1 0 A上的双射函数有多少个 上的双射函数有多少个 第一步确定y 共有n种可能的取值 第一步确定 1,y1共有 种可能的取值 * 1 0

$ 根据乘法法则,有 1 根据乘法法则 有n 个不同的函数 1 * 0

§12.1 加法法则与乘法法则协议网址计数: 位地址(w.x.y.z):网络标识 主机标识 网络标识+主机标识 例12.2 Ipv4协议网址计数 32 位地址 协议网址计数 网络标识 A类:最大网络；B类:中等网络；C:最小网络；D类:多路广播；E类:备用 类 最大网络 最大网络； 类 中等网络 中等网络； 最小网络 最小网络； 类 多路广播 多路广播； 类 备用 限制条件： 限制条件：1111111 在A 类中的网络标识部分无效 主机标识部分不允许全0或全 主机标识部分不允许全 或全1 或全

A 类: netid 27 1, hostid 224 2 , 地址数 127 * 16777214 地址数: B 类: netid 214, hostid 216 2 , 地址数 16384 * 65534 地址数: C 类: netid 221, hostid 28 2 , 地址数: 地址数 2097152 * 254®

Ipv4协议网址总数 2130706178+1073709056+532676608 = 3737091842 协议网址总数= 协议网址总数

§12.1 加法法则与乘法法则加法法则与乘法法则的其它例子 加法法则与乘法法则的其它例子从城市A到城市 有两条陆路 两条水路, 一条航线, 从城市 到城市B有两条陆路 两条水路 一条航线 到城市 有两条陆路, 则由推广的加法原理知, 种走法。 则由推广的加法原理知 从A到B有2 + 2 + 1 = 5种走法。 到 有 种走法 书架上有三本不同的英语书, 两本不同的日语书, 书架上有三本不同的英语书 两本不同的日语书 两本不 …… 此处隐藏：7156字，全部文档内容请下载后查看。喜欢就下载吧 ……