组合数学第三章容斥原理.ppt

《组合数学第三章容斥原理.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、三、有限制位置的排列及棋子多项式一、容斥原理二、容斥原理的应用四、Mobius反演及可重复的圆排列第三章容斥原理3.1容斥原理定理3.1.1:设S是有限集合，是同集合S有关的m个性质，设Ai是S中具有性质Pi的元素构成的集合是S中不具有性质Pi的元素构成的集合，则S中不具有性质的元素个数为：推论3.1.1:设S是有限集合，是同集合S有关的m个性质，设Ai是S中具有性质Pi的元素构成的集合则S中至少具有一个性质的元素个数为：机动目录上页下页返回结束例1:1到1000之间不能被5,6,8整除的整数有多少个？例2：求由a,b,c,d四个字符构成的n位符号串中，机动目录

2、上页下页返回结束a,b,c,d至少出现一次的符号串的数目。机动目录上页下页返回结束例3：欧拉函数表示小于n且与n互素的整数的个数,例4：若图G有n个顶点，且不含有完全k(k≥2)子图，则它的顶点的度数d(x)满足不等式其中X是图G的顶点集。设S是有限集合，是S上的性质集合，用N(r)表示集合S中恰好具有P中r个性质的元素个数。表示S中具有性质机动目录上页下页返回结束的元素个数若集合S中某元素x恰好具有P中k+r个性质,则x在w(k)中计算了而对于S中具有P中少于k个性质的元素，则不计算在w(k)中。机动目录上页下页返回结束定理3.1.2:设集合S中具有性质集合中

3、恰好r个性质的元素个数为N(r)，则例5:某学校有12位教师，已知教数学课的老师有8位，教物理课的老师有6位，教化学课的老师有5位，其中有5位教师既教数学又教物理，4位教师既教数学又教化学，3位教师既教物理又教化学，还有3位教师兼教这三门课，试问：（1）教数、理、化以外的课的教师有几位？（2）只教数、理、化一门课的教师有几位？（3）正好教数、理、化中两门课的教师有几位？机动目录上页下页返回结束3.2容斥原理的应用1.具有有限重数的多重集合的r组合数例1:求的10组合数。多重集合的m组合数。机动目录上页下页返回结束机动目录上页下页返回结束2.错排问题集合的一个错排

4、是的全排列该集合的一个满足条件即集合的一个没有一个数字在它的自然顺序位置上的全排列。用Dn记的全部错排个数，则机动目录上页下页返回结束定理3.2.1:对任意正整数n，有递推关系：机动目录上页下页返回结束2.有禁止模式的排列问题用Qn表示的不出现12,23,…,(n-1)n这些模式并规定的全排列的个数。则有：定理3.2.2：对任意正整数n，有机动目录上页下页返回结束例2：多重集合的全排列中不出现模式的排列有多少中？机动目录上页下页返回结束例3(menage问题）N对夫妇参加宴会围桌就座，要求男女相间并且每对夫妇两人不得相邻，问有多少种就座方式？