组合数学课件--第三章第三节广义的容斥原理.ppt

* 如果求正好过上述四条线段中两条的路径数 不通过上述四条线段中任何一条的路径数 路径数问题: **** * 1、求n对夫妻排成一行，夫妻相邻的排列数。 解： 3.10,n对夫妻问题。 2、求n对夫妻排成一行，夫妻不相邻的排列数。 解：设Ai是第i对夫妻排在一起的排列集。 正好有m对夫妻排在一起的方案数 * 解：设Ai是第i对夫妻排在一起的排列集。 3.10,n对夫妻问题。 * 3.10,n对夫妻问题。 正好有m对夫妻排在一起的方案数 * 3,n对夫妻围一圆桌而坐，夫妻相邻的排列数。 3.10,n对夫妻问题。 4、n对夫妻围一圆桌而坐，夫妻不相邻的方案数？ 解：设Ai是第i对夫妻排在一起的排列集。 正好有m对夫妻排在一起的方案数 * 3.10,n对夫妻问题。 * 习 题 3.20 在由a,a,a,b,b,b,c,c,c组成的排列中,求满足下列条件的排列数。 (1)不存在相邻三元素相同。 (2)相邻两元素不相同 设A是有两个a相邻的排列数。 B是有两个b相邻的排列数。 C是有两个c相邻的排列数。 解(2)： * 习 题 设A是两个a相邻的排列数。 B是两个b相邻的排列数。 C是两个c相邻的排列数。 解： * 习 题 * 设X是a与aa相邻的排列数。 Y是b与bb相邻的排列数。 Z是c与cc相邻的排列数。 习 题 **** 谢谢！ * 第3章 容斥原理与鸽巢原理 3.1 De Morgan定理 1 3.2 容斥原理 1 3.3 容斥原理举例 1 3.4 棋盘多项式与有限制的排列 2 3.5 有禁区的排列 2 3.6 广义的容斥原理 2 3.7 广义容斥原理的应用 3 2.8 第二类Stirling数的展开式 1 2.9 欧拉函数?(n) 1 2.10 n对夫妻问题 3 *2.11 Mobius反演定理 × 2.12 鸽巢原理 4 2.13 鸽巢原理举例 4 2.14 鸽巢原理的推广 4 *2.15 Ramsey数 × * 3.6 广义的容斥原理 容斥原理解决的问题: 广义的容斥原理解决的问题 * 3.6 广义的容斥原理 求只参加了数学课的人数？ 只参加了物理课的人数？ 只参加了化学课的人数？ 例3.6.1：一个学校只有数学，物理，化学3门课 。学这3门课的学生人数分别是170,130,120；同时学数学、物理两门课的学生有45人；同时学数学、化学的有20人；同时学物理、化学的有22人；同时修三门课的学生有3人，问这个学校共有多少学生? 只参加了数学、物理课的人数？ 只参加了数学、化学课的人数？ * 单修一门数学，即修数学而不修物理和化学的学生数；可如下表示： 解：设M为修数学课的学生集合；P为修物理课的学生集合；C为修化学课的学生集合， 求只参加了数学课的人数？ 3.6 广义的容斥原理 * 关于M互为补集 M P C 因此：只参加数学课学习的人数有 3.6 广义的容斥原理 * 只学数学、物理两门课 M P C 3.6 广义的容斥原理 *** * 3.6.1 一般公式 假定全集是N,其中有A1,A2,…,An个子集， 定义：当m0时 对于特殊情况m=0时定义: 3.6 广义的容斥原理 * 3.6 广义的容斥原理 定义 是正好存在于m个集合的元素 的个数 * 例3.6.2 设N={1,2,3,…,14},4个集合A1,A2,A3,A4。 A1={2,5,8,12,13,}； A2={1,3,5,6,7,8,10,12,14}； A3={1,4,5,7,12,13}； A4={1,4,5,7,12,14}。 3.6 广义的容斥原理 * N 1 2 3 4 5 6 7 8 9 10 11 12