组合数学一.引言●设U为该单位所有人集合,A,B分别为学英语,法语人的集合,如图所示.在一些计数问题中,经常遇到间接计算一个集合中具有某种性质的元素个数比起直接计算来得简单.例如:计算1到700之间不能被7整除的整数个数.先计算1到700之间能被7整除的整数个数=700/7=100,所以1到700之间不能被7整除的整数个数=700-100=600.上面举的间接计数的例子是利用了如下原理：如果A是集合S的子集,则A中的元素个数等于S中的元素个数减去不在A中的元素个数,这个原理可写成：●原理的重要推广,称之为容斥原理,并且将它运用到若干问题上去,其中包括：错位排列、有限制的排列、禁位排列和棋阵多项式等.DeMorgan定理:设A,B为全集U的任意两个子集,则证明从略1.两个集合的容斥原理设A和B是分别具有性质P1和P2的元素的集合,则同时被5和7整除的整数个数2.三个集合上的容斥原理设A,B,C为任意三个集合,则有4.集合n中不具有a1,a2,a3…之一元素的个数为（余集形式）例求在1到10000的整数中不能被4,5,6任意一个整除的数的个数.三.容斥原理的应用实例1.错排问题利用容斥原理很容易理解错排数列通项公式的组合意义.（1..n）的错位排列个数记为Dn.结论如下：Aj=(n-1)!,j=1,2,3,,n.AiAj=(n-2)!,i,j=1,2,3,,n,但ij.对于任意整数k且1kn,则有17课堂思考题-被毁坏的玉米地选做题：孪生项链