nullnull第三章 容斥原理及其应用
§3.1 容斥原理
容斥原理又称为排斥原理,它利用集合的基本运算 (交或并)解决实际中的计数问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
。
设S为一个有限集，A为其子集，则
|A|=|S|-|Ā|， 或 |Ā|=|S|-|A|。
若A1、A2为S的两个子集，则
|A1∪A2|=|A1|+|A2|-|A1∩A2|，
|Ā1∩Ā2|=|S|- |A1|-|A2|+|A1∩A2|。
以上第二个公式的含义：先将所有元素容纳在内，再排斥掉A1 和A2中元素，再重新容纳A1∩A2中元素。null 一般地，令 ,且Ai为S中具有性质Pi的元素
集合，i=1,2,…,m，则 为S中同时具有性质P1,
P2,…,Pm的元素集合； 为S中既不具有性质P1,
又不具有性质P2,…,更不具有性质Pm的元素集合,即
性质P1, P2,…,Pm均不具有的元素集合。
null 如何通过Ai来 或 中元素的个数？
null容斥原理:
①S中均不具有性质P1, P2,…,Pm的元素个数为
②S中至少具有性质P1, P2,…,Pm中一个的元素个数为:
null例1 某校甲班有学生60名,24个学生喜欢数学,28个学生喜欢物理,26个学生喜欢化学, 10个学生既喜欢数学又喜欢物理,8个学生既喜欢数学又喜欢化学,14个学生既喜欢物理又喜欢化学,6个学生对这三门课都喜欢,问有多少个学生对这三门课都不喜欢? null例2 求从1到1000的整数中不能被5、6和8中任何一个整除的整数的个数。
例3 定义欧拉
函数
excel方差函数excelsd函数已知函数 2 f x m x mx m 2 1 4 2拉格朗日函数pdf函数公式下载
φ(n)为小于n且与n互素的正整数的个数。求φ(n)的值。
例4 在由a、b、c、d四个字符构成的n位符号串中，求a、b和c均出现的符号串的数目。
例5 求长为5的二进制数的个数，其中要求每个1都同另一个1相邻。null§3.2 错排问题 设a1, a2,…,a n为{1,2,…,n}的一个排列，如对任意i，有ai ≠i，则称该排列为n错排。记n错排的个数为Dn，则
证明：null例1 求{1,2,…,n}的全排列中，正好只有r(0≤r≤n)个元素在原来位置上的排列数。
例2 将n册书分给n位学生，之后又收回再分给这n个学生。问有多少种分配
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
使得没有一个学生两次得到同一册书。
例3 求由数字1,2,…,8所组成的全排列中，偶数均不在其自然位置上的全排列个数。
§3.3 容斥原理的一般形式§3.3 容斥原理的一般形式设有n个性质P1, P2,…,Pn，S为全集。令Ai为S中具有性质Pi的元素集合，i=1,2,…,n，则
A1∪ A2∪…∪An
为S中至少具有一个性质的元素集合，
为S中所有n个性质均不具有的元素集合。由容斥原理可得|A1∪ A2∪…∪An|和 。
问：S中恰具有i个性质的元素个数是多少？如何求？--------容斥原理的一般形式。null对i=1,2,…,n，令则有null例1 某校有12个教师，已知教数学的有８位，教物理的有６位，教化学的５位；教数、理５位，教数、化４位，教理、化３位；教数理化３位。问教其他课的有几位？只教一门的有几位？只教两门的有几位？
解 令教数学的教师属于A1，教物理的属于A2，教化学的属于A3。则P0＝12，
P1＝| A1 |+| A2|+| A3 |＝8+6+5＝19;
P2＝| A1∩A2|+ | A1∩A3|+| A2∩A3|＝12；
P3＝| A1∩A2∩A3|＝3；
故教其他课的老师数为：
q0＝P0 －P1 +P2－P3＝２。
null恰好一门的教师数：
q1＝P1－2P2 + 3P3＝4，
恰好教两门的老师数为：
q2＝P2－3P3＝3。
例2 七人围圆桌就座，其中有三对夫妇，问
(1)所有夫妇均不相邻的坐法有多少种？(没有男女相间的限制)
(2)恰好有两对夫妇不相邻的坐法有多少种？(即恰有一对夫妇相邻的坐法)
浙公网安备 33021202002483