[清华离散数学第2版9.1-2.ppt

第9章 容斥原理 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第9章 容斥原理 9.1 容斥原理 9.2 对称筛公式及其应用 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 9.1 容斥原理 9.1.1 容斥原理的基本形式 容斥原理 容斥原理的推论 9.1.2 容斥原理的应用 计数多重集的r-组合数 计数限制条件的元素数 计算欧拉函数的值 证明组合恒等式 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 容斥原理的基本形式 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 证明 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 推论 推论 S 中至少具有其中一条性质的元素数为 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 应用——计数多重集的r-组合数 例1 求多重集 B = { 3a, 4b, 5c} 的 10-组合数 解：令 S = { x | x 是 a, b, c 任意重复的10-组合} A1 = { x | xS，x 中至少含4个 a } = { x | x 是 a, b, c 的任意 6-组合} A2 = { x | xS，x 中至少含 5 个 b } = { x | x 是 a, b, c 的任意 5- 组合} A3 = { x | xS，x 中至少含 6 个c } = { x | x 是 a, b, c 的任意 4-组合} Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 计数多重集的r-组合数（续） 注意：性质的设定与要求条件相反 性质彼此独立，不同性质的元素计数互不影响 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 应用——计数限制条件的元素数 例2 求不超过120 的素数个数 解：112 = 121，不超过120的合数的素因子可能是2,3,5,7， S = { x | xZ, 1x120 }, |S| = 120 被2, 3, 5, 7 整除的集合分别为 A1, A2, A3, A4： |A1| = 60，|A2| = 40，|A3| = 24，|A4| = 17 |A1A2|= 20, |A1A3|=12, |A1A4|=8, |A2A3|=8, |A2A4|=5, |A3A4|=3 |A1A2A3|=4, |A1A2A4|=2, |A1A3A4|=1, |A2A3A4|=1，|A1A2A3A4|=0 N=27+3. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile