（高考复习课件）容斥原理1.docVIP

第六章 容斥原理 定理6.1.1 集合S的不具有性质P1, P2,…, Pm的物体的个数由下式给出: ( …(=(S(-+-+… +(-1)m 其中:第一个求和对集合{1,2,…,m}的所有的1-组合进行, 第二个求和对集合{1,2,…,m}的所有的2-组合进行,依此类推. 推论6.1.2 集合S的具有性质P1, P2,…, Pm之一的物体的个数由下式给出: (…(=-++… +(-1)m+1 例1: 求1到1000不能被5, 6和8整除的数的个数. 6.2 多重集的组合 (第三章) 悬而未决的问题： 令多重集S={n1.a1, n2.a2, 、、、, nk.ak }，n= n1+n2+、、、+nk ，求S的r-组合数，其中0(r(n. 上述问题相当于求解方程x1 +x2+ 、、、+ xk =r 的满足条件0 ( x1 ( n1 , 0 ( x2 ( n2 ,、、、, 0 ( xk ( nk 的整数解的个数。 例1: 确定多重集T={3.a, 4.b, 5.c}的10-组合的个数. 例2: 求满足 1(x1(5, -2(x2(4, 0(x3(5, 3(x4(9条件的方程x1+ x2+ x3+ x4=18的整数解个数. 6.3 错位排列 定义1: 设X={1,2,…,n}, 它的排列用i1 i2…in 表示, 错位排列就是问有多少种排列方法使得 i1 (1, i2 (2, …, in (n. 我们用Dn表示错位排列个数. 显然, D1 =0, D2 =1. 定理6.3.1 对于n(1, Dn =n!(1-+-+…+(-1)n) 一个有趣的结论： e-1=1-+-+… (e=2.718) 即 e-1=+(-1)n+1+(-1)n+2… 当n大于7时, e-1和的误差小于(约1/1000), 因此10位绅士随机拿一顶帽子, 每人都错拿的概率是e-1(37%). 100000位绅士随机拿一顶帽子, 每人都错拿的概率是仍e-1(37%). 推论6.3.2 Dn 满足如下递推关系: Dn =(n-1)( Dn-2 - Dn-1 ) (n=3,4,…) Dn =nDn-1 + (-1)n (n=2,3,…) 6.4 带有禁止位置的排列 定义1: 令X1, X2,…, Xn 是{1,2,..,n}的子集(可以是空集, 子集间可能有重叠) , 用P(X1, X2,…, Xn)表示{1,2,…,n}的所有排列i1 i2…in 的集合, 要求: i1 不在X1内, i2 不在X2内,…, in 不在Xn内. 称这种排列为带有禁止位置的排列，用( P(X1, X2,…, Xn)(表示满足上述条件的排列数. 例： 在n(n的棋盘上放置n个非攻击型车，现在规定一些禁止位置： P1：表示在第一行的车要放在X1的列上（X1是{1，2，、、、，n}的子集）； P2：表示在第一行的车要放在X2的列上（X2是{1，2，、、、，n}的子集）； 、、、、 Pn：表示在第一行的车要放在Xn的列上（Xn是{1，2，、、、，n}的子集）； 满足性质Pj的n个非攻击型车的摆放方法相当于第j行的车只能放在Xj规定的列上，即相当于{1，2，、、、，n}的n-排列i1 i2 …in ,满足ij ( Xj . 设满足性质Pj 的n-排列的集合为Aj ，（j=1,2,…,n）. 问题就是求( …(。 定理6.4.1 将n个非攻击型车放到有禁止位置的n行n列棋盘上的方法数等于: n!-r1(n-1)!+ r2(n-2)!+…+(-1)k rk(n-k)!+…+(-1)n rn. 例1: 6个非攻击型车放到6(6棋盘上, 禁止位置如图所示, 求放置方法数. 6.5 其它的禁排位置问题 定义1: 设集合S={1,2,…,n}, 它的不出现12, 23, … ,(n-1)n的排列称相对禁止位置排列. 相对禁止位置排列的排列数用Qn 表示. 定理6.5.1 对于n(1, Qn =n! -(n-1)! + (n-2)! +…+(-1)n 1! Qn 和Dn 的关系: Qn = Dn + Dn-1 (n(2)