《清华离散数学(第2版)：.ppt》由会员分享，可在线阅读，更多相关《清华离散数学(第2版)：.ppt（25页珍藏版）》请在金锄头文库上搜索。
1、第第9 9章章 容斥原理容斥原理1第第9章章 容斥原理容斥原理9.1 容斥原理容斥原理9.2 对称筛公式及其应用对称筛公式及其应用29.1 容斥原理容斥原理9.1.1 容斥原理的基本形式容斥原理的基本形式容斥原理容斥原理容斥原理的推论容斥原理的推论9.1.2 容斥原理的应用容斥原理的应用计数多重集的计数多重集的r-组合数组合数计数限制条件的元素数计数限制条件的元素数计算欧拉函数的值计算欧拉函数的值证明组合恒等式证明组合恒等式3容斥原理的基本形式容斥原理的基本形式定理定理9.1 设设S为有穷集，为有穷集，P1,P2, , Pm是是m种性质，种性质，Ai是是S中具有性质中具有性质Pi 的元素构成的
2、子集，的元素构成的子集， 是是Ai 相对于相对于S 的补集，的补集， i=1, 2, , m. 则则 S 中不具有性质中不具有性质P1, P2, , Pm的元的元素数为素数为4证明证明证明方法：数学归纳法、组合分析证明方法：数学归纳法、组合分析证证 组合分析组合分析.若若 x 不具有任何性质，则对等式右边贡献为：不具有任何性质，则对等式右边贡献为： 1 0 + 0 0 + +( 1)m 0 = 1 若若 x 具有具有n 条性质，条性质，1 n m, 则对等式右边的贡献为：则对等式右边的贡献为： 5推论推论推论推论 S S 中至少具有其中一条性质的元素数为中至少具有其中一条性质的元素数为证证6应
3、用应用计数多重集的计数多重集的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-组合组
4、合 7计数多重集的计数多重集的r-组合数（续）组合数（续）注意：性质的设定与要求条件相反注意：性质的设定与要求条件相反 性质彼此独立，不同性质的元素计数互不影响性质彼此独立，不同性质的元素计数互不影响8应用应用计数限制条件的元素数计数限制条件的元素数例例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| = 4
5、0，|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|=0N=27+3. 9应用应用欧拉函数的值欧拉函数的值例例3 计算欧拉函数的值计算欧拉函数的值 (n). 欧拉函数欧拉函数 ：小于：小于 n 且与且与 n 互素的自然数的个数互素的自然数的个数解解 n 的素因子分解式的素因子分解式: Ai = x | 0 x n 1，且，且 pi 整
6、除整除 x ， 10应用应用证明交错和的恒等式证明交错和的恒等式证：证：S=1,2,n, A=1,2,m，计数，计数S 中包含中包含A的的r-子集子集. Pj: 在在S 的的 r-子集中不包含子集中不包含 j, j =1, 2, , m例例4 4 证明证明119.2.1 对称筛公式及其应用对称筛公式及其应用对称筛公式对称筛公式错位排列计数错位排列计数9.2.2 棋盘多项式与有限制条件的排列棋盘多项式与有限制条件的排列布棋方案与有限制条件排列的对应布棋方案与有限制条件排列的对应棋盘多项式及其性质棋盘多项式及其性质布棋方案数的计数布棋方案数的计数9.2 对称筛公式及其应用对称筛公式及其应用12对称
7、筛公式对称筛公式令令, |S|=N,对称筛公式对称筛公式: (容斥原理的特殊情况容斥原理的特殊情况) 使用条件：使用条件：不同性质对计数的影响对称不同性质对计数的影响对称.各性质计数是独立的各性质计数是独立的.13应用应用错位排列计数错位排列计数错位排列数记作错位排列数记作 Dn , 设设 S 为为 1, 2, , n 的排列的集合，的排列的集合，Pi 是其中是其中 i 在第在第 i 位的性质，位的性质，i=1, 2, , n. 14错位排列实例错位排列实例例例1 1 8个字母个字母 A, B, C, D, E, F, G, H 的全排列中，使得的全排列中，使得4个个 字母不在原来位置的排列数
8、字母不在原来位置的排列数.解：解：4 4个个字母字母的错排数为的错排数为15错位排列的性质错位排列的性质3. . Dn为偶数当且仅当为偶数当且仅当n为奇数为奇数. 4. 当当 n 充分大时，充分大时，Dn/n! 趋向于趋向于1/e. 证明思路：证明思路：1.使用组合分析，按照第使用组合分析，按照第 1 位是什么数分类计数位是什么数分类计数.2.将将 n! 个排列按照出现错位的个数分类计数个排列按照出现错位的个数分类计数3.归纳证明归纳证明4.将将 Dn 的值代入取极限的值代入取极限16排列与布棋方案排列与布棋方案一个棋盘由大小相同的正方形方格构一个棋盘由大小相同的正方形方格构成，一个方格中允许
9、放入一个棋子成，一个方格中允许放入一个棋子. .在向棋盘布棋时，要求任何两个棋子在向棋盘布棋时，要求任何两个棋子既不能布在棋盘的同一行，也不能布既不能布在棋盘的同一行，也不能布在同一列上在同一列上. . 排列排列 i1 i2 in 表示表示: 第一行的棋子放在第第一行的棋子放在第 i1 列列 第二行的棋子放在第第二行的棋子放在第 i2 列列 第第 n 行的棋子放在第行的棋子放在第 in 列列步棋方案步棋方案 排列：排列： 2 5 1 3 6 4 17 排列与排列与 n 个棋子在个棋子在 n n 棋盘的布棋方案一一对应棋盘的布棋方案一一对应 位置有限制的排列与有禁区的步棋方案一一对应位置有限制的
10、排列与有禁区的步棋方案一一对应 布棋方案与棋盘多项式布棋方案与棋盘多项式rk(C) 表示表示 k 个棋子在棋盘个棋子在棋盘 C上的布棋方案数，则称上的布棋方案数，则称为为棋盘多项式棋盘多项式 位置受限的排列：位置受限的排列： 2 5 1 3 6 4 一般表示：一般表示： i1 i2 i6 ij j, j = 1, 2, , 6 18棋盘多项式的性质棋盘多项式的性质Ci ：去掉某个给定方格所在的行和列之后剩余棋盘：去掉某个给定方格所在的行和列之后剩余棋盘Cl ：去掉某个给定方格之后剩余棋盘：去掉某个给定方格之后剩余棋盘C1 和和 C2 表示两个分离的棋盘表示两个分离的棋盘则不难证明：则不难证明：
11、19简单棋盘多项式的结果简单棋盘多项式的结果20有禁区的排列有禁区的排列限制某些数字不能出现在某些位置的排列，对应于有禁限制某些数字不能出现在某些位置的排列，对应于有禁区的放棋方案区的放棋方案. .有下述计数定理有下述计数定理. . 定理定理9.2 C 是是 n n 的具有给定禁区的棋盘，禁区对应于的具有给定禁区的棋盘，禁区对应于1,2, , n的元素在排列中不允许出现的位置，则这种有的元素在排列中不允许出现的位置，则这种有禁区的排列数为禁区的排列数为 中中ri 是是 i 个棋子布置到禁区的方案数个棋子布置到禁区的方案数使用条件：使用条件：棋盘为棋盘为 n n, , 小禁区小禁区 21定理证明
12、定理证明证证不考虑禁区限制，不带编号棋子的布棋方案数不考虑禁区限制，不带编号棋子的布棋方案数: n!，考虑棋子编号，布棋方案数考虑棋子编号，布棋方案数: n! n!Pj: 第第 j 个棋子落入禁区的性质个棋子落入禁区的性质 ，j =1, 2, , n给定的给定的1个棋子落入禁区的方案数个棋子落入禁区的方案数: N1=r1(n 1)!(n 1)! 给定的给定的2个棋子落入禁区的方案数个棋子落入禁区的方案数: N2=2! r2 (n 2)!(n 2)!给定的给定的k个棋子落入禁区的方案数个棋子落入禁区的方案数: Nk=k! rk (n k)! (n k)!n个棋子落入禁区的方案数：个棋子落入禁区的
13、方案数： Nn=n! rn 0! 0! 22定理证明（续）定理证明（续）带编号的棋子不落入禁区的方案数带编号的棋子不落入禁区的方案数: N0不带编号的棋子不落入禁区的方案数不带编号的棋子不落入禁区的方案数: N 两者关系：两者关系：N0=N n!23应用实例应用实例工作分配工作分配 N = 4! 6 3! + 10 2 4 = 24 36 + 20 4 = 4 解：禁区的棋盘多项式为解：禁区的棋盘多项式为根据定理根据定理9.2得得例例2 G, L, W, Y 4 位工作人位工作人员，员，A, B, C, D 为为 4 项工作项工作.每个人不能从事的工作如每个人不能从事的工作如图中棋盘的禁区所示图中棋盘的禁区所示. 问有问有 多少种分配方案？多少种分配方案？24应用实例应用实例错排问题错排问题例例3 错位排列的禁区是主对角线上的所有方格错位排列的禁区是主对角线上的所有方格关于禁区的棋盘多项式如下：关于禁区的棋盘多项式如下：25
